Table of Contents

Combinatorics

Summer 2025
Stefan Felsner

1. lecture, 15.04.2025

   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
   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) 

  Formal power series
      Basic operations
      Bernoulli numbers and a summation formula
      Newton's binomial theorem and roots
      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

       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

    Erdös-Ko-Rado Theorem - cyclic permutations
    Frankl-Wilson Theorem - a linear algebra proof
    Shadows 
      A second proof of Sperner's
    The Kruskal-Katona Theorem
      Co-lex order on k-sets

    Shifting and compresses families
    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

      Orthogonal chain decompositions 
      A probability application of orthogonal chain decompositions
      Duality theorems
       Dilworth's Theorem       
     König-Egervary matching theorem
        Equivalence with Dilworth's
 

      Hall condition
        Perfect matchings in regular bip. graphs
        Quantified version of Hall's condition
   Polya Theorie: Counting with symmetries
        Example: coloring cubes

         Permutation groups and the cycle index
         The Lemma of Cauchy-Frobenius-Burnside
         Polya's first theorem