18.212 Algebraic Combinatorics

Spring 2026
Professor: Alexander Postnikov (apost@math.mit.edu)
Course website: https://math.mit.edu/~apost/18.212/
(Optional) Readings:

Richard Stanley Algebraic Combinatorics: Walks, Trees, Tableaux, and More
Richard Stanley Enumerative Combinatorics

These are notes taken for the spring 2026 iteration of 18.212 Algebraic Combinatorics by Angeline Peng. I use a nonlinear notetaking system called Zettelkasten. In short, it is Wikipedia-style.

Note! I am publishing a subset of my Zettelkasten, and so I might publish some Zettels that I have already made, which might contain information that we did not cover in the course. I will leave a note on this page (note there will not be a note on the Zettel itself) if this happens.

I try to update by the end of the day after lecture. If you notice any issues (both display-wise and content-wise) please email me pengs14@mit.edu and I will try to fix it. Most of the time, it will be a LaTeX rendering issue because my local is a little bit different than the deployed.

There a couple ways to navigate:

Below you'll see the list of items that we went over for each day. You can click on the topics to go to the page.
- I probably wouldn't recommend reading my notes if you missed a lecture. They are nonlinear, and better used for reference, for review, etc. There are other, more traditional, notes posted on the course site.
You can search with the search bar on the left or use ctrl/cmd + k
There is a list of all the notes on the left that you can click on

4/3

Prufer's coding proof for Cayley's formula
another bijective proof with functions

4/1

Counting labelled trees. More precisely, stated and gave an inductive proof of Cayley's formula
- corollary: number of labellings on a tree with given degrees

3/30

Recall definition of differential poset
Gave a combinatorial interpretation of Fibonacci's lattice with compositions of $n$ by parts of 1 or 2
walks on differential posets
- Stated the correspondence between paths on differential posets and rooks

3/20

Recall that as a corollary of RSK, we showed that $\sum_{λ ⊢ n} (f_{λ})^{2} = n!$ (here). Today, we shall give some more intuitive proofs of this.
Defined Young's lattice for all Young diagrams
- Used this to prove the above fact
differential posets as a generalization of posets that satisfy the same types of properties as Young's lattice
- Gave Fibonacci's lattice as an example

3/18

Proved Jacobi's triple product formula
This technique of cutting and pasting can be used in other combinatorial problems to establish a bijection between pairs of partitions and one partition. For example, distinct parts and partitions with less than k parts

3/16

Finished proving Euler's pentagonal number theorem by using Franklin's bijective proof (1881)
A related result, due to Gauss:

\prod_{n \geq 1} (1 - x^{n})^{3} = \sum_{k \in Z} (- 1)^{k} k x^{k (k + 1) / 2}

We may reasonably wonder if there is a nice formula for $\prod_{n \geq 1} (1 - x^{n})^{r}$ for any fixed $r$ . The answer for $r = 2$ is already really messy.
Another formula by Gauss:

\prod_{n \geq 1} \frac{1 - x^{n}}{1 + x^{n}} = \sum_{k \in Z} (- 1)^{k} x^{k^{2}}

The two formulas above are specializations of Jacobi's triple product formula, which we might state later

3/11

Presented solutions to homework problems:
- number of permutations that are stack-sortable is catalan by Veronica, proved by showing that stack-sortable if and only if 231-avoidant
- Knuth's hook length formula for trees by Luna, proved by showing recurrence relation by splitting to the left and right subtree
- the first column of Schensted shape is the length of longest decreasing by Elena, proved by the lemma that column insertion commutes with row insertion. This lemma shows that the Schensted shape of $w$ reversed is the transpose of the Schensted shape of $w$ .
- exceedance is equidistributed to weak exceedance + 1 by Aprameya, proved by showing that you can map $w$ to $w_{i} - 1$ for each $i$ (mapping $1 \mapsto n$ ). The number of weak exceedances of this + 1 is the exceedance of $w$
- bijection between size k subsets and n-k subsets by Zack, proved by taking each element of a set (of the set with the smaller size) and mapping successively each element to the smallest number that is not in the set (and previously mapped by another element), then taking the complement of that.
Worked on proving Euler's pentagonal number theorem

3/9

Clarified limit in this proof
Theory of partitions!

3/6

Gave second proof for q-binomial coefficients are generating functions for size of bounded young diagrams
- As a corollary, this gives us a formula for the generating function for size of young diagrams
Introduced Young's lattice

3/4

q-analogs:

3/2

Gave proof of product of chains has a SCD to prove Sperner's theorem
Some related results:
- Dilworth's theorem
- Mirsky's theorem
- Greene's theorem (posets)
  - Exercise: Some part of the proof of this will be on the next pset
