Table of Contents


Sommer Term 2021
Stefan Felsner

Content of individual lectures: 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 , 10 , 11 , 12 , 13 , 14 , 15 , 16 , 17 , 18 , 19 , 20 , 21 , 22 , 23 , 24 25 , 26 , 27 ,

1. lecture, 13.04.2021

   What is Combinatorics - introductory examples
       Aspects of counting derangements (fixed point free permutations) Montmort
       sequence A000166 in OEIS
       recurrence - summation - asymptotics - generating function  
2. lecture, 15.04.2021
     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
3. lecture, 20.04.2021
   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
4. lecture, 22.04.2021
The quality of the recording is terrible - I didn't pin speakers view - sorry.
Here are my notes for the lecture [Lecture-4-notes.pdf]
        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
5. lecture, 27.04.2021
        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
6. lecture, 29.04.2021
        Euler's Pentagonal Number Theorem 
   Fibonacci numbers
7. lecture, 04.05.2021
   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)		      
8. lecture, 06.05.2021
  Formal power series
      Basic operations
      Bernoulli numbers and a summation formula
      Composition of FPS
      The symbolic method
      Catalan numbers and their generating function 
9. lecture, 11.05.2021
     Permutations and inversions
     Mac Mahon's maj-index and the equidistribution theorem
     Eulerian numbers 
     Equidistribution of des and exc
10. lecture, 18.05.2021
       Eulerian numbers 
       Worpitzky's identity
       q-binomial coefficients
       01-words and inversions
       First q-binomial theorem
11. lecture, 20.05.2021
       Subspaces of q-vectorspaces
         A second q-binomial theorem   
   Finite sets and posets
      Intersecting families of subsets
      Posets and lattices
12. lecture, 25.05.2021
      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
13. lecture, 27.05.2021
    The Lovasz version of Kruskal-Katona
      Erdös-Ko-Rado from LKK
14. lecture, 01.06.2021
   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
15. lecture, 03.06.2021
   Duality theorems
      Dilworth's Theorem       
      König-Egervary matching theorem
        Equivalence with Dilworth's
      Lemma of Erdöos-Szekeres
16. lecture, 08.06.2021
       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
17. lecture, 10.06.2021
             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
18. lecture, 15.06.2021 >
       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
19. lecture, 17.06.2021
          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 
20. lecture, 22.06.2021
          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
21. lecture, 24.06.2021
      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 
22. lecture, 29.06.2021
   Design Theory
     Sλ(t,k,v) designs
     Some examples and constructions 
     Arithmetic conditions
     Fisher's inequality
23. lecture, 01.07.2021
     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
24. lecture,06.07.2021
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
25. lecture, 08.07.2021
    Counting k-covers
       (An application in 'exact exponential algorithms')
       The Fast-Zeta transform
  Catalan numbers
      5 Catalan families
      Another 5 Catalan families
        some bijections
26. lecture, 13.07.2021
     More Catalan families
        some bijections
        Determining the numbers
           cycle lemma
           reflection principle
           symmetric chain decompositions
        Narayana numbers via LGV Lemma 
27. lecture, 15.07.2021
       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

Back to the course page.