Course Syllabus

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
Enumeration under group action.
Counting orbits using the Burnside Lemma. Polya's theorem.
[St] Chapter 7 [Aig] Sections 6.1-6.3
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


This is a more accurate description of the topics covered each day so far:

Day 1: Lattice paths, Dyck paths, the reflection principle, rotated paths, recurrences
Day 2: Binomial coefficients, multisets, compositions, partitions
Day 3: More partitions, set partitions, Stirling numbers, cycles in permutations
Day 4: Permutation statistics: cycles, records, descents, inversions
Day 5: Inversion table, major index, fixed points, derangements; inclusion-exclusion
Day 6: More 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, partitions, plane trees
Day 11: Binary trees, set partitions; the symbolic method for labeled structures
Day 12: The labeled product, sequences and sets of labeled classes; labeled rooted trees, set partitions
Day 13: Cycles of labeled classes; surjective maps, labeled graphs, permutations, involutions; multivariate generating functions
Day 14: The Lagrange inversion formula, Cayley's formula and Prufer code
Day 15: Group actions, orbits, equivalent colorings
Day 16: [Justin] Enumeration under group action
Day 17: [Justin] Enumeration under group action
Day 18: [Justin] Enumeration under group action
Day 19: Applications of Polya's theorem: necklaces, dihedral necklaces, Stirling numbers
Day 20: Partially ordered sets, graded posets, chains, antichains
Day 21: Sperner's theorem, order matchings using linear algebra
Day 22: Finishing the algebraic proof of Sperner's theorem; Lubell's proof
Day 23 -Nov 1:

Juan's presentation: A general partition theorem.
Young's lattice, standard young tableaux

Day 24 -Nov 3:

Avery and Sophie's presentation: Walks in graphs.
The hook-length formula

Day 25 -Nov 6:

Lizzie's presentation: The inversion number and the major index.
Linear operators and walks in Young's lattice

Day 26 -Nov 8:
Sara and Emma's presentation: Two proofs of the hook-length formula
Day 27 -Nov 10: Doug and Zach's presentation: Random walks in Zd
Day 28 -Nov 13:

Amir's presentation: A combinatorial proof of the Lagrange inversion formula

Shikhin's presentation: The RSK correspondence


Course Summary:

Date Details