These notes follow Kevin Purbhoo’s lecture notes for C&O 430/630 (Algebraic Enumeration), Fall 2011, based in part on course materials by I.P. Goulden and D.G. Wagner. The course develops the algebraic foundations of combinatorial enumeration: formal power series, the theory of species, signed formulae, tableaux algorithms, symmetric functions, and the representation theory of the symmetric group and the Lie algebra \(\mathfrak{sl}_2(\mathbb{C})\).

---

Chapter 1: The Algebra of Formal Power Series

Generating functions are one of the most powerful tools in combinatorics: they encode sequences of integers as coefficients of formal power series, transforming counting problems into algebraic ones. But before we can manipulate generating functions with confidence, we need to understand what kind of objects they are and what operations on them are legitimate. This chapter develops that foundation, culminating in Lagrange’s Implicit Function Theorem (LIFT) — a general tool for extracting coefficients from power series satisfying functional equations.

1.1 A First Example: Catalan Numbers

Let \(\mathcal{B}\) be the set of binary trees: rooted, ordered trees in which every vertex has up-degree 0 or 2. The weight of a binary tree \(b\) is \(\mathrm{wt}(b) = \) the number of vertices with up-degree 2. The generating function is

\[ B(x) = \sum_{b \in \mathcal{B}} x^{\mathrm{wt}(b)} = \sum_{n \geq 0} b_n x^n, \]

where \(b_n\) counts binary trees of weight \(n\). Almost every binary tree decomposes uniquely as a root plus an ordered pair of binary trees (the left and right subtrees above the root), with the single-vertex tree \(\delta\) as the base case. This gives the bijection \(\mathcal{B} \leftrightarrow \{\delta\} \sqcup \{\delta\} \times \mathcal{B} \times \mathcal{B}\), which translates to the functional equation

\[ B(x) = 1 + xB(x)^2. \]

Quadratic formula approach. Solving this quadratic and taking the branch with \([x^0]B(x) = 1\) gives

\[ B(x) = \frac{1 - \sqrt{1-4x}}{2x} = \sum_{n \geq 0} \frac{1}{n+1}\binom{2n}{n} x^n. \]

The numbers \(b_n = \frac{1}{n+1}\binom{2n}{n}\) are the celebrated Catalan numbers. They count a surprising variety of combinatorial objects, including legitimate bracketings with \(n\) pairs of brackets, weakly increasing sequences \(\lambda_1 \leq \cdots \leq \lambda_n\) with \(\lambda_i \leq i\), and rooted ordered trees with \(n+1\) vertices.

Lagrange’s theorem approach. Substituting \(B(x) = A(x) + 1\) transforms the equation to \(A(x) = x(A(x)+1)^2\), which has the form \(A(x) = x\phi(A(x))\) with \(\phi(\lambda) = (1+\lambda)^2\). Lagrange’s Implicit Function Theorem (stated precisely in §1.6) then gives

\[ [x^n]A(x) = \frac{1}{n}[\lambda^{n-1}]\phi(\lambda)^n = \frac{1}{n}[\lambda^{n-1}](1+\lambda)^{2n} = \frac{1}{n}\binom{2n}{n-1} = \frac{1}{n+1}\binom{2n}{n}, \]

recovering the Catalan numbers with considerably less computation.

One of the great advantages of LIFT over the quadratic formula is that it applies to equations that are not quadratic. For instance, if trees can have up-degree 0 or \(m\), the functional equation becomes \(C(x) = x(1+C(x))^m\), and LIFT yields \([x^n]C(x) = \frac{1}{n}\binom{mn}{n-1}\).

1.2 A Second Example: Rooted Triangulations

Our second example illustrates the quadratic method, a technique for solving functional equations involving two unknown series. A rooted near-triangulation is a connected planar graph in which every interior face has degree 3 (multiple edges allowed, no loops or cut-vertices), with one edge on the outer face designated as the root. Let \(T\) be the set of all rooted near-triangulations, with weight functions \(\mathrm{wt}_1(t) = \deg(\text{outer face})\) and \(\mathrm{wt}_2(t) = \text{number of interior faces}\).

Removing the root edge gives either two near-triangulations joined at a cut-vertex, or a single near-triangulation with the outer face degree increased by 1. This recursive decomposition yields

\[ T(x,y) = x^2 + x^{-1}y T(x,y)^2 + x^{-1}y\bigl(T(x,y) - x^2 S(y)\bigr), \]

where \(S(y)\) is the generating function for the sub-family with outer face degree 2.

The quadratic method proceeds by completing the square: the equation becomes \((2yT + y - x)^2 = D(x,y)\) for an explicitly computed \(D\). One then finds a formal power series \(\alpha(y)\) such that \(D(\alpha, y) = 0\), which forces the expression inside the square to vanish, yielding equations for both \(\alpha\) and \(S(y)\). Applying LIFT ultimately gives:

\[ [y^{2n}]S = \frac{(3n)! \cdot 2}{n!\,(2n+2)!}, \]

the number of near-triangulations in \(S\) with \(2n\) interior faces — a beautiful closed form derived through a chain of algebraic identities.

The quadratic method exemplifies a broader principle: when a generating function satisfies a polynomial equation in two unknowns, one can use the condition that the discriminant vanishes at an auxiliary series to solve the system.

1.3 The Ring of Formal Power Series

Having used formal power series freely, we now put them on solid footing. Let \(R\) be an integral domain.

Invertibility. \(A(x)\) is invertible in \(R[[x]]\) if and only if \([x^0]A(x) = a_0\) is invertible in \(R\). The formula \(A^{-1} = a_0^{-1}(1 - (1 - a_0^{-1}A(x)))^{-1}\) gives the inverse explicitly via geometric series substitution.

Composition. Define \(R[[x]]^+ = \{B \in R[[x]] : [x^0]B = 0\}\). For \(B \in R[[x]]^+\), the substitution \(A(B(x)) = \sum_{n \geq 0} a_n B(x)^n\) is well-defined: each coefficient \([x^n]A(B(x))\) involves only finitely many terms.

The injectivity is key for justifying the technique used in §1.2: if we know \(Q(g(\alpha)) = f(\alpha)\) as power series in \(\alpha\), we can recover \(Q(g(y)) = f(y)\) as an identity in \(R[[y]]\).

