# Combinatorics

### 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
Derangements
Aspects of counting derangements (fixed point free permutations) P.R.de 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
Distinct and odd are equinumerous
```
6. lecture, 29.04.2021
```        Euler's Pentagonal Number Theorem
Fibonacci numbers
Identities
```
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
```  q-Enumeration
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
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
```
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
```    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
```
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
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