Course Syllabus

Jump to Today

Here is a tentative list of topics that will be covered, together with the corresponding references.

Main reference Other references
Basic combinatorics
Catalan numbers. Sets and multisets. Compositions. [dM] Chapter 1 [Aig] Sections 1.1-1.2
[EC1] Section 1.2
Integer and set partitions. Stirling numbers. Permutations. [dM] Chapter 3 [Aig] Sections 1.3-1.5
[vLW] Chapter 13
[EC1] Section 1.3.
Inclusion-Exclusion. [dM] Chapter 2 [Aig] Section 5.1
[EC1] Sections 2.1-2.3
[vLW] Chapter 10
Generating functions
Recurrences. Formal power series. [dM] Chapter 4 [Aig] Sections 2.1, 2.2, 3.1
[Wf] Section 2.1
[vLW] Chapter 14
The symbolic method. Unlabeled structures.
Ordinary generating functions.		 [dM] Chapter 5 [FS] Chapter 1
[Wf] Section 2.2
Labeled structures. Exponential generating functions. [dM] Chapter 6 [Aig] Section 3.3
[FS] Chapter 2
[Wf] Section 2.3
Topics in algebraic combinatorics
Partially ordered sets. Chains and antichains.
Sperner's theorem.		 [St] Chapter 4
Young tableaux. The hook-length formula. Operators on Young's lattice. [St] Chapter 8 [EC2] Section 7.11
[BS] Section 4
Young diagrams and q-binomial coefficients. [St] Chapter 6 [Aig] Section 1.6
Enumeration under group action.
Counting orbits using Burnside's Lemma. Polya's theorem.		 [St] Chapter 7 [Aig] Sections 6.1-6.3

 

Below is a more detailed description of the topics covered each day, which will be regularly updated throughout the term:

Day 1: Lattice paths, Dyck paths, the reflection principle, rotated paths, recurrences
Day 2: Binomial coefficients, multisets, compositions
Day 3: Integer partitions, set partitions, Stirling numbers of the second kind
Day 4: Permutation statistics: cycles, records, Foata's fundamental bijection
Day 5: Descents, inversions, major index, fixed points, derangements
Day 6: The Principle of Inclusion-exclusion, answers to enumeration questions, generating functions
Day 7: The ring of formal power series, operations with generating functions
Day 8: Linear recurrences and rational generating functions; a non-linear recurrence
Day 9: The symbolic method for unlabeled structures, operations on combinatorial classes
Day 10: Ordinary generating functions for words, compositions, plane trees, Dyck paths
Day 11: Ordinary generating functions for integer partitions and set partitions; the symbolic method for labeled structures
Day 12: The labeled product, sequences and sets of labeled classes; exponential generating functions for labeled rooted trees, set partitions
Day 13: Exponential generating functions for ordered set partitions, permutations, involutions, derangements, labeled graphs.
Day 14: Cycles of labeled classes, the Lagrange inversion formula, Cayley's formula and bijective proof via Prüfer code
Day 15: Partially ordered sets, graded posets, chains
Day 16: Antichains, Sperner's theorem, order matchings using linear algebra
Day 17: Finishing the algebraic proof of Sperner's theorem
Day 18: Lubell's proof of Sperner's theorem, Young's lattice, the hook-length formula
Day 19: Walks in Young's lattice, U and D operators, the RSK correspondence
Day 20: Properties of RSK, the poset of partitions with bounded largest part and bounded number of parts
Day 21: q-binomial coefficients, enumeration under group action
Day 22: Equivalent colorings, group actions
Day 23: Orbits, Burnside's lemma, applications to counting inequivalent colorings
Day 24: Polya's theorem, applications to counting necklaces, dihedral necklaces, Stirling numbers
Day 25 -Nov 6: Presentation by Ben, David and Beth Anne: Viennot’s geometric construction of the RSK correspondence.
Day 26 -Nov 8:

Presentation by Ben, David and Beth Anne: Viennot’s geometric construction of the RSK correspondence (continued).

Presentation by Mario: Random walks in Z^d.
Day 27 -Nov 10: Presentation by Amya, Paul and Zach: The transfer-matrix method.
Day 28 -Nov 13: Presentation by Amya, Paul and Zach: The transfer-matrix method (continued).

 

Course Summary:

Date Details Due