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. |
| Day 24 -Nov 3: |
Avery and Sophie's presentation: Walks in graphs. |
| Day 25 -Nov 6: |
Lizzie's presentation: The inversion number and the major index. |
| 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 | Due |
|---|---|---|