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