Differentiation. The formal derivative \(A'(x) = \sum_{n \geq 1} n a_n x^{n-1}\) satisfies the usual rules: linearity, product rule, and chain rule. These are purely formal identities, proved by explicit coefficient computation.

Metric structure. For \(A(x) \neq 0\), define \(\mathrm{val}\,A(x)\) to be the smallest \(m\) with \([x^m]A(x) \neq 0\), and \(\mathrm{val}(0) = +\infty\). The function \(\|A\|_\varepsilon = \varepsilon^{\mathrm{val}\,A}\) (for \(0 < \varepsilon < 1\)) defines a norm making \(R[[x]]\) a complete metric space — the completion of the polynomial ring \(R[x]\).

This is far stronger than the real-number analogue: there are no conditionally convergent series. Any series whose terms tend to zero in the formal metric is automatically (absolutely) convergent.

1.4 Hensel’s Lemma

The main existence theorem for solutions to functional equations is Hensel’s Lemma, the formal analogue of the implicit function theorem in calculus.

The proof constructs \(f\) as the limit of the Newton–Raphson iteration:

\[ f_{n+1}(t) = f_n(t) - \frac{F(t, f_n(t))}{F_x(t, f_n(t))}, \quad f_0(t) = 0. \]

By Taylor’s formula (Theorem 1.4.1), one shows \(\mathrm{val}\,F(t, f_{n+1}(t)) \geq 2\,\mathrm{val}\,F(t, f_n(t))\), so the iteration converges doubly-exponentially fast in the formal metric. Uniqueness follows from the same Taylor expansion argument.

Example. Taking \(F(t,x) = 1+t - (1+x)^n\) shows that \(1+t\) has a unique \(n\)th root in \(\mathbb{C}[[t]]\) with constant term 1 — the formal analogue of a familiar analytic fact.

Hensel’s Lemma immediately implies the existence and uniqueness of solutions in LIFT: to solve \(A(x) = x\phi(A(x))\), set \(F(x,y) = y - x\phi(y)\) and check that \(F(0,0)=0\) and \(\frac{\partial F}{\partial y}(0,0) = 1\).

1.5 Examples of Formal Power Series

Several formal power series arise constantly in combinatorics:

\[ e^x = \sum_{n \geq 0} \frac{x^n}{n!}, \quad \log(1-x)^{-1} = \sum_{n \geq 1} \frac{x^n}{n}, \quad (1+x)^a = \sum_{n \geq 0} \binom{a}{n} x^n, \]

where \(\binom{a}{n} = \frac{a(a-1)\cdots(a-n+1)}{n!}\) for any \(a \in R\). These satisfy the same functional identities as their analytic counterparts — \(e^{x+y} = e^x e^y\), \(\log(e^x) = x\), \(\frac{d}{dx}(1+x)^a = a(1+x)^{a-1}\) — because those identities hold coefficient-by-coefficient.

An elegant application is Abel’s extension of the binomial theorem: for \(n \geq 0\),

\[ (\alpha+\beta)(\alpha+\beta+n)^{n-1} = \sum_{k=0}^n \binom{n}{k} \alpha(\alpha+k)^{k-1} \cdot \beta(\beta+n-k)^{n-k-1}. \]

Rewriting the right side as a convolution, this becomes the identity \([x^n]F(\alpha+\beta, x) = [x^n]F(\alpha,x)F(\beta,x)\) where \(F(\gamma,x) = \sum_{n \geq 0} \frac{\gamma}{n!}(\gamma+n)^{n-1}x^n\). By LIFT applied to \(T(x) = xe^{T(x)}\) with \(f_\gamma(\lambda) = e^{\gamma\lambda}\), one identifies \([x^n]F(\gamma,x) = [x^n]e^{\gamma T(x)}\), and the identity reduces to the obvious \(e^{(\alpha+\beta)T(x)} = e^{\alpha T(x)} e^{\beta T(x)}\).

1.6 Formal Laurent Series and LIFT

The ring of formal Laurent series \(R((x))\) consists of expressions \(\sum_{k \geq N} a_k x^k\) for some \(N \in \mathbb{Z}\), allowing finitely many negative powers. If \(R\) is a field then \(R((x))\) is a field — the field of fractions of \(R[[x]]\).

Since \(x^{-1}\) has no antiderivative in \(R((x))\), formal integration is not defined. Instead we use the formal residue \([x^{-1}]A(x)\), an \(R\)-linear map satisfying integration by parts: \([x^{-1}]f'g = -[x^{-1}]fg'\).

This is the key lemma for proving LIFT.

The proof of (i) applies the substitution formula with \(B(\lambda) = \lambda/\phi(\lambda)\), using the fact that \(A(B(\lambda)) = \lambda\). Integration by parts converts the resulting residue calculation into the claimed formula.

---

Chapter 2: Exponential Generating Functions and Species

Ordinary generating functions count objects weighted by size. Exponential generating functions (EGFs) are designed for a different purpose: counting labelled structures. If we want to know how many ways to build a structure on a set \(X\) of \(n\) labelled vertices, EGFs are the natural tool. The key theoretical framework is the theory of species.

2.1 Species

The transport condition formalises the idea that structures are defined independently of the labels: relabelling via \(f\) transforms the structure. Some fundamental species are:

• \(E\) (Set): \(E_X = \{X\}\) for every \(X\). EGF: \(E(x) = e^x\).
• \(E_m\) (m-Set): \((E_m)_X = \{X\}\) if \(|X|=m\), else \(\emptyset\). EGF: \(E_m(x) = x^m/m!\).
• \(\mathcal{S}\) (Permutations): \(\mathcal{S}_X = \{\text{bijections } X \to X\}\). EGF: \((1-x)^{-1}\).
• \(\mathcal{C}\) (Cyclic permutations): EGF: \(\log(1-x)^{-1}\).
• \(\mathcal{L}\) (Linear orders): EGF: \((1-x)^{-1}\).

Note that \(\mathcal{S}\) and \(\mathcal{L}\) have the same EGF but are not naturally equivalent (a natural equivalence is a species isomorphism). One can prove \(\mathcal{L} \not\simeq \mathcal{S}\) by checking that no natural transformation between them can be a bijection on the 2-element set.

The EGF of species \(A\) is defined as \(A(x) = \sum_{n \geq 0} \#A_n \frac{x^n}{n!}\), where \(\#A_n = |A_X|\) for any set \(X\) of size \(n\).

2.2 Interspecies Interactions

Species can be combined through several operations, each with a clean EGF translation:

Sum: \((A \oplus B)_X = (\{1\} \times A_X) \sqcup (\{2\} \times B_X)\). EGF: \(A(x) + B(x)\).

\[(A \ast B)_X = \bigsqcup_{S \subseteq X} A_S \times B_{X \setminus S}.\]

EGF: \(A(x)B(x)\).

Marking \(A^\bullet\): An \(A^\bullet\)-structure on \(X\) is a pair \((\alpha, x)\) with \(\alpha \in A_X\) and \(x \in X\) a “marked” element. EGF: \(x \frac{d}{dx}A(x)\).

Derivative \(A'\): An \(A'\)-structure on \(X\) is an \(A\)-structure on \(X \cup \{X\}\) (adding a special unlabelled element). EGF: \(\frac{d}{dx}A(x)\).

Composition: If \(B\) is connected (\(B_\emptyset = \emptyset\)), an \(A[B]\)-structure on \(X\) consists of a set partition \(P\) of \(X\), an \(A\)-structure on \(P\), and a \(B\)-structure on each block of \(P\). EGF: \(A(B(x))\).

Example: Since every permutation decomposes uniquely into disjoint cyclic permutations, we have \(\mathcal{S} \simeq E[\mathcal{C}]\), giving the identity \(e^{\log(1-x)^{-1}} = (1-x)^{-1}\). More substantively:

\[[x^n]T(x) = \frac{1}{n}[\lambda^{n-1}]e^{n\lambda} = \frac{n^{n-1}}{n!}.\]

Thus there are \(n^{n-1}\) rooted labelled trees on \(n\) vertices — and \(n^{n-2}\) unrooted ones (Cayley’s formula).

2.3 Mixed Generating Functions

A species \(A\) may carry a weight function \(\mathrm{wt}: A_X \to \mathbb{Z}^k\), compatible with relabelling. The mixed generating function is

\[ A(x; t_1, \ldots, t_k) = \sum_{n \geq 0} A_n(t_1,\ldots,t_k) \frac{x^n}{n!}, \]

where \(A_n(t_1,\ldots,t_k)\) is the ordinary generating function for \(A_{[n]}\) by weight. The main theorem for EGFs extends to mixed generating functions with the same formulas.

Stirling numbers. Give each cyclic permutation weight 1 (so a permutation has weight equal to its number of cycles). The mixed EGF for permutations is \(\mathcal{S}(x;y) = (1-x)^{-y}\). The coefficients \(S_{n,k} = n![x^n y^k]\mathcal{S}(x,y)\) are the Stirling numbers of the first kind. From this, the expected number of cycles in a random permutation of \([n]\) is \(\frac{d}{dy}\mathcal{S}(x;y)\big|_{y=1}\) evaluated at \([x^n]\), which gives \(1 + \frac{1}{2} + \cdots + \frac{1}{n}\) — the \(n\)th harmonic number.

Combinatorial proof of LIFT. Using trees with a sophisticated weight function that encodes the degrees of vertices, one constructs a weight-preserving bijection that directly verifies LIFT. The key is the correspondence \(A \simeq E_1 \ast \Phi[A]\), where \(\Phi\) is a species with mixed generating function \(\phi(x; t_0, t_1, \ldots)\) that can represent any power series by choosing the \(t_i\) appropriately.

---

Chapter 3: Signed Formulae and Inclusion-Exclusion

Not every counting formula is obviously non-negative. Determinants, Möbius functions, and alternating sums can all produce formulas whose positivity is not transparent. This chapter develops techniques for working with such signed formulae: inclusion-exclusion, sign-reversing bijections, and Möbius inversion.

3.1 Inclusion-Exclusion

The fundamental inversion relationship between two functions on subsets is:

The key special case: if \(S\) is a finite set and \(A_1, \ldots, A_n \subseteq S\), with \(f(\alpha) = \#\bigcap_{i \in \alpha} A_i\) and \(g(\alpha)\) counting elements with exactly the properties indexed by \(\alpha\), then for \(\alpha = \emptyset\):

\[ g(\emptyset) = \#\!\left(S \setminus \bigcup_{i=1}^n A_i\right) = \sum_{\beta \subseteq [n]} (-1)^{|\beta|} \#\!\bigcap_{i \in \beta} A_i. \]

Derangements. The number \(D_n\) of fixed-point-free permutations of \([n]\) is obtained by taking \(A_i\) to be the set of permutations fixing \(i\):

\[ D_n = n! \sum_{k=0}^n \frac{(-1)^k}{k!} \approx \frac{n!}{e}. \]

Ménage problem. \(n\) couples seated at a circular table so that no person sits next to their partner or a person of the same gender: the count is

\[ M_n = \sum_{k=0}^n (-1)^k \frac{2n}{2n-k}\binom{2n-k}{k}(n-k)!, \]

obtained by expressing the rook placements \(R_k\) on the disallowed board in closed form.

3.2 Inclusion-Exclusion with Generating Functions

The inclusion-exclusion principle has a clean generating function form:

Strings avoiding a pattern. The generating function for binary strings not containing 011 as a substring is computed by letting \(A_i\) be the set of strings with a marked occurrence of 011 starting at position \(i\). The generating function for strings with \(k\) marked occurrences is \(F(x;u) = (1 - 2x - ux^3)^{-1}\), so the desired generating function is \(G(x;0) = F(x;-1) = (1 - 2x + x^3)^{-1}\).

3.3 Sign-Reversing Bijections

The most powerful technique for proving signed identities is to find a bijection that cancels almost all terms:

The map \(\alpha\) is called a sign-reversing involution.

Inclusion-Exclusion revisited. Define \(S' = \{(x,\alpha) : x \in A_i \text{ for all } i \in \alpha\}\) with index \(|\alpha|\) and weight 1. The sign-reversing involution \(\alpha(x,\alpha) = (x, \alpha \triangle \{j\})\), where \(j = \min\{i : x \in A_i\}\), pairs up almost all elements, leaving only those with \(x \notin \bigcup A_i\). This gives another proof of inclusion-exclusion.

Gessel-Viennot theorem. This is one of the deepest applications of sign-reversing bijections:

The proof constructs a sign-reversing involution on the set of all \(n\)-tuples of paths (not necessarily vertex-disjoint): given a tuple where paths \(P_i\) and \(P_j\) first intersect at vertex \(v\), swap the tails of \(P_i\) and \(P_j\) after \(v\). This is weight-preserving (same edges are used), changes the sign of the associated permutation (by a transposition), and is an involution, leaving only the non-intersecting tuples uncancelled.

3.4 Möbius Inversion

Inclusion-exclusion is a special case of a theorem about partially ordered sets.

\[ \mu(x,x) = 1, \quad \mu(x,y) = -\sum_{x \leq z < y} \mu(x,z) \text{ for } x < y, \quad \mu(x,y) = 0 \text{ otherwise.} \]

Thinking of \(\mu\) and the zeta function \(\zeta(x,y) = \mathbf{1}[x \leq y]\) as upper-triangular matrices:

Examples of Möbius functions:

1. Total order: \(\mu(i,j) = 1\) if \(i=j\), \(-1\) if \(i = j-1\), and 0 otherwise — Möbius inversion is just differencing.

2. Divisibility: \(\mu(1,n) = (-1)^m\) if \(n\) is a product of \(m\) distinct primes, and 0 otherwise — this is the classical number-theoretic Möbius function.

3. Boolean lattice (subsets of \([n]\)): \(\mu(\alpha,\beta) = (-1)^{|\beta|-|\alpha|}\) for \(\alpha \subseteq \beta\) — this recovers the inclusion-exclusion formula.

---

Chapter 4: Partitions, Tableaux, and Algorithms

Partitions and Young tableaux are central objects in algebraic combinatorics, lying at the intersection of representation theory, symmetric function theory, and combinatorial algorithms. This chapter develops three fundamental tableau algorithms whose remarkable properties underpin the theory of symmetric functions in the next chapter.

4.1 Partitions and q-Analogues

A partition \(\lambda = (\lambda_1, \ldots, \lambda_d)\) is a weakly decreasing sequence of positive integers. Its size is \(|\lambda| = \lambda_1 + \cdots + \lambda_d\); we write \(\lambda \vdash n\) if \(|\lambda| = n\). The Ferrers diagram (or Young diagram) of \(\lambda\) consists of \(\lambda_i\) boxes in row \(i\).

\[ \sum_{\lambda} q^{|\lambda|} = \prod_{i=1}^\infty (1-q^i)^{-1}. \]

The conjugate partition \(\lambda^t\) is obtained by reflecting the Ferrers diagram along the main diagonal. Conjugation gives a bijection between partitions with at most \(k\) parts and partitions with largest part at most \(k\).

\[ [n]_q = 1 + q + \cdots + q^{n-1}, \quad [n]_q! = [n]_q[n-1]_q \cdots [1]_q, \quad \binom{n}{k}_q = \frac{[n]_q!}{[k]_q!\,[n-k]_q!}. \]

The proof counts \(k\)-dimensional subspaces of \(\mathbb{F}_q^{k+\ell}\) in two ways. First, the number of such subspaces equals \(\frac{(q^{k+\ell}-1)(q^{k+\ell}-q)\cdots(q^{k+\ell}-q^{k-1})}{(q^k-1)(q^k-q)\cdots(q^k-q^{k-1})} = \binom{k+\ell}{k}_q\). Second, a subspace has a unique row-reduced echelon form, and the positions of the free entries in such a matrix correspond bijectively to partitions \(\lambda \in P_{k,\ell}\), with \(q\) choices for each free entry, contributing \(q^{|\lambda|}\) to the count.

4.2 Young Tableaux

The content of a SSYT \(T\) is \((c_1, c_2, \ldots)\) where \(c_i\) is the number of \(i\)’s in \(T\).

The combinatorics of tableaux is rich and deep. In the next chapter, the generating function \(s_\lambda = \sum_{T \in \mathrm{SSYT}(\lambda)} x^{\mathrm{content}(T)}\) will be shown to be a symmetric function — the Schur function — one of the most important symmetric functions in mathematics.

4.3 Row-Insertion

The first algorithm takes a SSYT \(T\) and a positive integer \(a\), and produces a new SSYT denoted \(T \leftarrow a\).

Row-merge subroutine. Given a row and an integer \(b\): if \(b \geq\) every entry in the row, append \(b\) to the end and STOP. Otherwise, let \(c\) be the leftmost entry greater than \(b\); replace \(c\) with \(b\) and output (\emph{bump}) \(c\).

Row-insertion. Row-merge \(a\) into row 1 of \(T\). If an entry is bumped, row-merge it into row 2, and so on, until a STOP occurs.

The proof checks that the newly inserted entry at each stage is \(\geq\) its left neighbour, \(\leq\) its right neighbour, \(<\) its lower neighbour, and \(>\) its upper neighbour. The crucial observation is that the sequence of bumps moves weakly leftward.

Key property. Row-insertion is invertible given the shape: given \(U \in \mathrm{SSYT}(\lambda^+)\) and \(\lambda \subset \lambda^+\) with one fewer box, there is a unique \(T \in \mathrm{SSYT}(\lambda)\) and unique integer \(a\) with \(U = T \leftarrow a\). The proof runs the algorithm in reverse, starting from the entry in \(\lambda^+/\lambda\).

Shape-tracking. Proposition 4.3.5 says: if \(a \leq b\), the new box added by \(T \leftarrow a \leftarrow b\) is strictly right of and weakly above the box added by \(T \leftarrow a\) (and symmetrically for \(a > b\)). This is fundamental for proving that RSK produces tableaux.

4.4 Sliding

The sliding algorithm takes a skew tableau \(T \in \mathrm{SSYT}(\lambda/\mu)\) and a marked corner of \(\mu\), and produces a new skew tableau \(T' \in \mathrm{SSYT}(\lambda'/\mu')\) with \(\mu' = \mu \setminus \{\text{marked corner}\}\).

The marked corner “slides” into the tableau, repeatedly swapping with the smaller of its right and lower neighbours (if tied, swap down). When neither neighbour exists, the process stops.

The deep connection between sliding and row-insertion: placing \(a\) to the upper-left of \(T\) (as a skew entry) and then sliding produces exactly \(T \leftarrow a\). More generally, rectification — repeatedly sliding a skew tableau until it has straight shape — is independent of the order in which corners are processed. This remarkable fact will follow from the crystal operator theory in §4.5.

4.5 Crystal Operators

For each positive integer \(a\), the crystal operators \(E_a, F_a, R_a\) act on SSYT by modifying the entries equal to \(a\) and \(a+1\):

1. Cross out all entries not equal to \(a\) or \(a+1\).
2. In reading order (rows read right-to-left, top to bottom), cross out pairs: when reading \(a+1\), pair it with the most recent uncrossed \(a\).
3. After pairing, the uncrossed entries form a word \(\underbrace{a+1 \cdots a+1}_{s}\underbrace{a \cdots a}_{t}\) in reading order.
4. \(E_a\): change the rightmost uncrossed \(a+1\) to \(a\) (if \(s \geq 1\)); else \(E_a(T) = \emptyset\).
5. \(F_a\): change the leftmost uncrossed \(a\) to \(a+1\) (if \(t \geq 1\)); else \(F_a(T) = \emptyset\).
6. \(R_a\): swap the numbers of uncrossed \(a\)’s and \(a+1\)’s (reflection).

The key theorem is:

The proof checks three cases based on whether the sliding move is to the right or downward and whether the entries near the marked corner are equal or unequal. In all cases, the crossing-out pattern is unchanged by the slide.

This theorem has a powerful corollary: rectification is well-defined (independent of corner choices), because sliding commutes with all crystal operators.

---

Chapter 5: The Ring of Symmetric Functions

The ring of symmetric functions is one of the most beautiful algebraic structures in mathematics. It possesses multiple natural bases, a rich inner product theory, and deep connections to representation theory, geometry, and combinatorics. The Schur functions, indexed by partitions, are simultaneously: generating functions for tableaux, characters of representations of the symmetric group, and eigenvalues of the Casimir operators of \(\mathfrak{gl}_n\).

5.1 Symmetric Functions in Finitely Many Variables

The symmetric group \(S_d\) acts on \(\mathbb{Q}[x_1, \ldots, x_d]\) by permuting variables. A polynomial \(f\) is symmetric if \(\sigma f = f\) for all \(\sigma \in S_d\). The ring of symmetric polynomials is

\[\Lambda^{(d)} = \mathbb{Q}[x_1, \ldots, x_d]^{S_d}.\]

For each partition \(\lambda \vdash n\) with at most \(d\) parts, the monomial symmetric polynomial is

\[m_\lambda = \sum_{\text{distinct}} x_{\sigma(1)}^{\lambda_1} \cdots x_{\sigma(d)}^{\lambda_d},\]

where the sum is over distinct monomials from permuting the exponents.

The dimension of \(\Lambda^{(d)}_n\) equals the number of partitions of \(n\) with at most \(d\) parts.

5.2 Symmetric Functions in Infinitely Many Variables

As \(d \to \infty\) the spaces \(\Lambda^{(d)}_n\) stabilize (for \(d \geq n\) the dimension equals the total number of partitions of \(n\)), so we define

\[\Lambda = \varprojlim_d \Lambda^{(d)},\]

the ring of symmetric functions in infinitely many variables. The monomial basis \(\{m_\lambda \mid \lambda \vdash n\}\) gives \(\dim \Lambda_n = p(n)\), the number of partitions of \(n\).

Four more families of symmetric functions are fundamental:

• Elementary: \(e_n = m_{1^n} = \sum_{i_1 < \cdots < i_n} x_{i_1} \cdots x_{i_n}\).
• Complete (homogeneous): \(h_n = \sum_\lambda m_\lambda = \sum_{i_1 \leq \cdots \leq i_n} x_{i_1} \cdots x_{i_n}\).
• Power sum: \(p_n = m_n = \sum_i x_i^n\).
• Schur: \(s_\lambda = \sum_{T \in \mathrm{SSYT}(\lambda)} x^{\mathrm{content}(T)}\).

These are extended to indexed families by \(e_\lambda = e_{\lambda_1} \cdots e_{\lambda_k}\) (and similarly \(h_\lambda, p_\lambda\)).

The elegant proof uses the crystal reflection operator \(R_i\), which gives a bijection between SSYT of content \((\ldots, c_i, c_{i+1}, \ldots)\) and content \((\ldots, c_{i+1}, c_i, \ldots)\). Since transpositions generate \(S_\infty\), this proves symmetry.

5.3 Five Bases and the Fundamental Involution

The proof for \(\{s_\lambda\}\) is particularly illuminating. The Kostka numbers \(K_{\lambda\mu} = \#\{\text{SSYT of shape } \lambda, \text{ content } \mu\}\) satisfy \(s_\lambda = m_\lambda + \sum_{\mu <_{\mathrm{lex}} \lambda} K_{\lambda\mu} m_\mu\), so the change-of-basis matrix is upper triangular with 1’s on the diagonal (in the lexicographic ordering) — hence invertible.

\[\sum_{k=0}^n (-1)^k e_k h_{n-k} = 0 \quad (n \geq 1).\]

This relation shows \(\{e_1, e_2, \ldots\}\) are algebraically independent generators of \(\Lambda\), so we can uniquely define a ring homomorphism \(\omega: \Lambda \to \Lambda\) by \(\omega(e_i) = h_i\). From \(E(t)H(-t) = 1\) and \(\omega(H(t)) = E(t)\), one deduces \(\omega^2 = \mathrm{id}\), making \(\omega\) an involution called the fundamental involution. It acts on the power sums by \(\omega(p_k) = (-1)^{k-1}p_k\).

\[nH_n = \sum_{k=1}^n h_{n-k} p_k, \quad ne_n = \sum_{k=1}^n (-1)^{k-1} e_{n-k} p_k.\]

5.4 The Hall Inner Product

Define a bilinear form on \(\Lambda\) by declaring \(\langle h_\lambda, m_\mu \rangle = \delta_{\lambda\mu}\). This is well-defined since \(\{h_\lambda\}\) and \(\{m_\mu\}\) are bases.

The right side is the Cauchy kernel. Since \(\prod_{i,j}(1-x_iy_j)^{-1} = \sum_\lambda m_\lambda(x) h_\lambda(y)\), this shows \(\{h_\lambda\}\) and \(\{m_\lambda\}\) are dual — consistent with our definition.

\[\prod_{i,j}(1-x_iy_j)^{-1} = \exp\!\sum_{k \geq 1} \frac{p_k(x)p_k(y)}{k} = \sum_\lambda \frac{p_\lambda(x)p_\lambda(y)}{z(\lambda)},\]

where \(z(\lambda) = \prod_j j^{m_j} m_j!\) and \(m_j\) is the number of parts of \(\lambda\) equal to \(j\).

5.5 The Robinson-Schensted-Knuth Correspondence

The proof constructs a weight-preserving bijection between pairs \((P,Q)\) of SSYT of the same shape and multisets \(\{(a_1,b_1),\ldots,(a_k,b_k)\}\) of pairs of positive integers — the Robinson-Schensted-Knuth (RSK) correspondence.

Algorithm. Order the pairs lexicographically. Set \(P_0 = Q_0 = \emptyset\). At step \(i\): let \(P_i = P_{i-1} \leftarrow b_i\) (row-insert \(b_i\)), and extend \(Q_{i-1}\) to \(Q_i\) by adding a box in the new position, labelled \(a_i\). The result is \((P_k, Q_k)\).

Using Proposition 4.3.5, one verifies that \(Q\) is a SSYT (rows weakly increasing, columns strictly increasing). The algorithm is invertible: the largest entry of \(Q\) identifies the last step, allowing recovery of \((a_k, b_k)\) and reduction to \((P_{k-1}, Q_{k-1})\). Surjectivity is immediate.

\[n! = \sum_{\lambda \vdash n} (f^\lambda)^2, \quad \text{where } f^\lambda = \#\mathrm{SYT}(\lambda).\]

A non-obvious symmetry: if \(\{(a_i,b_i)\} \leftrightarrow (P,Q)\) under RSK, then \(\{(b_i,a_i)\} \leftrightarrow (Q,P)\). Applied to the standard case: \(\pi \leftrightarrow (P,Q)\) implies \(\pi^{-1} \leftrightarrow (Q,P)\), so \(P = Q\) if and only if \(\pi\) is an involution. Counting involutions: the species of involutions is \(E[E_1 \oplus E_2]\), so \(\sum_{\lambda \vdash n} f^\lambda = [x^n]\exp(x + x^2/2)\).

5.6 The Jacobi-Trudi Formula

The proof applies the Gessel-Viennot theorem to a grid where paths from \(A_i\) to \(Z_j\) accumulate weight \(h_{\lambda_j - j + i}\). Vertex-disjoint paths correspond bijectively to SSYT of shape \(\lambda\), with the determinantal weight accounting for signs.

Two formulas for the number of standard tableaux follow:

Degree formula: \(\displaystyle\frac{f^\lambda}{|\lambda|!} = \frac{\prod_{i \[f^\lambda = \frac{|\lambda|!}{\prod_{\alpha \in \lambda} h(\alpha)},\]

where \(h(\alpha)\) is the hook-length at cell \(\alpha\) (number of cells directly to the right plus cells directly below, plus 1).

\[s_\lambda(x_1,\ldots,x_d) = \frac{\det(x_j^{\lambda_i - i + d})}{\det(x_j^{-i+d})},\]

where the denominator is the Vandermonde determinant. This formula, going back to Cauchy and Schur, connects the combinatorial definition via tableaux to the algebraic definition via alternating polynomials.

5.7 Skew Schur Functions and the Pieri Rule

\[s_{\lambda/\mu} = \sum_{T \in \mathrm{SSYT}(\lambda/\mu)} x^{\mathrm{content}(T)}.\]

The special case \(\nu = (k)\) (a single part):

Similarly, \(s_\mu e_k = \sum s_\lambda\) where the sum is over \(\lambda\) with \(\lambda/\mu\) a vertical strip (Dual Pieri), and \(\omega(s_\lambda) = s_{\lambda^t}\).

5.8 The Littlewood-Richardson Rule

\[\mathrm{LR}_{\lambda/\mu;\nu} = \{T \in \mathrm{SSYT}(\lambda/\mu) : E_a(T) = \emptyset \text{ for all } a \geq 1\}.\]

The numbers \(c^\lambda_{\mu,\nu} = |\mathrm{LR}_{\lambda/\mu;\nu}|\) are the Littlewood-Richardson coefficients.

The proof uses the crystal of SSYT(\(\lambda/\mu\)): the directed graph with an edge \(T \to E_a(T)\) whenever defined. LR tableaux are precisely the sources in this graph. By Theorem 4.5.4, sliding commutes with crystal operators, so each connected component \(C\) of the crystal is isomorphic to \(\Gamma(\nu_C)\) (the crystal on SSYT(\(\nu_C\))) for some unique partition \(\nu_C\). Since the crystal on a straight shape is connected (with unique LR tableau having entry \(i\) in every box of row \(i\)), summing over components gives \(s_{\lambda/\mu} = \sum_\nu c^\lambda_{\mu,\nu} s_\nu\). The result then follows from Theorem 5.7.2.

This argument simultaneously proves that rectification is well-defined: any sequence of slides on a skew tableau defines the unique crystal isomorphism to the straight shape, regardless of which corners are chosen.

Alternate characterizations of LR tableaux: \(T\) is an LR tableau iff in every initial segment of the reading word, the count of \(1\)’s is at least the count of \(2\)’s, which is at least the count of \(3\)’s, and so on — the classical “ballot sequence” condition.

5.9 Plane Partitions and MacMahon’s Formula

A plane partition with support \(\lambda\) is a filling \(\Pi\) of the boxes of \(\lambda\) with non-negative integers, weakly decreasing along rows and down columns. These are 2-dimensional analogues of ordinary partitions.

Enumerating plane partitions by their size \(|\Pi| = \sum \Pi_{\alpha}\):

Bijection. Any plane partition \(\Pi\) with diagonal entries \(\lambda\) produces a pair \((P, Q)\) of “reverse SSYT” of the same shape \(\lambda\), defined by reading the plane partition along rows and columns. Under this bijection, the generating function for plane partitions with all entries from \(\mathbb{Z}_{>0}\) of shape \(\lambda\) is \(s_\lambda(x, x^2, x^3, \ldots)\), while the generating function for entries from \(\mathbb{Z}_{\geq 0}\) is \(s_\lambda(1, x, x^2, \ldots)\).

Summing over all shapes via the Cauchy identity:

\[\sum_\lambda s_\lambda(x, x^2, \ldots) s_\lambda(1, x, x^2, \ldots) = \prod_{i,j \geq 1}(1 - x^{i+j-1})^{-1} = \prod_{k \geq 1}(1-x^k)^{-k}.\]

This is MacMahon’s formula: the generating function for all plane partitions by size is \(\prod_{k \geq 1}(1-x^k)^{-k}\), a remarkable result connecting symmetric function theory to classical combinatorics.

---

Chapter 6: Representations of the Symmetric Group

The representation theory of the symmetric group \(S_n\) is one of the most complete and beautiful theories in all of algebra. As we will see, the irreducible representations are indexed by partitions of \(n\), their characters are given by the Schur functions, and the Kostka numbers and Littlewood-Richardson coefficients that appear throughout symmetric function theory have direct representation-theoretic interpretations.

6.1 Definitions and Basic Examples

A (finite-dimensional complex) representation of a finite group \(G\) is a finite-dimensional complex vector space \(V\) together with a group homomorphism \(\rho_V: G \to \mathrm{GL}(V)\). A subrepresentation is a \(G\)-invariant subspace; an irreducible representation (irrep) has no proper non-zero subrepresentations.

Key examples for \(S_n\):

• The permutation representation \(V = \mathbb{C}^n\) with \(\rho(\pi)e_i = e_{\pi(i)}\).
• The trivial representation \(T = \mathrm{span}\{(1,\ldots,1)\} \subset \mathbb{C}^n\).
• The standard representation \(\tilde{V} = \{x : \sum x_i = 0\} \subset \mathbb{C}^n\).
• The alternating representation \(A = \mathbb{C}\) with \(\rho(\pi) = \mathrm{sgn}(\pi)\).

For each partition \(\lambda \vdash n\), define \(M^\lambda\) as the vector space spanned by tabloids of shape \(\lambda\): fillings of rows of \(\lambda\) with distinct elements of \([n]\), where rows are unordered. The symmetric group acts by permuting entries.

6.2 A Crash Course in Representation Theory

The character of \(V\) is the class function \(\chi_V: G \to \mathbb{C}\) defined by \(\chi_V(g) = \mathrm{tr}\,\rho_V(g)\). Characters determine representations up to isomorphism, and satisfy \(\chi_{V \oplus W} = \chi_V + \chi_W\).

The character inner product \(\langle \chi_W, \chi_V\rangle = \frac{1}{|G|}\sum_{g \in G} \chi_W(g)\overline{\chi_V(g)}\) satisfies:

6.3 Character Theory for S_n

For \(G = S_n\), the conjugacy classes are indexed by cycle types, hence by partitions \(\mu \vdash n\). The inner product formula becomes

\[\langle \chi_W, \chi_V\rangle = \sum_{\mu \vdash n} \frac{1}{z(\mu)} \chi_W(\mu)\chi_V(\mu).\]

The characters \(\xi^\lambda\) of the representations \(M^\lambda\) play a key role:

The proof: a tabloid of shape \(\lambda\) is fixed by a permutation \(\pi\) of cycle type \(\mu\) if and only if each cycle of \(\pi\) is contained within some row. Counting such arrangements gives \([x_1^{\lambda_1} \cdots x_d^{\lambda_d}]p_\mu\), which equals \(\langle h_\lambda, p_\mu\rangle\) by the Hall inner product.

Since \(\xi^\lambda(\mu) = 0\) when \(\mu >_{\mathrm{lex}} \lambda\) (the first part of \(\mu\) exceeds the number of parts of \(\lambda\)), the characters \(\{\xi^\lambda\}\) are linearly independent. This proves: (1) every irrep is a constituent of some \(M^\lambda\); (2) the number of non-isomorphic irreps equals the number of partitions of \(n\); (3) all characters of \(S_n\) are integer-valued.

6.4 Specht Modules

For each \([n]\)-filling \(T\) of a partition shape \(\lambda\), define:

• the column stabilizer (C(T) = {\pi \in S_n : \pi \text{ fixes each column setwise}}$,
• the Young symmetrizer \(b_T = \sum_{\pi \in C(T)} \mathrm{sgn}(\pi)\,\pi \in \mathbb{C}[S_n]\),
• the polytabloid \(v_T = b_T \cdot \{T\} \in M^\lambda\).

Two key lemmas establish the irreducibility:

Lemma 6.4.3. If \(a \neq b\) are in the same row of tabloid \(U\) and the same column of filling \(T\), then \(b_T U = 0\).

Lemma 6.4.4. For any \(x \in M^\lambda\): \(b_T x\) is a scalar multiple of \(v_T\). Moreover \(b_T v_T = |C(T)| v_T \neq 0\).

In particular, \(S^\lambda \not\cong S^\mu\) for \(\lambda \neq \mu\), so the \(\{S^\lambda : \lambda \vdash n\}\) are all the irreducible representations of \(S_n\).

6.5 Characters of Specht Modules

The proof defines an isometry \(\Psi\) from class functions to \(\Lambda_n\) by \(\Psi(\xi^\mu) = h_\mu\), then shows the orthonormal basis obtained by Gram-Schmidt from \(\{h_\mu\}\) (in lexicographically decreasing order) is exactly \(\{s_\lambda\}\) — a beautiful convergence of symmetric function theory and representation theory.

Key corollaries:

• \(\dim S^\lambda = f^\lambda = \chi^\lambda(1^n) = \langle s_\lambda, h_{1^n}\rangle\) — so the hook-length formula computes dimensions of Specht modules.
• The Kostka numbers \(K_{\lambda\mu}\) express the decomposition \(M^\mu = \bigoplus_\lambda S^\lambda{}^{\oplus K_{\lambda\mu}}\).
• The group algebra decomposes as \(\mathbb{C}[S_n] \cong \bigoplus_{\lambda \vdash n} \mathrm{End}(S^\lambda)\), giving the identity \(n! = \sum_\lambda (f^\lambda)^2\).

6.6 The Centre of the Group Algebra

The centre of \(\mathbb{C}[S_n]\) has basis \(\{C_\mu : \mu \vdash n\}\), where \(C_\mu = \sum_{\pi \in C_\mu} \pi\) is the sum of all permutations of cycle type \(\mu\).

\[\alpha_\mu^\lambda = \frac{n!}{z(\mu)f^\lambda}\chi^\lambda(\mu).\]

The central elements \(F_\theta = \sum_\nu \beta_{\theta\nu} C_\nu\) (where \((\beta_{\theta\nu})\) is the inverse matrix to \((\alpha_\mu^\lambda)\)) are orthogonal idempotents: \(F_\theta F_{\theta'} = \delta_{\theta\theta'} F_\theta\).

The product of conjugacy class sums yields:

\[A(w,x,y) = \sum_\theta \frac{|\theta|!}{f^\theta}\, s_\theta(w)s_\theta(x)s_\theta(y).\]

6.7 Enumeration of Maps

A labelled map is a graph embedded in a closed oriented surface so that all faces are discs, with the \(2n\) endpoints of the \(n\) edges labelled \(1, \ldots, 2n\).

Given a labelled map with \(n\) edges, one constructs three permutations:

• \(\pi\): cycles list the labels around each vertex counterclockwise.
• \(\sigma\): cycles are the pairs of labels of each edge (\(\sigma \in C_{2^n}\)).
• \(\tau\): cycles list the labels at each face counterclockwise.

These satisfy \(\pi\sigma\tau = \mathrm{id}\), and the map is connected if and only if the triple \((\pi,\sigma,\tau)\) is connected (its “superimposed graph” is connected). By Euler’s formula, if the vertex degree sequence is \(\lambda\) and face degree sequence is \(\mu\), the map lies on a surface of genus \(g\) where \(|\lambda| - n + |\mu|/2 = 2 - 2g\).

\[\tilde{A}(w,x,y) = \log A(w,x,y) = \log\!\sum_\theta \frac{|\theta|!}{f^\theta} s_\theta(w)s_\theta(x)s_\theta(y).\]

---

Chapter 7: Representations of sl₂(ℂ)

Lie algebras are infinitesimal symmetry objects whose representation theory connects to combinatorics in deep ways. The simplest non-abelian Lie algebra is \(\mathfrak{sl}_2(\mathbb{C})\), and its representation theory yields powerful tools for proving that counting sequences are unimodal and palindromic — properties that can be extremely difficult to establish by direct combinatorial arguments.

7.1 What is an sl₂(ℂ)-Representation?

\[ EF - FE = 2H, \quad HE - EH = 2E, \quad HF - FH = -2F. \]\[ e = \begin{pmatrix}0 & 1 \\ 0 & 0\end{pmatrix}, \quad f = \begin{pmatrix}0 & 0 \\ 1 & 0\end{pmatrix}, \quad h = \begin{pmatrix}1 & 0 \\ 0 & -1\end{pmatrix}, \]

satisfying \([e,f] = h\), \([h,e] = 2e\), \([h,f] = -2f\). A representation sends \(e \mapsto E\), \(f \mapsto F\), \(h \mapsto H\) preserving these brackets.

7.2 The Main Example: C^{2^n}

One checks \(EF - FE = 2H\) directly: the coefficient of \(x_\sigma\) in \((EF - FE)x_\sigma\) is the number of 1’s in \(\sigma\) minus the number of 2’s.

The symmetric group \(S_n\) also acts on \(\mathbb{C}^{2^n}\) by permuting positions: \(\pi x_{\sigma_1 \cdots \sigma_n} = x_{\sigma_{\pi(1)} \cdots \sigma_{\pi(n)}}\). Since this action commutes with \(E, F, H\), any \(G\)-invariant subspace (for any subgroup \(G \leq S_n\)) is an \(\mathfrak{sl}_2\)-subrepresentation.

7.3 Palindromic and Unimodal Sequences

Application. Let \(P_{k,\ell}\) be the set of partitions with at most \(k\) parts and largest part at most \(\ell\), and let \(p_m = |P_{k,\ell} \cap \{\lambda : |\lambda| = m\}|\). We have \(\sum_m p_m q^m = \binom{k+\ell}{k}_q\), a symmetric polynomial in \(q\) of degree \(k\ell\). The coefficients \(p_0, p_1, \ldots, p_{k\ell}\) are palindromic (easy, by the bijection \(\lambda \mapsto (k^{(\ell)} - \lambda)\)) but the unimodality is far from obvious.

To prove unimodality, form the space \(W \subset \mathbb{C}^{2^{k\ell}}\) of \(G\)-invariant vectors (for the group \(G\) permuting rows and then permuting rows among themselves). Each partition \(\lambda \in P_{k,\ell}\) gives a basis vector \(w_\lambda\) that is an eigenvector of \(H\) with eigenvalue \(2|\lambda| - k\ell\). Thus \(\dim W_{2m-k\ell} = p_m\), and unimodality follows from Corollary 7.3.3.

7.4 Crystal Operators Revisited

The crystal operators from Chapter 4 arise naturally as the arrows in the representation-theoretic graph of \(\mathbb{C}^{2^n}\).

\[z_{1^k 2^{n-k}} = \sum_{\sigma : \sigma \text{ has } k \text{ ones}} x_\sigma.\]

These satisfy \(Ez_{1^k 2^{n-k}} = (n-k)z_{1^{k+1}2^{n-k-1}}\) and \(Fz_{1^k 2^{n-k}} = k\, z_{1^{k-1}2^{n-k+1}}\) — a “good basis” for \(W\). This is extended to all of \(\mathbb{C}^{2^n}\) via maps \(\phi_k: \mathbb{C}^{2^m} \to \mathbb{C}^{2^{m+2}}\) defined by \(\phi_k(x_\sigma) = x_{\sigma_1\cdots\sigma_k 21 \sigma_{k+1}\cdots\sigma_m} - x_{\sigma_1\cdots\sigma_k 12 \sigma_{k+1}\cdots\sigma_m}\), building a good basis \(\{z_\sigma : \sigma \in \{1,2\}^n\}\) for all of \(\mathbb{C}^{2^n}\).

In other words, the combinatorial pairing algorithm used by crystal operators is precisely the algebraic construction of the \(\mathfrak{sl}_2\) structure. This identification is achieved through the RSK correspondence:

This is the beginning of the general story for \(\mathfrak{sl}_m(\mathbb{C})\): its representation theory is connected to strings in \(\{1,\ldots,m\}^n\), the crystal operators \(E_a\) for \(a = 1, \ldots, m-1\), and the full RSK correspondence for two-row tableaux extended to \(m\) rows. The deeper theory — involving highest weight representations, the classification of finite-dimensional \(\mathfrak{sl}_m\)-modules, and Kazhdan-Lusztig theory — extends far beyond the scope of these notes, but the combinatorial foundations developed here form the essential groundwork.