Combinatorics Lecture Notes

Constructions for combinatorial classes......Page 7
A combinatorial example: semi-directed self-avoiding paths......Page 9
Complements on rational functions......Page 10
Binary trees, a bad (but instructive) method......Page 11
Lukaciewicz words and the cycle lemma......Page 13
The Lagrange Inversion formula......Page 17
Complement: some general facts on algebraic series......Page 20
Preliminary: the inclusion-exclusion formula......Page 23
The chromatic polynomial......Page 24
The Tutte polynomial......Page 25
Euler tours and the BEST theorem......Page 27
The matrix-tree theorem......Page 29
Illustration: The de Bruijn graph......Page 33
Introduction: intervals in the Stanley lattice and the reflection principle......Page 35
The Lindström-Gessel-Viennot lemma......Page 37
Non intersecting Catalan paths, a.k.a. watermelons......Page 39
Plane Partitions in a box and MacMahon's formula......Page 41
The figure I handed out in class: plane partitions, hexagons, paths systems......Page 45
The amazing power of two......Page 47
Schröder paths......Page 48
Matchings......Page 54
Polygon gluings and the genus of a matching......Page 55
The Harer-Zagier formula......Page 57
Proof of Theorem 57, according to Bernardi (2010)......Page 58
Viennot's theory of heaps (2011)......Page 61
Integer partitions......Page 63
Plane partitions and MacMahon's formula......Page 64
A vector space, and two operators......Page 66
The commutation relation......Page 67
Another bijective proof of (5.7), with pictures......Page 68
End of the proof of MacMahon's formula......Page 70