associated poset to a permutation, lambda(P(w)) is schensted shape
lattice of order ideals (as a teaser for what we're going to talk about later)

2/27

Presented Sperner's theorem and this related problem. Before we prove it, we have to develop some theory:
Defined:
- partially ordered set (poset)
- covering relation
- Hasse diagram
- chain, saturated chain, antichain
- Boolean lattice which we can use to reformulate Sperner's into something we shall prove.
- ranked poset, rank numbers, rank symmetric poset, rank unimodal poset, Sperner poset
- symmetric chain decomposition
- product of posets - ignore the categorical nonsense
DeBruijn's theorem and gave proof sketch.
- Note that this is a generalization of Sperners and so implies Sperners.

2/25

Talked a little about notations for permutations
Defined a statistic on permutations
- In particular, we care about the equivalence class of statistics modulo equidistributed
Three main classes of statistics:
Exercise: number of weak exceedance - 1 is equidistributed to exceedances.

2/20

Narayana numbers and Narayana triangle
- Exercise: Show that the Narayana numbers are symmetric with the combinatorial definition
plane binary tree and proved number of plane binary trees with n vertices is Catalan
- Exercise: Show that $N (n, k)$ is the number of plane binary trees with $n$ vertices and $k - 1$ left edges combinatorially
increasing binary tree and proved number of increasing binary trees with n vertices and k left edges is Eulerian numbers
Knuth's hook length formula for trees
- Exercise: prove this

2/18

Eulerian polynomial, the numerator of the infinite sum $1^{n} + 2^{n} x + 3^{n} x^{2} + 4^{n} x^{3} + \dots$
We can put the coefficient of this polynomial into a triangle, called the Eulerian triangle. Examining this, we notice a certain property about the row sums.
We defined the Eulerian numbers combinatorially to explain the row sum being $n!$ , and we showed that the Eulerian numbers are coefficients of Eulerian polynomial

2/17

Finished the Robinson-Schensted-Knud (RSK) correspondence
Defined the Schensted shape of a permutation
Proved this property of Schensted shape
Stated Greene's theorem

2/13

Finished proof of hook length formula
Introduced the Robinson-Schensted-Knud (RSK) correspondence (we're actually doing a more specific instance of this, due to just Robinson-Schensted).

2/11

Worked on the proof of the hook length formula
We shall use the notation $[k] = {1, 2, \dots, k}$

2/9

Quick recap / addition to stack-sortable permutations
Introduce k-queue sortable and stated that the number of permutations that are 2-queue sortable is catalan
pattern avoidance - certain permutations can be characterized by pattern avoidance
- For example, stack-sortable iff 2, 3, 1 avoidant
- and, k-queue sortable iff it is k, k-1, ..., 1-avoidant.
The number of 3-permutation-avoiding permutations is catalan
Standard Young Tableauxs!
- partition - there is some content from my other notes. We only covered the definition (and we assumed that there are finitely many parts) and what it means to be a partition of n
  - Ex: 3 has the partitions $(3), (2, 1), (1, 1, 1)$
- Young diagram
- Young tableau(x) - ignore Young symmetrizer
- We asked about the number of standard Young tableauxs of shape $λ$ (which we denote by $f_{λ}$ )
  - $f_{(n)} = 1$ and by similar logic $f_{(1^{n})} = 1$
    - personal aside: notice that $f_{λ} = f_{λ^{'}}$ where $λ^{'}$ is the conjugate partition - not covered in class
  - $f_{(2, 1)} = 2$
  - $f_{(2, 2)} = 2$
  - $f_{(3, 2)} = 5$ - one way you can see this is by splitting it into two cases: if you fill the first column with 1 and 2 and then notice the right side is $f_{(2, 1)}$ ; or if you fill 1, 2 in the first row. Then, the last box in the first row can be one of 3,4,5.
  - $f_{(3, 3)} = 5$ since the last box (that is not there in $(3, 2)$ ) must be filled with the last number.
- the number of SYTs of shape (n, n) is catalan
- hook length formula and hook length - I include a formalization of the hook length with the conjugate partition that we do not use, see the less formal definition.

2/6

Some more interpretation of the Catalan numbers (all of these are just proof sketches. Rigorization is left as an exercise.)
- number of valid parenthesization of n+1 letters is catalan
- number of complete binary trees with n+1 leaves is catalan
  - Exercise: the number of nonleaves + 1 is equal to the number of leaves
- number of triangulations of a convex (n+2)-gon is catalan
- number of non-cross perfect matchings with 2n vertices is catalan
- number of non-crossing partitions with n vertices is catalan
- number of permutations that are stack-sortable is catalan

2/4

Finished generating functions proof
Did a more combinatorial proof: reflection method
And one more "even more" combinatorial proof: cyclic shifts

2/2

Algebraic combinatorics involves the interplay of algebra and combinatorics. We will often use one to solve problems in the other and vice versa.
There are two main types of combinatorics:
- Richard Stanley did something called enumerative combinatorics, basically counting things
- Paul Erdos worked more with asymptotics and bounding
Introduced Catalan numbers and Dyck path as an interpretation
Worked on proving with generating functions