So we grew together
Like to a double cherry, seeming parted
But yet an union in partition
Two lovely berries moulded on one stem
— William Shakespeare (A Midsummer Night’s Dream)
Recall from Chapter 2 that an integer partition of size $n$ is a sequence of positive integers listed in weakly-decreasing order that sum to $n.$ Equivalently, partitions are compositions where the order of the summands doesn’t matter (writing partitions with terms in weakly decreasing order gives a canonical representative for equivalent compositions).
Example: The compositions of size 3 are
$$ 3 = 2 + 1 = 1 + 2 = 1+1+1 $$
while the partitions of size 3 are
$$ 3 = 2 + 1 = 1+1+1. $$
The compositions $2+1$ and $1+2$ have the same set of summands, so we consider only the one that is in weakly-decreasing order.
If $\lambda = (\lambda_1,\dots,\lambda_r)$ is a partition then following standard convention we write
$$n(\lambda) = |\lambda| = \lambda_1 + \cdots + \lambda_r$$
for the size of the partition and
$$k(\lambda)=r$$
for the number of parts (or summands) that it contains.
Although there is no nice explicit formula for the number $p_n$ of partitions of size $n,$ the generating functions of partitions with various restrictions often have compact representations. This allows us to, for instance, show that sets of partitions with different restrictions have the same counting sequences, without ever explicitly finding the counting sequences.
We begin by characterizing the generating function of the class $\mathcal{Y}$ of unrestricted partitions.
Theorem: The generating function of partitions is
$$ \Phi(z) = \sum_{\lambda \in \mathcal{Y}}z^{n(\lambda)} = \prod_{k \geq 0}\frac{1}{1-z^k}. $$
Proof of Theorem
Intuitively, we think of a partition as a sequence of $1$s, followed by a sequence of $2$s, followed by a sequence of $3$s, and so on, resulting in the generating function
$$
\begin{aligned}
\Phi(z) &= \underbrace{(1 + z + z^2 + \cdots)}_{\text{contributions of 1s}}\underbrace{(1 + z^2 + z^4 + \cdots)}_{\text{contributions of 2s}}\cdots \\[+6mm]
&= \prod_{k \geq 1} \sum_{j \geq 0} \left(z^k\right)^j \\[+5mm]
&= \prod_{k \geq 1} \frac{1}{1-z^k}.
\end{aligned}
$$
Formally, let $\mathcal{S}$ be the class of infinite sequences $\mathbf{r} = (r_1,r_2,\dots)$ where each $r_j \in \mathbb{N}$ and only a finite number of the $r_j$ are non-zero. The map $f : \mathcal{Y} \rightarrow \mathcal{S}$ that takes a partition $\lambda$ and returns the sequence $(r_1,r_2,\dots)$ where $r_j$ is the number of $j$s that appear in $\lambda$ is a bijection (can you find its inverse?). If $f(\lambda) = \mathbf{r}$ then $n(\lambda) = r_1 + 2r_2 + 3r_3 + \cdots$ since each $j$ appears $r_j$ times in the partition.
Often we want to track the number of parts of a partition. It is easy to modify our previous argument to obtain the following.
Theorem: The bivariate generating function enumerating partitions by size and number of parts is
$$ \Phi(u,z) = \sum_{\lambda \in \mathcal{Y}}u^{k(\lambda)}z^{n(\lambda)} = \prod_{k \geq 0}\frac{1}{1-uz^k}. $$
Proof of Theorem
Let $f:\mathcal{Y}\rightarrow\mathcal{S}$ be the bijection constructed in our last proof. If $f(\lambda) = \mathbf{r}$ then $k(\lambda)=r_1+r_2+r_3+\cdots$ since $r_j$ is the number of times that $j$ appears. We have already seen that $n(\lambda) = r_1 + 2r_2 + 3r_3 + \cdots$ so
$$
\begin{aligned}
\Phi(u,z) = \sum_{\lambda \in \mathcal{Y}}u^{k(\lambda)}z^{n(\lambda)}
&= \sum_{\mathbf{r} \in \mathcal{S}}u^{r_1+r_2+r_3+\cdots}z^{r_1 + 2r_2 + 3r_3 + \cdots} \\[+4mm]
&= \left(\sum_{r_1 \in \mathbb{N}}(uz)^{r_1}\right)\left(\sum_{r_2 \in \mathbb{N}}(uz^2)^{r_2}\right)\cdots \\[+4mm]
&= \prod_{k \geq 1} \frac{1}{1-uz^k}.
\end{aligned}
$$
In fact, this bijective argument is quite flexible. Both of the previous theorems are special cases of the following result.
Partition Generating Function Theorem: For each $k \geq 1$ let $M_k$ be a subset of $\mathbb{N}.$ The bivariate generating function, tracking size and number of parts, for the subclass of partitions where the number of parts equal to $k$ lies in $M_k$ for all $k \geq 1$ is
$$ \Phi(u,z) = \prod_{k \geq 1}{\Bigg(}\sum_{j \in M_k}\left(u z^k\right)^j {\Bigg)}. $$
Remark: If we do not want to track the number of parts for a class of partitions then we can simply set the variable $u$ to $1$ in the Partition Generating Function Theorem.
Example: The bivariate generating function for the class of all partitions is recovered by taking $M_k = \mathbb{N}$ for all $k \geq 1,$ giving
$$ \Phi(u,z) = \prod_{k \geq 1}{\Bigg(}\sum_{j\geq 0}\left(u z^k\right)^j {\Bigg)} = \prod_{k \geq 1} \frac{1}{1-uz^k}. $$
Example: The (univariate) generating function for the class of partitions where every part is even is derived by taking
$$
M_k =
\begin{cases}
\{0\} &: \text{if $k$ is odd} \\
\mathbb{N} &: \text{if $k$ is even}
\end{cases}
$$
so that
$$ \Phi(z) = \prod_{k \geq 1}{\Bigg(}\sum_{j\geq 0}\left( z^{2k}\right)^j {\Bigg)} = \prod_{k \geq 1} \frac{1}{1-z^{2k}}. $$
Proof of the Partition Generating Function Theorem
Let $\mathcal{Y}_M$ be the subclass of partitions with the stated restrictions, and $\mathcal{S}_M$ be the subclass of $\mathcal{S}$ containing the sequences $\mathbb{r}$ where $r_j \in M_j$ for all $j.$ The bijection $f:\mathcal{Y}\rightarrow\mathcal{S}$ described above restricts to a bijection $f:\mathcal{Y}_M\rightarrow\mathcal{S}_M$ so that
$$
\begin{aligned}
\Phi(u,z) = \sum_{\lambda \in \mathcal{Y}_M}u^{k(\lambda)}z^{n(\lambda)}
&= \sum_{\mathbf{r} \in \mathcal{S}_M}u^{r_1+r_2+r_3+\cdots}z^{r_1 + 2r_2 + 3r_3 + \cdots} \\[+4mm]
&= \left(\sum_{r_1 \in M_1}(uz)^{r_1}\right)\left(\sum_{r_2 \in M_2}(uz)^{2r_2}\right)\cdots \\[+4mm]
&= \prod_{k \geq 1} {\Bigg(}\sum_{j \in M_k}\left(u z^k\right)^j {\Bigg)}.
\end{aligned}
$$
As mentioned above, we can use the Partition Generating Function Theorem to prove equality between the counting sequences of different classes of generating functions without finding the counting sequences themselves (which may be very complicated). This illustrates once again the role of the generating function as a data structure for sequences.
Corollary: For any $n \geq 0$ the number of partitions of $n$ with odd parts equals the number of partitions of $n$ with distinct parts (i.e., where each part appears at most once).
Proof of Corollary
The Partition Generating Function implies that the generating function for the class of partitions with distinct parts is
$$
\begin{aligned}
\prod_{k \geq 1}\left(1+z^k\right)
&= \prod_{k \geq 1}\left(\left(1+z^k\right) \cdot \frac{1-z^k}{1-z^k}\right) \\[+2mm]
&= \frac{\prod_{k \geq 1}\left(1-z^{2k}\right)}{\prod_{k \geq 1}\left(1-z^k\right)} \\[+2mm]
&= \prod_{k \geq 1} \frac{1}{1-z^{2k-1}},
\end{aligned}
$$
where the final line follows from the fact that all even powers of $z$ in the denominator cancel with the terms in the numerator. But the Partition Generating Function implies that this final line is the generating function for the class of partitions with odd parts, so the number of partitions of size $n$ in these two classes are equal for all $n.$
Exercise: Find the generating function for the three classes of partitions where
each part occurs at most twice
each part is divisible by 3
every even part is divisible by 4 and each odd part occurs an even number of times.
Exercise: Prove that for all $n$ the number of partitions of $n$ where each part occurs at most 3 times equals the number of partitions of $n$ where each even part occurs at most once.
It can be extremely useful to display partitions graphically. If $\lambda = (\lambda_1,\dots,\lambda_r)$ is a partition then its Ferrers diagram consists of $r$ rows of dots with the $i$th row having $\lambda_i$ dots.
Example: The Ferrers diagram of the partition $\lambda = (5,3,3,2,1)$ is
For some arguments it is more convenient to draw boxes instead of dots, giving the Young diagram or Young tableau of a partition.
Example: The Young tableaux of size $5$ are
The following correspondences between properties of partitions and properties of their diagrams hold.
Partition
Diagram
size
number of dots/boxes
number of parts
number of rows
maximum part
number of columns
We now have three ways of thinking about and encoding partitions: as sequences of integers, using diagrams, and via their generating functions. Each of these viewpoints has its advantages. For instance, while generating functions are usually good for studying counting sequences, diagrams are often useful for studying symmetry.
If $\lambda = (\lambda_1,\dots,\lambda_k)$ is a partition of $n$ (with largest part $\ell = \lambda_1)$ then its conjugate partition $\lambda^\prime$ is the partition $\lambda^\prime = (\lambda_1^\prime,\dots,\lambda_r^\prime)$ of $n$ where $\lambda_j^\prime$ equals the number of indices $i \in \{1,\dots,r\}$ such that $\lambda_i \geq j.$
Conjugation is particularly easy to see using Ferrers diagrams: tracing through the definition shows that Ferrers diagram of $\lambda^\prime$ is obtained from the Ferrers diagram of $\lambda$ by swapping rows and columns (i.e., by reflecting the diagram over the main diagonal).
Example: The conjugate of $\lambda = (4,2,2,1,1)$ is $\lambda^\prime = (5,3,1,1).$
The map $\lambda \mapsto \lambda^\prime$ defined by conjugation is a bijection and is its own inverse (i.e., applying the map twice to any partition $\lambda$ returns $\lambda$). A partition is called self-conjugate if $\lambda^\prime = \lambda.$
Conjugating partitions immediately yields interesting results. For instance, the number of parts in $\lambda$ becomes the maximum part of $\lambda^\prime,$ and vice-versa, instantly proving the following result.
Lemma: For any $n \geq 0$ and positive integer $k$ the number of partitions of $n$ with $k$ parts equals the number of partitions of $n$ with maximum part $k.$
If $\lambda$ is a partition then its Durfee length $d(\lambda)$ is the number of indices $i$ such that $\lambda_i \geq i.$ Visually, $d(\lambda)$ is the number of dots on the main diagonal of the Ferrers diagram of $\lambda,$ which is also the side-length of the largest square fitting in the Ferrers diagram (known as the Durfee square of $\lambda$).
Example: If $\lambda = (5,3,3,2,1)$ then $d(\lambda)=3$
We can derive information about the Durfee length of partitions by relating it to other information we already know using bijections.
Proposition: Let $\mathcal{S}$ be the class of self-conjugate partitions. Then the bivariate generating function enumerating $\mathcal{S}$ by size and Durfee length is
$$ F(u,z) = \sum_{\lambda \in \mathcal{S}} u^{d(\lambda)}z^{n(\lambda)} = \prod_{k \geq 1} \left(1+uz^{2k-1}\right). $$
Proof of Proposition
The Partition Generating function implies that $\prod_{k \geq 1} \left(1+uz^{2k-1}\right)$ is the bivariate generating function enumerating the class of partitions with odd distinct parts by size and number of parts. Thus, letting $\mathcal{O}$ be the class of partitions with odd distinct parts, it is sufficient to construct a bijection $f:\mathcal{S}\rightarrow\mathcal{O}$ that preserves the size of a partition and sends $d(\lambda)$ to $k(\lambda).$
The general idea is that a row with an odd number of dots can be “folded”
and when the rows of a Ferrers diagram are distinct then this gives a valid partition and can be reversed.
Figure:
Example of the folding map.
Formally, we define $f$ as follows. Given $\lambda \in \mathcal{S}$ we let
$R_j$ be the points in the Ferrers diagram of $\lambda$ to the right of $(j,j)$
$D_j$ be the points in the Ferrers diagram of $\lambda$ below $(j,j)$
for each $1 \leq j \leq d(\lambda).$
Because $\lambda$ is self-conjugate we have $|R_j|=|D_j|$ for all $j.$ Furthermore, $|R_1| > |R_2| > \cdots$ and $|D_1| > |D_2| > \cdots,$ so if we define $f(\lambda)$ to be the partition $(\mu_1,\dots,\mu_{d(\lambda)})$ where $\mu_j = |R_j|+|D_j|+1$ then
$f(\lambda)$ is a partition with distinct parts
$f(\lambda)$ has $d(\lambda)$ parts
each part $\mu_j = |R_j|+|D_j|+1 = 2|R_j| + 1$ of $f(\lambda)$ is odd
the size of $f(\lambda)$ is
$$\underbrace{|R_1| + \cdots + |R_{d(\lambda)}|}_{\text{\# dots to the right of diagonal}} + \underbrace{|D_1| + \cdots + |D_{d(\lambda)}|}_{\text{\# dots under diagonal}} + d(\lambda) = n$$
It remains only to prove that $f$ is injective and surjective.
If $\lambda \neq \tau$ then $\lambda_i \neq \tau_i$ for some $i,$ meaning $R_i$ and $D_i$ have different sizes for $\lambda$ and $\tau$ so that $f(\lambda) \neq f(\tau).$ In other words, $f$ is injective.
To prove surjectivity we note that $\lambda\in\mathcal{S}$ is uniquely defined by the values $|R_1| > \cdots > |R_{d(\lambda)}| > 0,$ and for any sequence of positive integers $p_1 > p_2 > \cdots > p_r$ there is an element $\lambda \in \mathcal{S}$ with $|R_j|=p_j$ for all $j.$ Now, given $\mu \in \mathcal{O}$ we let $p_j = (\mu_i-1)/2$ so that $p_1 > \cdots > p_{k(\mu)}$ are positive integers. If $\lambda$ is the element of $\mathcal{S}$ with $|R_j|=p_j$ for all $j$ then $f(\lambda)=\mu,$ meaning $f$ is surjective.
Thus, $f$ is a bijection preserving size and mapping Durfee length to number of parts, giving the stated result.
Just as we used $q$-analogues to prove identities about polynomials, we can use partition enumeration to prove series identities. Introducing interesting parameters like Durfee length allow one to prove interesting identities.
The left-hand side of this identity is the bivariate generating function for the class of all partitions enumerated by size and number of parts (after changing variable names to match convention) so we interpret the right-hand side using partitions.
Recall that the Durfee square of a partition $\lambda,$ denoted $D_\lambda,$ is the $d(\lambda) \times d(\lambda)$ square in its Ferrers diagram starting in the top left corner.
We can decompose the Ferrers diagram of $\lambda$ into:
$D_\lambda$
the Ferrers diagram of a partition $\alpha_\lambda$ below $D_\lambda$
the Ferrers diagram of a partition $\beta_\lambda$ to the right of $D_\lambda$
Note that $\alpha_\lambda$ is a partition with maximum part at most $d(\lambda)$ and $\beta_\lambda$ is a partition with at most $d(\lambda)$ parts. Furthermore, for any partitions $\alpha$ and $\beta$ satisfying these two conditions we can construct a partition $\lambda$ such that $\alpha_\lambda = \alpha$ and $\beta_\lambda=\beta.$
Thus, we have a bijection $g$ from the class $\mathcal{Y}$ of partitions to the disjoint union
$$ \bigcup_{d \geq 0} \left(\{d\} \times A_d \times B_d\right) $$
where $d$ represents the Durfee length of a partition, $A_d$ is the class of partitions with parts of size at most $d,$ and $B_d$ is the class of partitions with at most $d$ parts.
If $g(\lambda) = (d,\alpha,\beta)$ then
$$
\begin{aligned}
n(\lambda) &= d^2 + n(\alpha) + n(\beta) \\[+3mm]
k(\lambda) &= d + k(\alpha),
\end{aligned}
$$
so
$$
\begin{aligned}
\prod_{j \geq 0} \frac{1}{1-x^jy}
&= \sum_{\lambda \in \mathcal{Y}} x^{n(\lambda)}y^{k(\lambda)} \\[+4mm]
&= \sum_{d \geq 0} \sum_{\alpha \in A_d}\sum_{\beta \in B_d} x^{d^2 + n(\alpha)+n(\beta)}y^{d + k(\alpha)} \\[+4mm]
&= \sum_{d \geq 0} x^{d^2}y^d \left(\sum_{\alpha \in A_d} x^{n(\alpha)}y^{k(\alpha)}\right)\left(\sum_{\beta \in B_d} x^{n(\beta)}\right) \\[+4mm]
&= \sum_{d \geq 0} x^{d^2}y^d \prod_{i=1}^d \left(\frac{1}{1-x^iy}\right)\prod_{i=1}^d \left(\frac{1}{1-x^i}\right),
\end{aligned}
$$
where the final equation simplified the generating functions for partitions with parts at most $d$ and max part at most $d.$
Partition enumeration, and related areas like the theory of symmetric functions, often fall under the umbrella of algebraic combinatorics, one of the most active areas of modern combinatorics. Our brief treatment here merely scratches the surface of this vast topic.
Problem 1: Write down an expression for the bivariate generating function enumerating the following classes of partitions with respect to size and number of parts.
Partitions in which even parts occur at most twice.
Partitions in which the parts of size at most 20 must be distinct.
Partitions in which the multiplicity of a part $j$ is either 0 or has the same parity (odd or even) as $j.$
Partitions in which every part is either divisible by 3 or even.
Problem 2: Let $A$ be the class of partitions in which no part occurs exactly once, and $B$ be the class of partitions in which every odd part is divisible by 3. Prove that for all $n$ the number of partitions in $A$ of size $n$ equals the number of partitions in $B$ of size $n$ by showing that their generating functions are equal.
Problem 3: Let $A$ be the class of partitions in which each part may occur $0,1,4,$ or $5$ times, and $B$ be the class of partitions which have no parts congruent to 2 modulo 4 and in which parts divisible by 4 occur at most once each. Prove that for all $n$ the number of partitions in $A$ of size $n$ equals the number of partitions in $B$ of size $n$ by showing that their generating functions are equal.
Problem 4: For any $n \in \mathbb{N}$ let $a(n)$ be the number of partitions of size $n$ with an even number of even parts, let $b(n)$ be the number of partitions of $n$ with an odd number of even parts, and let $\text{od}(n)$ be the number of partitions of size $n$ with odd and distinct parts. Show that for all $n \in \mathbb{N},$
$$ a(n) = b(n) + \text{od}(n).$$
Problem 5: For all $n\in\mathbb{N}$ let $\text{pe}(n)$ be the number of partitions of size $n$ with an even number of parts, and $\text{po}(n)$ be the number of partitions of size $n$ with an odd number of parts. Let $\text{od}(n)$ be the number of partitions of size $n$ which have odd and distinct parts. Show that for all $n\in\N,$
$$ \text{pe}(n) - \text{po}(n) = (-1)^n\text{od}(n).$$
Problem 6(a): For a partition $\lambda$ let $a(\lambda)$ denote the number of times 1 occurs as a part of $\lambda.$ Obtain a formula for the generating function
$$ A(x,y) = \sum_{\lambda \in \mathcal{Y}} x^{n(\lambda)}y^{a(\lambda)}. $$
6(b): For a partition $\lambda$ let $b(\lambda)$ denote the number of different sizes of parts that occur in $\lambda$ (for instance, $b(7 6 4 4 2 2 2)=4$). Obtain a formula for the generating function
$$ B(x,y) = \sum_{\lambda \in \mathcal{Y}} x^{n(\lambda)}y^{b(\lambda)}. $$
6(c): Show that for all $n\in\mathbb{N},$ the sum of $a(\lambda)$ over all partitions of size $n$ is equal to the sum of $b(\lambda)$ over all partitions of size $n.$ If needed, you may use the infinite product formula
$$\frac{d}{dz}\prod_{k\geq0} f_k(z) = \sum_{k \geq 0} \frac{d}{dz}f_k(z) \prod_{j \neq k}f_j(z)$$
without proof (this is a generalization of the product formula).
Problem 7: Fix positive integers $m$ and $n.$ A monotonically increasing function from $[n]$ to $[m]$ is any function $\phi:\{1,\dots,n\}\rightarrow\{1,\dots,m\}$ such that $\phi(k) \leq \phi(k+1)$ for all $k=1,2,\dots,n-1.$ Give a bijection between the set of monotonic increasing functions from $[n]$ to $[m]$ and partitions with at most $n$ parts where each part is at most $m-1$ (including the empty partition).
Problem 8: Prove that the generating function $B(q)$ for the number of partitions with at most $a$ parts, all less than or equal to $b,$ is the $q$-binomial coefficient $B(q) = \left[a+b \atop a\right]_q.$
