Table of Contents

Combinatorics

Sommer Term 2017
Stefan Felsner

1. lecture, 18.4.2017

   What is Combinatorics - introductory examples
     Derangements
       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 of odd order 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 
        Extending binomial identities to polynomial identities
      The binomial theorem

   Combinatorics of Permutations
      The type of a permutation
        Enumeration of permutations of given type
      Permutations with k cycles
        Stirling numbers of first kind
        Recursion and raising factorials
      Expected number of cycles 

  The twelvefold way
      Partitions of a set
        Stirling numbers of 2nd kind
        Stirling inversion 
      Partitions on an integer
      

        Generating function of partitions
        The Hardy-Ramanujan-Rademacher formula
        Distinct and odd are equinumerous
        Euler's Pentagonal Number Theorem 

   Fibonacci numbers
      Basic models
      Identities
      Number system (Zeckendorf)
      Binet's formula via generating function

  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

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

       Eulerian numbers 
       Equidistribution of des and exc
       Worpitzky's identity
       q-binomial coefficients

         01-words and inversions
         A first q-binomial theorem
       Subspaces of q-vectorspaces
         A second q-binomial theorem   
   Finite sets and posets
      Intersecting families of subsets

     Posets and lattices
     Sperner's Theorem - LYM inequality
     Erdös-Ko-Rado Theorem - cyclic permutations
 

    Small maximal k-intersecting families
     Shadows and a second proof of Sperner's
    The Kruskal-Katona Theorem

 
    The Lovasz version of Kruskal-Katona
       Erdös-Ko-Rado from LKK
   Symmetric chain decompositins

   Symmetric chain decompositins
      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
        Equivalence with Dilworth's
      Hall's Theorem (Marriage Theorem)
      Applications 
 

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

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

      Applications of the lemma, e.g. Stirling numbers of 2nd kind
      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 

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

     Fisher's inequality
     Kirkman's problem
     Resolvable designs
     Solutions to Kirkman's problem
     3-Designs from PGL(2,q)

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

  Lemma of Lindström, Gessel-Viennot
     Applications
       Evaluating determinants 
       The Binet-Cauchy formula
       Counting disjoint path systems

  Permanents, Determinants and Matchings
      Derangements and a determinant
      Derangements and a permanent
    The permanent
      Basic facts
      The number of perfect matchings of 3-regular bip. graphs 

      Using determinants to evaluate permanents
      Determinants to count matchings of planar bipartite graphs
      Matchings and some tiling problems

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

           symmetric chain decompositions
        Narayana numbers via LGV Lemma 
      Orders on Catalan families
        Associahedron and flips