# Combinatorics

### Sommer Term 2017 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 , 28

1. lecture, 18.4.2017

```   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, 18.4.2017
```     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
MOLS and projective planes
```
3. lecture, 26.4.2017
```   Basic Counting
Basic rules for counting
Binomial coefficients
Models and identities
Extending binomial coefficients
Extending binomial identities to polynomial identities
The binomial theorem
```
4. lecture, 26.4.2017
```   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
```
5. lecture, 2.5.2017
```  The twelvefold way
Partitions of a set
Stirling numbers of 2nd kind
Stirling inversion
Partitions on an integer

```
6. lecture, 2.5.2017
```        Generating function of partitions
Distinct and odd are equinumerous
Euler's Pentagonal Number Theorem
```
7. lecture, 9.5.2017
```   Fibonacci numbers
Basic models
Identities
Number system (Zeckendorf)
Binet's formula via generating function
```
8. lecture, 9.5.2017
```  Solving linear recurrences
The general approach (partial fraction decomposition)
The matrix approach (companion matrix)
Exponential generation function for Fibonacci numbers
```
9. lecture, 16.5.2017
```  Formal power series
Basic operations
Bernoulli numbers and sums
Composition of FPS
```
10. lecture, 16.5.2017
```
The symbolic method
Catalan numbers and their generating function
q-Enumeration
Permutations and inversions
Mac Mahon's maj-index and the equidistribution theorem
```
11. lecture, 23.5.2017
```       Eulerian numbers
Equidistribution of des and exc
Worpitzky's identity
q-binomial coefficients
```
12. lecture, 23.5.2017
```         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
```
13. lecture, 30.5.2017
```     Posets and lattices
Sperner's Theorem - LYM inequality

```
14. lecture, 30.5.2017
```    Small maximal k-intersecting families
Shadows and a second proof of Sperner's
The Kruskal-Katona Theorem

```
15. lecture, 6.6.2017
```
The Lovasz version of Kruskal-Katona
Symmetric chain decompositins
```
16. lecture, 6.6.2017
```   Symmetric chain decompositins
Symmetric chain decompositions for multisets
Symmetric chain decomp. and pairing brackets
An application to Dedekind's problem
```
17. lecture, 13.6.2017
```    Duality theorems
Dilworth's Theorem
König-Egervary matching theorem
Equivalence with Dilworth's
Hall's Theorem (Marriage Theorem)
Applications
```
18. lecture, 13.6.2017
```    Linear extensions
generic algorithm
dimension of posets
Boolean lattices and standard examples
bounds for dimension
characterizations of 2-dimensional posets
```
19. lecture, 20.6.2017
```   Polya Theorie: Counting with symmetries
Necklaces and colored cubes - two introductory examples
Permutation groups and the cycle index
The Lemma of Cauchy-Frobenius-Burnside
```
20. lecture, 20.6.2017
```      Applications of the lemma, e.g. Stirling numbers of 2nd kind
Polya's first theorem: counting orbits of RD
Weights on R and the induced weight on RD
Polya's second theorem: counting orbits with weights
```
21. lecture, 27.6.2017
```   Design Theory
Sλ(t,k,v) designs
Some examples and constructions
Arithmetic conditions
```
22. lecture, 27.6.2017
```     Fisher's inequality
Kirkman's problem
Resolvable designs
Solutions to Kirkman's problem
3-Designs from PGL(2,q)
```
23. lecture, 4.7.2017
```   Möbius inversion
Incidence algebra of a poset
Zeta function and  Möbius function
Möbius function of chains and products
Applications
```
24. lecture, 4.7.2017
```  Lemma of Lindström, Gessel-Viennot
Applications
Evaluating determinants
The Binet-Cauchy formula
Counting disjoint path systems
```
25. lecture, 11.7.2017
```  Permanents, Determinants and Matchings
Derangements and a determinant
Derangements and a permanent
The permanent
Basic facts
The number of perfect matchings of 3-regular bip. graphs
```
26. lecture, 11.7.2017
```      Using determinants to evaluate permanents
Determinants to count matchings of planar bipartite graphs
Matchings and some tiling problems
```
27. lecture, 18.7.2017
```  Catalan numbers
Ten Catalan families
some bijections
Determining the numbers
cycle lemma
path reflection
```
28. lecture, 18.7.2017
```           symmetric chain decompositions
Narayana numbers via LGV Lemma
Orders on Catalan families
Associahedron and flips
```

Back to the course page.