Table of Contents

Combinatorics

Sommer Term 2013
Stefan Felsner

1. lecture, 8.4.2013

   What is Combinatorics
     What does it mean to count?
       Aspects of counting derangements (fixed point free permutations) P.R.de Montmort
       sequence A000166 in OEIS
       recurrence - summation - asymptotics - generating function

     Orthogonal Latin Squares 
       (Euler's 36 officers problem)
       Orthogonal Latin squares from groups
       MOLS (mutually orthogonal Latin squares)
       There are at most N-1 MOLS of order N
       MOLS and projective planes

   Basic Counting
      Basic rules for counting
      Binomial coefficients
        Models and identities
        Extending binomial coefficients 
        (positive integer -> integer -> complex -> polynomial)
      The binomial theorem

   Fibonacci numbers
      Basic models
      Identities
      Number system (Zeckendorf)

      Binet's formula via generating function
                      via linear algebra
      Continued fractions and continuants
  The twelvefold way
      Partitions of a set
        Stirling numbers of 2nd kind

      Partitions on an integer
        Generating function of partitions
        The Hardy-Ramanujan-Rademacher formula
        Distinct and odd are equinumerous

        Euler's Pentagonal Number Theorem 
      Solving linear recurrences
        The general approach (partial fraction decomposition)

        The matrix approach (companion matrix)
      Exponential generation function for Fibonacci numbers
      Formal power series
        Basic operations
        Bernoulli numbers and sums
        Composition of FPS

        Catalan numbers and their generating function 
      q-Enumeration
        Mac Mahon's maj-index and the equidistribution theorem
        Permutations and inversions
        Eulerian numbers 

          Equidistribution of des and exc
          Worpitzky's identity
        01-words and inversions
        A q-binomial theorem

        Subspaces of q-vectorspaces
        A second q-binomial theorem       
      Finite sets and posets
        Intersecting families of subsets
        Posets and lattices
        Substructures in posets and lattices

       Sperner's Theorem - LYM inequality
        Erdös-Ko-Rado Theorem - cyclic permutations
        Small maximal k-intersecting families
        Shadows

       Some remarks on the Kruskal-Katona Theorem
         Erdös-Ko-Rado from KKT
       Symmetric chains
          Symmetric chain decompositions for multisets
          Symmetric chain decomp. and pairing brackets

 
          An application to Dedekind's problem
      Duality theorems
        Dilworth's Theorem       
        König-Egervary matching theorem

        The Marriage Theorem (Hall condition)
        Applications 
        A quantified Marriage Theorem
     Stable Marriages
        Gale-Shapley algorithm
        Rotations and the lattice of stable marriages        

    Polya Theorie: Counting with symmetries
      Necklaces and colored cubes - two introductory examples
      Permutation groups and the cycle index
      The Lemma of Cauchy-Frobenius-Burnside

      Polya's first theorem: counting orbits of RD
      Weights on R and the induced weight on RD
      Polya's second theorem: counting orbits with weights 

       Linear extensions
        generic algorithm
        dimension of posets
          Boolean lattices and standard examples
        bounds for dimension 
        characterizations of 2-dimensional posets 

   Design Theory
     Sλ(t,k,v) designs
     Some examples and constructions 
     Arithmetic conditions
     Kirkman's problem

     Resolvable designs
     Solutions to Kirkman's problem
     3-Designs from PGL(2,q)
     A construction of the plane S(2,5,21) from K6

       Möbius inversion
         Incidence algebra of a poset
         Zeta function and  Möbius function
         Möbius function of chains and products
         Applications

       Involutions
         Vandermonde determinant and tournaments
         Lemma of Lindström, Gessel-Viennot

       Catalan numbers
         Ten Catalan families
            some bijections
         Determining the numbers
            path reflection
            cycle lemma

            Narayana numbers via LGV Lemma 
         Further directions
            two lattices on Catalan families
            rotations and flips
            the associahedron