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
 

  Design Theory
     Sλ(t,k,v) designs
     Examples and constructions based on 
        linear algebra / group theory
     Arithmetic conditions
     projective planes
     Kirkman's problem

    Resolvable S(2,3,15) from S(3,4,16)
    Fisher's inequality
    Construction of the projective plane S(2,5,21)
        from K6 and its P- and Q-classes
    Remarks on a contruction of the small Witt design S(5,6,12) 

     A construction of S(3,q+1,qn) 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, derangements as example
   Counting k-covers
       (An application in 'exact exponential algorithms')
       The Fast-Zeta transform
 

   Lemma of Lindström Gessel-Viennot
        Applications
        Evaluating determinants
        Counting monotone polyominos
        The formula of Cauchy-Binet
   Some remarks on permanents     

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

     The Aztex diamond theorem
        Schröder numbers and small Schröder numbers
        Recursion for tilings via LGV
     Domino tilings of the grid and rhombic tilings
     Perfect matchings, permanents and Kasteleyn signature