# Combinatorics

### Sommer Term 2011 Stefan Felsner

Vorlesungsdetails: 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 , 10 , 11 , 12 , 13 , 14 , 15 , 16 , 17 , 18 , 19 , 20 , 21 , 22 , 23 , 24

1. lecture, 11.4.2011

```   What is Combinatorics
What does it mean to count?
Aspects of counting derangements (fixed point free permutations) P.R.de Montmort
sequence A000166 in OEIS
recurrence - summation - asymptotics - generating function
```
2. lecture, 11.4.2011
```     Orthogonal Latin Squares
(Euler's 36 officers problem)
Orthogonal Latin squares from groups
MOLS (mutually orthogonal Latin squares)
There are at most N-1 MOLS of order N
MOLS and projective planes
```
3. lecture, 18.4.2011
```   Basic Counting
Basic rules for counting
Binomial coefficients
Models and identities
Extending binomial coefficients
(positive integer -> integer -> complex -> polynomial)
The binomial theorem
Fibonacci numbers
Basic models
```
4. lecture, 18.4.2011
```      Identities
Number system (Zeckendorf)
Binet's formula via generating function
via linear algebra
Continued fractions and continuants
```
5. lecture, 2.5.2011
```      The twelvefold way
Partitions of a set
Stirling numbers of 2nd kind
Partitions on an integer
Generating function of partitions
Distinct and odd are equinumerous
```
6. lecture, 2.5.2011
```        Euler's Pentagonal Number Theorem
Formal power series
Basic operations
Bernoulli numbers and sums
```
7. lecture, 9.5.2011
```        Composition of FPS
Catalan numbers and their generating function
Solving linear recurrences
The general approach
```
8. lecture, 9.5.2011
```        Spanning trees of Gn
Exponential generation function for Fibonacci numbers
q-Enumeration
Permutations and inversions
Mac Mahon's maj-index and the equidistribution theorem
```
9. lecture, 16.5.2011
```        01-words and inversions
A q-binomial theorem
Subspaces of q-vectorspaces
A second q-binomial theorem
```
10. lecture, 16.5.2011
```   Finite sets and posets
Intersecting families of subsets
Posets and lattices
Substructures in posets and lattices
Sperner's Theorem - LYM inequality
Small maximal k-intersecting families
```
11. lecture, 23.5.2011
```        Shadows
Sperner's Theorem again
Kruskal-Katona Theorem
```
12. lecture, 23.5.2011
```        Symmetric chains
Symmetric chain decompositions for multisets
Symmetric chain decomp. and pairing brackets
An application to Dedekind's problem
```
13. lecture, 30.5.2011
```
Duality theorems
Dilworth's Theorem
König-Egervary matching theorem
The Marriage Theorem (Hall condition)
A quantified Marriage Theorem
On the number of Latin squares
```
14. lecture, 30.5.2011
```
The matching polytope of a bipartite graph
LP relaxation for max matching
Polyhedra, polytopes and their vertices
The TDI property of the incidence matrix
LP-duality and the König-Egervary theorem
```
15. lecture, 6.6.2011
```    Polya Theorie: Counting with symmetries
Necklaces and colored cubes - two introductory examples
Permutation groups and the cycle index
The Lemma of Cauchy-Frobenius-Burnside
```
16. lecture, 6.6.2011
```      Polya's first theorem: counting orbits of RD
Weights on R and the induced weight on RD
Polya's fundamental theorem:
```
17. lecture, 20.6.2011
```      Linear extensions
generic algorithm
dimension of posets
Boolean lattices and standard examples
bounds for dimension
characterizations of 2-dimensional posets
```
18. lecture, 20.6.2011
```     Algorithms for chain- and antichain partitions
the 2-dimensional case
Young-Tableaux and the Robinson-Shensted correspondence
bumping
Viennot's proof via skeletons
Connections to the Greene-Kleitman theory
```
19. lecture, 27.6.2011
```   Design Theory
Sλ(t,k,v) designs
Some examples and constructions
Arithmetic conditions
Kirkman's problem
```
20. lecture, 27.6.2011
```     Resolvable designs
Solutions to Kirkman's problem
Projective planes as designs
A construction of the plane S(2,5,21) from K6
Fisher's inequality
```
21. lecture, 4.7.2011
```       Möbius inversion
Incidence algebra of a poset
Zeta function and  Möbius function
Möbius function of chains and products
Applications
```
22. lecture, 4.7.2011
```       Involutions
Vandermonde determinant and tournaments
Lemma of Lindström, Gessel-Viennot
```
23. lecture, 11.7.2011
```       Catalan numbers
Ten Catalan families
some bijections
Determining the numbers
path reflection
```
24. lecture, 11.7.2011
```            cycle lemma
Narayana numbers via LGV Lemma
Further directions
two lattices on Catalan families
rotations and flips
the associahedron
```

Back to the course page.