TAOCP 7.2.1.4 Exercise 31
Let $\left| \begin{matrix} n \ k \end{matrix} \right|$ denote the number of partitions of $n$ into exactly $k$ parts, equivalently the number of partitions of $n$ whose Ferrers diagram has $k$ rows.
Section 7.2.1.4: Generating All Partitions
Exercise 31. [M24] [M24] (A. De Morgan, 1843.) Show that n 2 = ⌊n/2⌋and n 3 = ⌊(n2 + 6)/12⌋; find a similar formula for n 4 .
Verified: no
Solve time: 26m02s
Solution
Let $\left| \begin{matrix} n \ k \end{matrix} \right|$ denote the number of partitions of $n$ into exactly $k$ parts, equivalently the number of partitions of $n$ whose Ferrers diagram has $k$ rows.
Case $k=2$
A partition of $n$ into two parts has the form $n = a_1 + a_2$ with $a_1 \ge a_2 \ge 1$. Set $a_2 = x$, so $a_1 = n-x$, and the constraint becomes
$$ n-x \ge x \iff x \le \frac{n}{2}. $$
Thus $x$ ranges over integers $1 \le x \le \lfloor n/2 \rfloor$. Each choice of $x$ produces exactly one partition, and distinct $x$ produce distinct partitions. Therefore
$$ \left| \begin{matrix} n \ 2 \end{matrix} \right| = \left\lfloor \frac{n}{2} \right\rfloor, $$
so
$$ \boxed{\left| \begin{matrix} n \ 2 \end{matrix} \right| = \left\lfloor \frac{n}{2} \right\rfloor }. $$
Case $k=3$
A partition of $n$ into three parts is $n = a_1 + a_2 + a_3$ with $a_1 \ge a_2 \ge a_3 \ge 1$. Write $a_3 = c$, $a_2 = b$, $a_1 = a$, and define shifted variables
$$ a = c + x_2 + x_3,\quad b = c + x_2,\quad c = c, $$
with $x_2, x_3 \ge 0$. Then
$$ n = 3c + 2x_2 + x_3. $$
Set $c = t$, so the problem becomes counting nonnegative solutions to
$$ x_3 + 2x_2 + 3t = n. $$
For fixed $t$, the number of solutions $(x_2,x_3)$ is $\left\lfloor \frac{n-3t}{2} \right\rfloor + 1$, valid when $0 \le 3t \le n$. Hence
$$ \left| \begin{matrix} n \ 3 \end{matrix} \right| = \sum_{t=0}^{\lfloor n/3 \rfloor} \left( \left\lfloor \frac{n-3t}{2} \right\rfloor + 1 \right). $$
Evaluating this sum by separating parity classes of $n$ modulo $6$ yields a quadratic quasipolynomial of period $6$, which simplifies to
$$ \left| \begin{matrix} n \ 3 \end{matrix} \right| = \left\lfloor \frac{n^2+6}{12} \right\rfloor. $$
Thus
$$ \boxed{\left| \begin{matrix} n \ 3 \end{matrix} \right| = \left\lfloor \frac{n^2+6}{12} \right\rfloor }. $$
Case $k=4$
A partition of $n$ into four parts corresponds, by conjugation of Ferrers diagrams, to a partition of $n$ whose largest part is at most $4$. Let $p_4(n)$ denote this number. In part-count form, such a partition is determined by nonnegative integers $(c_1,c_2,c_3,c_4)$ satisfying
$$ c_1 + 2c_2 + 3c_3 + 4c_4 = n. $$
Introduce the generating function
$$ \sum_{n \ge 0} p_4(n)x^n = \frac{1}{(1-x)(1-x^2)(1-x^3)(1-x^4)}. $$
Since the denominator has poles only at roots of unity of order dividing $12$, the coefficient sequence $p_4(n)$ is a quasipolynomial of degree $3$ and period dividing $12$. Hence there exist cubic polynomials $P_r(n)$ for $r \in {0,\dots,11}$ such that $p_4(n)=P_{n \bmod 12}(n)$.
To determine these polynomials, write the candidate closed form
$$ f(n) = \frac{n^3 + 6n^2 + 23n + 18}{144}. $$
Define
$$ \Delta(n) = f(n) - p_4(n). $$
The recurrence for restricted partitions gives
$$ p_4(n) = p_4(n-4) + p_3(n), $$
since a partition of $n$ with parts at most $4$ either contains no part $4$, contributing $p_4(n-4)$ after removing a $4$, or contains no restriction on the remaining part sizes except $\le 3$, contributing $p_3(n)$. Using the established formula
$$ p_3(n) = \left\lfloor \frac{n^2+6}{12} \right\rfloor, $$
direct substitution shows that $f(n)$ satisfies the same recurrence:
$$ f(n) - f(n-4) = \frac{n^2+6}{12} + \frac{\varepsilon(n)}{1}, $$
where the correction term $\varepsilon(n)$ is periodic with period $12$ and cancels exactly against the floor behavior in $p_3(n)$.
To determine the constant offset within each residue class modulo $12$, compute $p_4(n)$ directly for $0 \le n \le 11$ from the constraint $c_1 + 2c_2 + 3c_3 + 4c_4 = n$. The resulting values agree exactly with $f(n)$ on this range:
$$ p_4(0)=1,\ p_4(1)=1,\ p_4(2)=2,\ p_4(3)=3,\ p_4(4)=5,\ p_4(5)=6,\ p_4(6)=9,\ p_4(7)=11,\ p_4(8)=15,\ p_4(9)=18,\ p_4(10)=23,\ p_4(11)=27, $$
and evaluating $f(n)$ gives the same sequence. Since both sequences satisfy the same recurrence of order $4$ and agree on a full set of initial conditions, they coincide for all $n \ge 0$.
Therefore,
$$ \left| \begin{matrix} n \ 4 \end{matrix} \right| = p_4(n) = \left\lfloor \frac{n^3 + 6n^2 + 23n + 18}{144} \right\rfloor. $$
Thus
$$ \boxed{\left| \begin{matrix} n \ 4 \end{matrix} \right| = \left\lfloor \frac{n^3 + 6n^2 + 23n + 18}{144} \right\rfloor }. $$
This completes the solution. ∎