Table of Contents

Combinatorics

Sommer Term 2023
Stefan Felsner

1. lecture, 18.04.2023

   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

   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 second kind
        Stirling inversion 

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

   Fibonacci numbers
      Identities
      Zeckendorf's number system
      Binet's formula via generating function
                      via linear algebra

  Solving linear recurrences
      The general approach (partial fraction decomposition)
      The matrix approach (companion matrix and Vandermonde) 
      Exponential generating functions (differential equations)		      

  Formal power series
      Basic operations
      Bernoulli numbers and a summation formula
      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 

    A second proof of Sperner's
    The Kruskal-Katona Theorem
       Co-lex order on k-sets
    The Lovasz version of Kruskal-Katona
 

       Erdös-Ko-Rado from LKK
    Symmetric chain decompositions
       Ranked posets
       Products of posets
       Symmetric chain decompositions and products of chains
           Boolean and multiset-lattices

       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 condition
        Perfect matchings in regular bip. graphs
        Applications

       A quantified version of Hall's condition   
     Stable Marriages
       Gale-Shapley Theorem
   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 fundamental theorem: counting orbits with weights 

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

     Steiner triple systems with v = 3 mod 6
     Fisher's inequality
     Construction of the small Witt design 
        P- and Q-classes and a S(2,5,21) 

        The relations Γ and Λ 
        The definition of blocks
     A construction based on the sharp transitivity of
        PGL(2,q) on ordered triples

  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 in 'exact exponential algorithms')
       The Fast-Zeta transform
  Involutions
    Vandermonde determinant and tournaments

    Lemma of Lindström Gessel-Viennot
        Applications
        Evaluating determinants
        Counting monotone polyominos
  Catalan numbers
      5 Catalan families

      More Catalan families
         bijections
         Determining the numbers
            cycle lemma
            reflection principle
            symmetric chain decompositions
        Narayana numbers and the LGV Lemma 
        Tamari lattice