TAOCP 7.2.1.4 Exercise 38

Section 7.2.1.4: Generating All Partitions

Exercise 38. [M20] [M20] Given positive integers l and m, what generating function enumerates partitions that have exactly m parts, and largest part l? (See Eq. (51).)

Verified: no
Solve time: 19m15s

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. ∎