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