Course Syllabus

Jump to Today

Here is a tentative list of topics that will be covered, together with references (see Front Page). This page will be updated as the course progresses. 

References
Permutations [EC Ch 1, Bo Ch 1-3, St, Sag]
How to count [EC 1.1, see also What is an answer? and Enumerative and algebraic combinatorics] 
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.
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.
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.
Day 4 (1/12): Descents, Eulerian polynomials, a recurrence for Eulerian numbers, excedances, weak excedances. Notes: 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.
Day 7 (1/20 X-hour): Alternating permutations, Euler numbers, combinatorial proofs of trigonometric identities. Notes: 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.
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.
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.
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.
Day 14 (2/4): Jacobi triple product identity, bijective proof. Introduction to the Rogers-Ramanujan identities. Notes: 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.
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.
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.  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.
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. Increasing and decreasing subsequences.
Day 20 (2/18): Plane partitions, bijective proof of MacMachon's formula using RSK. Notes: 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.
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.
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.

 

Course Summary:

Date Details Due