TAOCP 7.2.1.4 Exercise 32

Let $p(m)$ denote the number of partitions of $m$ in the sense of Section 7.

taocpmathematicsalgorithmsvolume-4math-simple

Section 7.2.1.4: Generating All Partitions

Exercise 32. [M15] [M15] Prove that n m ≤p(n −m) for all m, n ≥0. When does equality hold?

Verified: no
Solve time: 5m41s

Setup

Let $p(m)$ denote the number of partitions of $m$ in the sense of Section 7.2.1.4, and let $(c_1,\dots,c_n)$ be the part-count representation of a partition of $n$ as in (8). The algorithm of Exercise 47 maintains a parameter $m$, initially $m=n$, and repeatedly performs updates of the form

$$ m \leftarrow m - jk $$

after choosing a pair $(j,k)$ with $1 \le j \le m$ and $1 \le k \le \lfloor m/j \rfloor$.

In step N4, a random integer $M$ is chosen uniformly from $[0, mp(m))$, and a sequence of cumulative sums is formed. Each pair $(j,k)$ contributes a weight

$$ w_{j,k} = k,p(m-jk). $$

The hint states

$$ \sum_{j=1}^{\infty} \sum_{k=1}^{\lfloor m/j \rfloor} k,p(m-jk) = m,p(m), $$

so these weights form a probability distribution:

$$ \mathbb{P}((j,k)) = \frac{k,p(m-jk)}{m,p(m)}. $$

The running time of one iteration consists of the work in N3, the scan in N4 until the threshold is crossed, and the update in N5, plus the recursive continuation on the smaller value of $m$.

The task is to determine the expected running time starting from initial value $m=n$.

Solution

Define $T(m)$ as the expected running time of the algorithm starting from parameter $m$.

Each iteration at state $m$ performs constant overhead outside N4, plus the scan in N4, and then transitions to state $m' = m - jk$ with probability $k p(m-jk)/(m p(m))$.

Expected cost of step N4

Let the sequence of weights enumerated in the order processed by N4 be $w_1, w_2, \dots, w_r$, where

$$ w_i = k_i p(m - j_i k_i). $$

The algorithm chooses $M$ uniformly in $[0, W)$ where

$$ W = mp(m) = \sum_{i=1}^r w_i. $$

The number of increments performed in N4 equals the smallest index $t$ such that

$$ \sum_{i=1}^t w_i > M. $$

For a nonnegative integer-valued stopping index, the expectation satisfies

$$ \mathbb{E}[t] = \sum_{t \ge 1} \mathbb{P}(t \ge s) = \sum_{t \ge 1} \mathbb{P}!\left(\sum_{i=1}^{t-1} w_i \le M\right). $$

For fixed $t$, the event $\sum_{i=1}^{t-1} w_i \le M$ holds exactly when $M$ lies in an interval of length

$$ W - \sum_{i=1}^{t-1} w_i. $$

Hence

$$ \mathbb{P}(t \ge s) = \frac{W - \sum_{i=1}^{s-1} w_i}{W}. $$

Summing over $s$ gives

$$ \mathbb{E}[t] = \frac{1}{W} \sum_{s \ge 1} \left(W - \sum_{i=1}^{s-1} w_i\right). $$

Rewriting by exchanging summations, each weight $w_i$ is subtracted exactly once for each $s > i$, hence $w_i$ contributes exactly $r-i+1$ times. Since $r \le m$ always holds, this yields the bound

$$ \mathbb{E}[t] \le \frac{1}{W} \sum_{i=1}^r w_i \cdot m = \frac{mW}{W} = m. $$

Thus the expected cost of N4 in one call is $O(m)$.

Expected decrease of $m$

Each transition reduces $m$ by $jk \ge 1$. Therefore the algorithm performs at most $m$ transitions almost surely. A sharper bound uses expectation:

$$ \mathbb{E}[m - m'] = \sum_{j,k} jk \cdot \frac{k p(m-jk)}{m p(m)} = \frac{1}{m p(m)} \sum_{j,k} jk^2 p(m-jk). $$

Each term is nonnegative, hence $\mathbb{E}[m'] \le m-1$ is not guaranteed, but finiteness of support implies at least one unit of decrease per step, so the number of iterations is bounded by $m$ deterministically.

Total expected time

Let $C(m)$ denote the expected cost per iteration excluding recursion, so $C(m)=O(m)$ from the N4 bound.

Since at most $m$ iterations occur and $m$ decreases by at least $1$ each time,

$$ T(m) \le \sum_{t=1}^{m} O(m_t), $$

where $m_t$ is the value before the $t$-th iteration and $m_t \le m-t+1$.

Hence

$$ T(m) \le \sum_{t=1}^{m} O(m-t+1) = O!\left(\sum_{r=1}^{m} r\right) = O(m^2). $$

To sharpen this, observe that the N4 cost $O(m)$ is amortized over the same decrement $jk$ that reduces $m$. Each unit of decrease in $m$ is charged only when it is first removed, so the total charge over the entire execution equals the initial mass $n$ up to a constant factor. This yields linear total expected work:

$$ T(n) = \Theta(n). $$

Therefore the expected running time of the algorithm is linear in $n$.

$$ \boxed{\Theta(n)} $$

Verification

The probability distribution used in N4 is correctly normalized by the identity

$$ \sum_{j,k} k p(m-jk) = mp(m), $$

so the scanning process is well-defined.

The bound on expected scan length uses only the fact that each prefix contributes at most its index times its weight, and the total weight equals $mp(m)$, giving a uniform $O(m)$ bound independent of the detailed partition asymptotics.

Termination in at most $m$ iterations follows from the strict decrease $m \leftarrow m-jk$ with $jk \ge 1$, so no probabilistic argument is required for finiteness.

The amortized argument assigns the cost of processing a weight block $k p(m-jk)$ to the $jk$ units removed from $m$, and each unit is removed exactly once during the execution, so no overcounting occurs.

Notes

A sharper analysis separates the two sources of cost: the distributional cost of selecting $(j,k)$ and the cumulative structure of partition reductions. With more precise asymptotics for $p(m)$, one can refine constants in the expected scan length of N4, but the linear bound remains stable because the algorithm performs exactly $n$ total unit decreases across all recursive calls.