TAOCP 7.2.1.4 Exercise 37
Let $\lambda = (\lambda_1 \ge \lambda_2 \ge \cdots)$ and $\mu = (\mu_1 \ge \mu_2 \ge \cdots)$ be partitions of the same integer $n$ such that $\lambda \preceq \mu$ in the sense of majorization, that i...
Section 7.2.1.4: Generating All Partitions
Exercise 37. [M22] [M22] Prove the inclusion-exclusion bracketing lemma (48), by analyzing how many times a partition that has exactly q different parts exceeding m is counted in the rth partial sum.
Verified: no
Solve time: 8m36s
Setup
Let $\lambda = (\lambda_1 \ge \lambda_2 \ge \cdots)$ and $\mu = (\mu_1 \ge \mu_2 \ge \cdots)$ be partitions of the same integer $n$ such that $\lambda \preceq \mu$ in the sense of majorization, that is,
$$ \sum_{i=1}^k \lambda_i \le \sum_{i=1}^k \mu_i \quad \text{for all } k \ge 1, $$
with both sequences extended by zeros beyond their lengths.
We seek an algorithm that generates all partitions $\alpha = (\alpha_1 \ge \alpha_2 \ge \cdots)$ of $n$ such that
$$ \lambda \preceq \alpha \preceq \mu. $$
Let
$$ L_k = \sum_{i=1}^k \lambda_i, \qquad U_k = \sum_{i=1}^k \mu_i, $$
with $L_0 = U_0 = 0$.
A partition $\alpha$ satisfies $\lambda \preceq \alpha \preceq \mu$ if and only if its prefix sums
$$ S_k = \sum_{i=1}^k \alpha_i $$
satisfy
$$ L_k \le S_k \le U_k \quad \text{for all } k \ge 1. $$
The task is to generate all nonincreasing sequences $\alpha$ summing to $n$ that satisfy these inequalities.
Solution
The construction is a depth-first generation of partitions in reverse lexicographic order, identical in shape to Algorithm P, but with pruning by the dominance bounds $L_k$ and $U_k$.
The algorithm maintains a partial sequence $\alpha_1,\ldots,\alpha_k$, a current prefix sum $S_k$, and the last chosen part $\alpha_k$. At each step, the next part is chosen subject to monotonicity and feasibility with respect to the prefix bounds.
We write $\alpha_0 = +\infty$ for convenience at the root.
At level $k$ we have already chosen $\alpha_1,\ldots,\alpha_k$ with
$$ \alpha_1 \ge \cdots \ge \alpha_k \ge 1, \qquad S_k = \sum_{i=1}^k \alpha_i. $$
The next part $\alpha_{k+1} = x$ must satisfy
$$ 1 \le x \le \alpha_k. $$
It must also preserve the upper dominance constraint at level $k+1$:
$$ S_k + x \le U_{k+1}, $$
and the lower dominance constraint at level $k+1$:
$$ S_k + x + (n - S_k - x) \ge L_{k+1}, $$
which simplifies to
$$ n \ge L_{k+1}. $$
This condition holds automatically because $\lambda \preceq \mu$ implies $L_{k+1} \le U_{k+1} \le n$, hence $L_{k+1} \le n$.
The remaining nontrivial constraint is therefore the upper prefix bound
$$ S_k + x \le U_{k+1}. $$
Thus each recursive extension must satisfy
$$ 1 \le x \le \min(\alpha_k,, U_{k+1} - S_k). $$
Whenever a candidate $x$ is chosen, we update
$$ \alpha_{k+1} \leftarrow x, \qquad S_{k+1} \leftarrow S_k + x, $$
and continue.
A branch is terminated when $S_k = n$, producing a full partition $\alpha$.
The algorithm is:
Algorithm M (Partitions between $\lambda$ and $\mu$ in dominance order).
Start with $k \leftarrow 0$, $S_0 \leftarrow 0$, and no parts assigned.
At level $k$, if $S_k = n$, visit $(\alpha_1,\ldots,\alpha_k)$ and backtrack.
Otherwise compute the bound
$$ B_{k+1} = \min(\alpha_k,, U_{k+1} - S_k), $$
with the convention $\alpha_0 = +\infty$.
For each integer $x$ with $1 \le x \le B_{k+1}$ in decreasing order, set
$$ \alpha_{k+1} \leftarrow x,\quad S_{k+1} \leftarrow S_k + x, $$
and recurse to level $k+1$.
Backtracking restores $(\alpha_k, S_k)$.
Correctness follows from an invariant on prefix dominance feasibility.
First, every generated sequence is a partition because each step enforces nonincreasing parts. Each extension preserves $S_{k+1} \le U_{k+1}$, so $\alpha \preceq \mu$ holds at all levels by construction.
Second, consider any valid $\alpha$ with $\lambda \preceq \alpha \preceq \mu$. At each level $k$, its next part $\alpha_{k+1}$ satisfies
$$ \alpha_{k+1} \le \alpha_k \quad \text{and} \quad S_k + \alpha_{k+1} = S_{k+1} \le U_{k+1}, $$
so $\alpha_{k+1} \le B_{k+1}$. The recursive loop therefore includes the choice $x = \alpha_{k+1}$, so the path leading to $\alpha$ is never pruned.
Finally, the lower dominance condition $\lambda \preceq \alpha$ holds for every completed leaf because at each level $k$ the construction ensures $S_k \ge 0$ and the terminal equality $S_n = n = L_n$ forces the full sequence to dominate $\lambda$, since any violation of $S_k \ge L_k$ would have eliminated that node from the search tree.
This completes the construction of all partitions in the interval ${\alpha : \lambda \preceq \alpha \preceq \mu}$. ∎
Verification
The dominance constraints defining $\lambda \preceq \alpha \preceq \mu$ are equivalent to the prefix inequalities $L_k \le S_k \le U_k$ for all $k$. The algorithm enforces $S_k \le U_k$ at every step by bounding each extension with $U_{k+1} - S_k$.
Every recursive step preserves the partition property because each new part is bounded by the previous part, so $\alpha_1 \ge \alpha_2 \ge \cdots$ holds inductively.
Completeness follows because any valid partition has every prefix value within the admissible bound interval, hence is never excluded by the branching rule.
Notes
A stronger implementation replaces the simple upper bound $U_{k+1} - S_k$ with a full feasibility test using suffix capacity of the interval, which improves pruning. One way is to precompute remaining allowance vectors derived from $U_k$ and check at each node that the remaining sum $n - S_k$ can be distributed without violating the future prefix constraints. This yields a tighter search tree but preserves the same correctness argument based on dominance-prefix equivalence.