TAOCP 7.2.1.4 Exercise 47

Let $p(m)$ denote the number of integer partitions of $m$, with $p(0)=1$.

taocpmathematicsalgorithmsvolume-4hm-medium

Section 7.2.1.4: Generating All Partitions

Exercise 47. ▶ [HM22] [HM22] (A. Nijenhuis and H. S. Wilf, 1975.) The following simple algorithm, based on a table of the partition numbers p(0), p(1), . . . , p(n), generates a random partition of n using the part-count representation c1 . . . cn of (8). Prove that it produces each partition with equal probability. N1. [Initialize.] Set m ←n and c1 . . . cn ←0 . . . 0. N2. [Done?] Terminate if m = 0. N3. [Generate.] Generate a random integer M in the range 0 ≤M < mp(m). N4. [Choose parts.] Set s ←0. Then for j = 1, 2, . . . , and for k = 1, 2, . . . , ⌊m/j⌋, repeatedly set s ←s + kp(m −jk) until s > M. N5. [Update.] Set ck ←ck + j, m ←m −jk, and return to N2. Hint: Step N4, which is based on the identity ∞  j=1 ⌊m/j⌋  k=1 kp(m −jk) = mp(m), chooses each particular pair of values (j, k) with probability kp(m −jk)/(mp(m)).

412 COMBINATORIAL SEARCHING 7.2.1.4

Verified: no
Solve time: 21m39s

Solution

Let $p(m)$ denote the number of integer partitions of $m$, with $p(0)=1$. The algorithm maintains a state $m$ and a part-count vector $c_1,\dots,c_n$, and terminates when $m=0$. Each transition chooses integers $j\ge 1$ and $k\ge 1$ with $jk\le m$, and updates

$$ c_k \leftarrow c_k + j,\qquad m \leftarrow m-jk. $$

A choice $(j,k)$ from state $m$ occurs with probability

$$ \frac{k,p(m-jk)}{m,p(m)}. $$

Write $m_0=n$, and let $m_0,m_1,\dots,m_t=0$ be the successive values of $m$ along a run of the algorithm. At step $i$, the algorithm chooses $(j_i,k_i)$ with probability

$$ \frac{k_i,p(m_i-j_i k_i)}{m_i,p(m_i)}, \qquad m_{i+1}=m_i-j_i k_i. $$

Fix any complete execution path ending at $m_t=0$. Its probability is the product

$$ \prod_{i=0}^{t-1} \frac{k_i,p(m_{i+1})}{m_i,p(m_i)}. $$

Rearranging factors yields

$$ \frac{1}{p(n)}\cdot \prod_{i=0}^{t-1}\frac{k_i}{m_i}\cdot \prod_{i=1}^{t-1} p(m_i)\cdot \frac{1}{\prod_{i=1}^{t-1} p(m_i)} = \frac{1}{p(n)} \prod_{i=0}^{t-1}\frac{k_i}{m_i}. $$

Hence every execution path contributing to a partition has probability equal to $p(n)^{-1}$ times a weight $\prod k_i/m_i$ depending only on the sequence of choices.

It remains to show that, for a fixed final partition $c_1,\dots,c_n$, the total weight

$$ \sum_{\text{paths producing }c_1,\dots,c_n}\ \prod_{i=0}^{t-1}\frac{k_i}{m_i} $$

equals $1$. This is proved by induction on $m$ in the stronger form that for every $m$, every partition of $m$ receives the same total probability.

For $m=0$ there is one empty execution path and one partition, so the probability is $1=p(0)^{-1}$.

Assume every partition of every integer $m'<m$ is produced with probability $1/p(m')$. Fix a partition of $m$. Every execution of the algorithm begins by choosing a pair $(j,k)$ with $jk\le m$, reducing $m$ to $m-jk$, and increasing $c_k$ by $j$. After this first step, the remaining process produces a partition of $m-jk$ whose probability, by the induction hypothesis, is $1/p(m-jk)$.

For a fixed admissible first choice $(j,k)$, the probability contribution of all executions starting with this choice and ending in the given final partition equals

$$ \frac{k,p(m-jk)}{m,p(m)}\cdot \frac{1}{p(m-jk)}=\frac{k}{m,p(m)}. $$

All executions producing the fixed final partition correspond exactly to all ways of decomposing that partition into successive removals of blocks of size $j$ taken $k$ times, and these decompositions partition the multiplicities of the parts uniquely among the steps. Summing over all valid first choices $(j,k)$ compatible with the fixed partition gives total probability

$$ \frac{1}{m,p(m)}\sum k, $$

where the sum is taken over all initial blocks removed in all valid decompositions of the partition.

In any complete decomposition of a partition of $m$, each unit of mass in the part-count representation contributes exactly once to some pair $(j,k)$, and each such contribution increases the corresponding $k$ exactly $k$ times over the decomposition of the $m$ units. Hence the total sum of all $k$ over a full decomposition equals $m$, independent of the partition, since exactly $m$ units are removed in total.

Therefore the total probability assigned to any fixed partition of $m$ is

$$ \frac{m}{m,p(m)}=\frac{1}{p(m)}. $$

By induction, every partition of $m$ is produced with probability $1/p(m)$ for all $m\le n$. In particular, every partition of $n$ is produced with probability $1/p(n)$.

This completes the proof. ∎