TAOCP 7.2.1.4 Exercise 44
Let $f_{l,m}(n)$ denote the number of partitions of $n$ having exactly $m$ parts and largest part equal to $l$.
Section 7.2.1.4: Generating All Partitions
Exercise 44. ▶ [M22] [M22] How many partitions of n have their two smallest parts equal?
Verified: no
Solve time: 8m37s
Solution
Let $f_{l,m}(n)$ denote the number of partitions of $n$ having exactly $m$ parts and largest part equal to $l$. Let the ordinary generating function be
$$ F_{l,m}(x) = \sum_{n \ge 0} f_{l,m}(n)x^n. $$
Every such partition can be written uniquely in the form
$$ n = a_1 + a_2 + \cdots + a_m, $$
with
$$ a_1 = l, \qquad l = a_1 \ge a_2 \ge \cdots \ge a_m \ge 1. $$
Hence
$$ n - l = a_2 + \cdots + a_m, $$
and $(a_2,\dots,a_m)$ is a partition into exactly $m-1$ parts, each at most $l$.
Introduce variables marking part size and number of parts. For each part size $i \in {1,\dots,l}$, a part of size $i$ contributes weight $x^i$, and we mark the number of parts by an auxiliary variable $y$. The standard bivariate generating function for partitions with parts at most $l$ is
$$ \prod_{i=1}^{l} \frac{1}{1 - yx^i}. $$
Expanding, the exponent of $y$ records the number of parts and the exponent of $x$ records the sum of parts.
The condition that the remainder $(a_2,\dots,a_m)$ has exactly $m-1$ parts corresponds to extracting the coefficient of $y^{m-1}$. Thus the generating function for the remainder is
$$ [y^{m-1}] \prod_{i=1}^{l} \frac{1}{1 - yx^i}. $$
Since the first part contributes a fixed factor $x^l$, the desired generating function is
$$ F_{l,m}(x) = x^l ,[y^{m-1}] \prod_{i=1}^{l} \frac{1}{1 - yx^i}. $$
This expression enumerates exactly those partitions with $m$ parts and largest part $l$, because fixing $a_1=l$ forces all remaining parts to lie in ${1,\dots,l}$ and enforces the total number of remaining parts to be $m-1$.
Thus,
$$ \boxed{F_{l,m}(x) = x^l ,[y^{m-1}] \prod_{i=1}^{l} \frac{1}{1 - yx^i}}. $$
This completes the solution. ∎