Table of Contents

Combinatorics

Sommer Term 2021
Stefan Felsner

1. lecture, 13.04.2021
Youtube youtu.be/605TY__RJ_0

   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 numbers of 2nd 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

   Fibonacci numbers
       Binet's formula via generating function
                      via linear algebra
  Solving linear recurrences
      The general approach (partial fraction decomposition)
      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

  
       Eulerian numbers 
       Worpitzky's identity
       q-binomial coefficients
       01-words and inversions
       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
   Orthogonal chain decompositions
      Two orthogonal chain decompositions for Bn
      A probability application of orthogonal chain decompositions

   Duality theorems
      Dilworth's Theorem       
      König-Egervary matching theorem
        Equivalence with Dilworth's
      Lemma of Erdöos-Szekeres

    Tilings
       Domino tilings - rectangles and almost rectangles
       Tilings with Vs (L-Trominos)
    Necessary conditions
        Crit 1: divisibility
        Crit 2: coloring conditions
             tilings with Ts and sticks
        Crit 3: homology criterion
             free abelian groups and reductions

             The homology group of Ls (L-tetrominoes)
             The power of homology arguments
	Aztec diamond A(k) and tilings with Zs (skew-tetrominoes)     
             coloring argument for k = 1,2 mod 4
	     no homology argument for k = 0,3 mod 4

       Crit 4: homotopy criterion     
           Proof for the homotopy criterion
           Ex: homotopy can be more powerful than homology
	   Aztec diamond tilings with Zs
               shadow paths and winding numbers
      Counting tilings
      The Aztec tiling theorem
           domino shuffling - sketch of the proof

          Schröder numbers and small Schröder numbers
	  Bijection: tilings of A(n) <-> families on n nonintersecting Schröder paths
	  systems on n nonintersecting paths, Schröder and small Schröder
	  Lemma of Lindström, Gessel-Viennot
	  The proof of the  Aztec tiling theorem
    The proof of the Lemma of Lindström, Gessel-Viennot
          Cancellation of intersecting paths systems via involution 

          Cauchy-Binet formula from the LGV Lemma
   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
     Sλ(t,k,v) designs
     Some examples and constructions 
     Arithmetic conditions
     Fisher's inequality
 

     Kirkman's problem and a solution
     Steiner triple systems with v = 3 mod 6
     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
  Catalan numbers
      5 Catalan families
      Another 5 Catalan families
        some bijections
 

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

       The Tamari lattice
       Rotation distance of binary trees,
           simplicial decompositions and ideal tetrahedra
       Fiber polytopes and the Associahedron
       The Maule lattice of a cloud
           three examples