Instructor: Sergi Elizalde
Course on Canvas: https://canvas.dartmouth.edu/courses/50115/ ⇗
Syllabus
Permutations [EC Ch 1, Bo Ch 1-3, St, Sag] How to count [EC 1.1, see also What is an answer? (Links to an external site.) and Enumerative and algebraic combinatorics (Links to an external site.)] Cycles, left-to-right maxima, inversions [EC 1.3, Sag 1.5] Descents, Eulerian numbers, major index, excedances [EC 1.4] Geometric representations of permutations, increasing trees [EC 1.5] Alternating permutations, Euler numbers [EC 1.6, St] Permutations of multisets, q-binomial coefficients [EC 1.7] Partitions and tableaux [EC, BS 2-9, AE, An, Br, St, Notes] Generating functions for partitions [EC 1.8, BS2, Sag 1.6, 3.5] Euler's pentagonal number theorem [EC 1.8, Pak 5] Jacobi's triple product identity [Pak 6] Rogers-Ramanujan identities [Pak 7] Refinements of Euler's identity: Fine's refinement, lecture hall partitions [AE 9] Asymptotic behavior of the partition function [Pak 9.6] Standard Young tableaux, the Hook-length formula [BS 4, Sag 7.3] The Robinson-Schensted-Knuth (RSK) algorithm [EC 7.11, 7.13, Bo 7.1, Sag 7.5] Increasing and decreasing subsequences [BS 6, St] Plane partitions, MacMahon's theorem [BS 3] Domino tilings of rectangles and Aztec diamonds, connections of tilings to plane partitions [BS 8,9] Lattice paths Determinants, the Gessel-Viennot formula [EC 2.7, Sag 2.5] This is a more accurate description of the topics covered each day so far, with links to lecture notes: Day 1 (1/5): Introductions, syllabus, etc. How to count, possible answers to an enumeration question. Notes: How to count Download How to count. Day 2 (1/7): More generating functions. Cycles in permutations, standard representation, Foata's fundamental transformation, permutations with given cycle type, cycle indicator. Notes: Cycles Download Cycles. Day 3 (1/10): Expected number of k-cycles, a recurrence and generating function for Stirling numbers of the first kind. Inversions, inversion table, q-analogue of n!. Notes: Inversions Download Inversions. Day 4 (1/12): Descents, Eulerian polynomials, a recurrence for Eulerian numbers, excedances, weak excedances. Notes: Descents Download Descents. Day 5 (1/14): Generating functions for Eulerian polynomials, major index, bijective proof of the equidistribution of inv and maj. Notes: same pdf from Day 4. No class 1/17: MLK holiday. Class moved to x-hour on 1/20. Day 6 (1/19): Symmetry of the joint distribution of inv and maj. Geometric representations of permutations, increasing binary trees, double ascents and descents, peaks, valleys. Notes: Geometric representations of permutations Download Geometric representations of permutations. Day 7 (1/20 X-hour): Alternating permutations, Euler numbers, combinatorial proofs of trigonometric identities. Notes: Alternating permutations Download Alternating permutations. Day 8 (1/21): Unordered increasing binary trees, the cd-index. Permutations of multisets, q-binomial and q-multinomial coefficients, inversion number. Notes: Permutations of multisets Download Permutations of multisets. Day 9 (1/24): Recurrence for q-binomial coefficients, interpretation in terms of inversions of multiset permutations, k-dimensional subspaces of vector spaces over a finite field, introduction to partitions. Notes: same pdf from Day 8. Day 10 (1/26): Recurrence for partitions with a given number of parts, interpretation of q-binomial coefficients as counting partitions inside a rectangle, generating function for partitions into at most k parts. Notes: Bounded partitions Download Bounded partitions. Day 11 (1/28): Generating functions for partitions with parts from a given set and/or with distinct parts, bijection between self-conjugate partitions and partitions into odd distinct parts, bijection between partitions into odd parts and partitions into distinct parts (Euler's partition identity). Notes: Partition identities Download Partition identities. Day 12 (1/31): Sylvester's proof of Euler's partition identity, multivariate generating functions for partitions, identities of the form product equals sum. Notes: same pdf from Day 11. Day 13 (2/2): Euler's pentagonal number theorem, Franklin's combinatorial proof, a recurrence for the partition numbers, an application to bound the probability that a matrix over a finite field is non-singular. Notes: Euler's pentagonal number theorem Download Euler's pentagonal number theorem. Day 14 (2/4): Jacobi triple product identity, bijective proof. Introduction to the Rogers-Ramanujan identities. Notes: Jacobi triple product identity Download Jacobi triple product identity. Day 15 (2/7): Proof of the first Rogers-Ramanujan identity using the Jacobi triple product identity and Schur's involution. Notes: Rogers-Ramanujan identities Download Rogers-Ramanujan identities. Day 16 (2/9): Second Rogers-Ramanujan identity, Ramanujan congruences and Dyson's rank, Fine's refinement of Euler's identity. Notes: Fine's refinement Download Fine's refinement. Day 17 (2/11): Lecture hall partitions, connection to partitions into odd bounded parts. Asymptotic behavior of the partition number, upper and lower bounds. Notes: Lecture hall partitions Download Lecture hall partitions. Asymptotic behavior of p(n) Download Asymptotic behavior of p(n). Day 18 (2/14): Upper bound on the partition number. Standard Young tableaux, the Hook length formula, the Robinson-Schensted-Knuth correspondence. Notes: Standard Young tableaux Download Standard Young tableaux. Day 19 (2/16): Extending the RSK correspondence to generalized permutations and semistandard Young tableaux, properties of RSK, increasing and decreasing subsequences, the Erdös-Szekeres theorem. Notes: The RSK correspondence Download The RSK correspondence. Increasing and decreasing subsequences Download Increasing and decreasing subsequences. Day 20 (2/18): Plane partitions, bijective proof of MacMachon's formula using RSK. Notes: Plane partitions Download Plane partitions. Day 21 (2/21): Enumeration of plane partitions by restricting the number of rows, the number of columns, and/or the value of the entries; symmetries in plane partitions. Domino tilings of a rectangle. Notes: Tilings Download Tilings. Day 22 (2/23): Domino tilings of the Aztec diamond, Elkies-Kuperberg-Larsen-Propp proof by domino shuffling, the arctic circle theorem, rhombic tilings of a hexagon, bijection to plane partitions inside a box. Notes: More on tilings Download More on tilings. Day 23 (2/25): Kathy and Melanie: Unimodality of the Eulerian polynomials. Day 24 (2/28): Alex and Ben A.: The alternating sign matrix conjecture. Day 25 (3/2): Ben L.: Min-max trees and the cd-index. Matt: Viennot's geometric construction and the symmetry of RSK. Day 26 (3/4): Jay and Peter: A combinatorial proof of the Rogers-Ramanujan identities. Day 27 (3/7): Dylan: The Edelman-Greene correspondence. Nonintersecting paths, the Lindström-Gessel-Viennot determinant. Notes: Nonintersecting lattice paths Download Nonintersecting lattice paths.