TAOCP 7.2.1.4 Exercise 46
Let $S$ be a multiset of positive integers, and write its distinct values in increasing order as 1 \le b_1 < b_2 < \cdots < b_t, with multiplicities $m_1, m_2, \ldots, m_t$.
Section 7.2.1.4: Generating All Partitions
Exercise 46. [M20] [M20] In the text’s analysis of Algorithm P, which is larger, T ′ 2(n) or T ′′ 2 (n)?
Verified: no
Solve time: 8m36s
Solution
Let $S$ be a multiset of positive integers, and write its distinct values in increasing order as
$$ 1 \le b_1 < b_2 < \cdots < b_t, $$
with multiplicities $m_1, m_2, \ldots, m_t$. A submultiset of $S$ is determined uniquely by choosing, for each $i$, an integer $0 \le k_i \le m_i$. Hence the total number of submultisets equals
$$ \prod_{i=1}^t (m_i + 1). $$
The definition of a perfect partition of $n$ requires that this number equals $n+1$, so
$$ \prod_{i=1}^t (m_i + 1) = n+1. $$
Each submultiset $T \subseteq S$ produces a sum
$$ \sigma(T) = \sum_{x \in T} x. $$
The second requirement states that these sums are exactly $0,1,\ldots,n$, each occurring once. In particular, the mapping $T \mapsto \sigma(T)$ is a bijection between all submultisets of $S$ and the integers $0$ through $n$.
Let
$$ f(x) = \prod_{i=1}^t (1 + x^{b_i} + x^{2b_i} + \cdots + x^{m_i b_i}) $$
be the generating polynomial for submultiset sums. The coefficient of $x^k$ in $f(x)$ equals the number of submultisets with sum $k$. The perfect partition condition is equivalent to
$$ f(x) = 1 + x + x^2 + \cdots + x^n = \frac{1-x^{n+1}}{1-x}. $$
Structure of admissible weights
Consider the smallest positive element $b_1$. If $b_1 \ge 2$, then all nonempty submultiset sums are multiples of $b_1$, so integer $1$ cannot be represented, contradicting completeness. Hence $b_1 = 1$.
Assume inductively that the set of representable sums forms a contiguous interval $[0, M]$. Adding a new value $b$ with multiplicity $m$ extends the representable interval without gaps only if
$$ b \le M+1. $$
Otherwise $M+1$ is not representable. If $b \le M$, then different choices of copies of $b$ would create repeated representations inside the interval, contradicting uniqueness. Hence necessarily
$$ b = M+1. $$
Thus the weights are forced to be constructed sequentially so that each new distinct value is exactly one greater than the maximum representable sum so far.
Let $S$ be ordered increasingly. Define $S_k$ as the prefix up to value $b_k$. Then the reachable sums from $S_k$ form exactly the interval
$$ [0, \Sigma_k], $$
where $\Sigma_k$ is the total sum of elements in $S_k$. The previous argument implies the recurrence
$$ b_{k+1} = \Sigma_k + 1. $$
Therefore the distinct values are uniquely determined by their multiplicities.
Determination of multiplicities
Let $c_i = m_i + 1$. Then
$$ \prod_{i=1}^t c_i = n+1. $$
The construction above shows that once multiplicities are fixed, the weights are forced. The sum constraint determines $n$ as
$$ n = \sum_{i=1}^t m_i b_i. $$
To minimize the number of elements, one must minimize $\sum m_i$ subject to $\prod c_i = n+1$, since $m_i = c_i - 1$. Hence we minimize
$$ \sum_{i=1}^t (c_i - 1) = \left(\sum_{i=1}^t c_i\right) - t $$
subject to fixed product.
For fixed product $n+1$, this is minimized when the factorization uses factors as large as possible, since replacing $ab$ by $a,b$ increases $(a-1)+(b-1)$.
Hence optimal solutions correspond to writing
$$ n+1 = 2^{e_1} 2^{e_2} \cdots 2^{e_t} $$
with maximal aggregation into large powers of two, i.e. the binary factor structure of $n+1$.
Extremal construction
Write $n+1$ in binary and repeatedly apply the greedy factor grouping that merges factors when possible into larger powers of two. This yields a canonical factorization
$$ n+1 = \prod_{k \ge 0} (2^{k+1})^{\alpha_k}, $$
corresponding to multiplicities
$$ m_k = 2^{k+1} - 1 \quad \text{repeated } \alpha_k \text{ times}. $$
Each block of size $2^{k+1}-1$ contributes a chain of weights
$$ 2^k, 2^k, \ldots, 2^k $$
with $2^{k+1}-1$ copies, which generates all sums in the interval $[0, (2^{k+1}-1)2^k]$ without gaps and with uniqueness. Successive blocks then concatenate by the forcing rule $b_{k+1} = \Sigma_k + 1$, preserving contiguity up to $n$.
Minimality
Any representation with a factor $c_i$ not a power of two can be refined into smaller factors whose total contribution to $\sum m_i$ strictly decreases while preserving the product constraint. Hence any non-binary factorization of $n+1$ yields a strictly larger total number of elements.
Therefore minimality is achieved precisely by the binary-saturated factorization above.
Final answer
The perfect partitions of $n$ with fewest elements are obtained by choosing multiplicities $m_i$ so that $m_i + 1$ are powers of two whose product is $n+1$, and assigning weights inductively by $b_1=1$, $b_{k+1} = \sum_{i \le k} m_i b_i + 1$. Equivalently, one groups the factorization of $n+1$ into powers of two as much as possible; each factor $2^k$ corresponds to a block of $2^k - 1$ equal elements.
$$ \boxed{\text{Minimal perfect partitions correspond to the binary factorization structure of } n+1.} $$
This completes the solution. ∎