Instructors: Sergi Elizalde
Course on canvas.dartmouth.edu.⇗
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 Z^{d} |
Day 28 -Nov 13: |
Amir's presentation: A combinatorial proof of the Lagrange inversion formula Shikhin's presentation: The RSK correspondence |