Table of Contents

Combinatorics

Sommer Term 2019
Stefan Felsner

1. lecture, 09.04.2019

   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
       Projective planes

       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 of an integer
        The Hardy-Ramanujan-Rademacher formula      

        Generating function of partitions
        Distinct and odd are equinumerous
        Euler's Pentagonal Number Theorem 

   Fibonacci numbers
      Identities
      Binet's formula via generating function
                      via linear algebra
  Solving linear recurrences
      The general approach (partial fraction decomposition)
		      

  Formal power series
     Basic operations
     Exponential generation function for Fibonacci numbers
     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 decompositions
      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 

    Stable Marriages
        Gale-Shapley Theorems
    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 

      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
       3 constructions of an STS(v)
     Projective plane of order 4 from K  

   Möbius inversion
      Incidence algebra of a poset
      Zeta function and  Möbius function
      Möbius function of chains and products
      Inclusion-Exclusion, an example

    Counting k-covers
       (An application from 'exact exponential algorithms')
       The Fast-Zeta transform
  Involutions     
    Vandermonde determinant and tournaments

  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
      5 Catalan families

     More 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