Instructor: Alexander Postnikov
(office hours: Wed 12 - 1 pm, or by appointment, Room 2-367)
TA: Elisabeth Bullock
(office hours: Fri 11 am - 12 pm, Room 2-332A)
When: Monday, Wednesday, Friday 1:00-2:00 pm
Where:
Room 4-237
Canvas:
https://canvas.mit.edu/courses/36003
Canvas will be used for submitting problem sets, grading, and
course annoncements.
Description:
Applications of algebra to combinatorics and vise versa.
We will discuss enumeration methods, permutations, partitions,
partially ordered sets and lattices, Young tableaux,
graph theory, matrix tree theorem, electrical networks,
random walks, convex polytopes, and other topics.
Course Level: Advanced Undergraduate.
Topics:
Catalan numbers, Dyck paths, triangulations, non-crossing set partitions,
symmetric group, statistics on permutations, inversions and major index,
partially ordered sets and lattices, Sperner's and Dilworth's theorems,
Young diagrams, Young's lattice, Gaussian q-binomial coefficients,
standard Young tableaux (STY),
Robinson-Schensted-Knuth (RSK) correspondence,
partitions, Euler's pentagonal theorem, Jacobi triple product,
non-crossing paths, Lindstrom-Gessel-Viennot lemma,
spanning trees, parking functions, Prufer codes,
matrix-tree theorem, electrical networks, random walks on graphs,
graph colorings, chromatic polynomial,
transportation and Birkhoff polytopes, cyclic polytopes, permutohedra,
domino tilings, matching enumeration, also (if time allows)
Mobius function, continued fractions,
enumeration under group action,
Burnside's lemma, Polya theory,
Pfaffians, Ising model, etc.
Grading:
Several problems sets and in-class exams.
Each problem set will be graded out of 80 points and each exam will be out
of 50 points. The total score will be the sum of all points.
Bonus points: in-class presentations, posting your lecture notes.
Problem Sets:
- Problem Set 1 (due Friday, March 6)
- Problem Set 2 (approximate release and due dates: April 6, April 17)
- Problem Set 3 (approximate release and due dates: April 24, May 8)
Exams:
Two in-class midterm exams on March 13 and May 1.
(No final exam.)
Lecture Notes:
Notes from past years:
Lectures:
-
Mon, Feb 2. Catalan numbers: Dyck paths, recurrence relation,
generating function.
-
Wed, Feb 4. Catalan numbers (cont'd): generalized binomial
coefficients, reflection method, cyclic shifts.
- Fri, Feb 6.
Catalan numbers (cont'd):
valid parenthesizations, binary trees, triangulations, non-crossing
matchings, non-crossing partitions. Bijective proofs.
- Mon, Feb 9.
Stack-sortable and queue-sortable permutations.
Pattern avoidance in permutations.
Standard Young Tableaux (SYT's). Dyck paths as SYT's of shape (n,n).
Frame-Robinson-Thrall's Hook Length Formula for the number of SYT's.
- Wed, Feb 11. A probabilistic ``Hook Walk'' proof of the Hook Length
Formula.
- Fri, Feb 13. Finish of the Hook Walk proof.
Longest increasing and descreasing subsequences in permutations.
Robinson-Schensted-(Knuth) correspondence (RSK).
Schensted's insertion algorithm.
- Tue, Feb 17. RSK (cont'd).
Properties of RSK. Schensted shape of a permutation.
Greene's theorem.
- Wed, Feb 18.
The Eulerian numbers A(n,k).
Euler's computation of nfinite power series.
Combinatorial interpretations of the Eulerian numbers in terms
of descents. The Eulerian triangle.
-
Fri, Feb 20.
The Narayana numbers N(n,k).
Peaks in Dyck paths.
The Narayna triangle.
Right and left edges in plane binary trees.
The Eulerian numbers in terms of increasing binary trees.
A bijection between permutations and increasing binary trees.
-
Wed, Feb 25. The symmetric group S_n. Statistics on permutations:
inv, des, cyc, maj, exc, rec. Equidistributed statistics.
-
Fri, Feb 27.
Sperner's theorem. Partially ordered sets (posets).
Chains and antichains in posets.
Symmetric chain decompositions (SCD's). Products of posets.
- Mon, Mar 2. Proofs of Sperner's and de Bruijn's theorems
in terms of symmetric chain decompositions.
Dilworth's, Mirsky's, and Greene's theorems.
- Wed, Mar 4. q-analogs: q-factorials and Gaussian q-binomial coefficients.
q-Pascal's triangle.
- Fri, Mar 6. q-analogs (cont'd):
Grassmannians over finite fields.
Counting points in the Grassmannian using Gaussian elimintation.
- Mon, Mar 9. Theory of partitions. The partition function p(n).
The generating function for p(n). Euler's theorem about partitions with distinct parts and partitions with odd parts. Euler's recurrence for p(n).
The pentagonal numbers.
-
Wed, Mar 11. Discussion of the problem set.
-
Fri, Mar 13. Exam 1. (The exam will in the usual class room.)
Additional reading:
Many (but not all) topics that we dicuss in class can be found in these books.
The students are not required to buy these books. However, it is good
idea to take a look at them.
[AC]
Algebraic Combinatorics: Walks, Trees, Tableaux, and More
by R. P. Stanley, Springer.
Book info
from Richard Stanley's webpage,
including Text of
version of 2013.
[EC1]
Enumerative Combinatorics Vol 1 by R. P. Stanley,
Cambridge University Press.
Book info
from Richard Stanley's webpage.
|
Last updated: March 11, 2026 |