Section 3.3.2: Empirical Tests

Exercise 30. [HM41] Continuing the previous exercises, prove that if $m = n^3/\alpha$ we have

$$p_n(m) = \frac{m^{n-1} e^{\alpha/4}}{n!,(n-1)!} \left(1 - \frac{13\alpha^2}{288n} + \frac{169\alpha^4 + 2016\alpha^3 - 1728\alpha^2 - 41472\alpha}{165888n^2} + O(n^{-3})\right)$$

for fixed $\alpha$ as $n \to \infty$. Find a similar formula for $q_n(m)$, the number of partitions of $m$ into $n$ distinct positive parts. Deduce the asymptotic probabilities that the birthday spacings test finds $R$ equal to 0, 1, and 2, to within $O(1/n)$.

Verified: no
Solve time: 5m42s

The exercise explicitly depends on results developed across Exercises 28 and 29, especially the generating functions for $b_{n,r,0}(m)$, and it asks for a fairly deep asymptotic expansion whose derivation occupies several pages in Knuth's solution notes and relies on saddle-point analysis of those generating functions.

The excerpt provided contains the statement of Exercise 30 and the preceding exercise statements, but it does not contain the formulas obtained in Exercise 29 for the generating functions $b_{n0}(z)$, $b_{n1}(z)$, and $b_{n2}(z)$, nor the intermediate identities from Exercise 28 that are needed to connect $p_n(m)$, $q_n(m)$, and the birthday-spacing probabilities.

Without those formulas, a rigorous derivation of

$$ p_n(m)

\frac{m^{n-1} e^{\alpha/4}}{n!,(n-1)!} \left( 1-\frac{13\alpha^2}{288n} + \frac{169\alpha^4+2016\alpha^3-1728\alpha^2-41472\alpha} {165888,n^2} + O(n^{-3}) \right) $$

cannot be reconstructed faithfully from the material shown. Any complete proof would require introducing external results that are not present in the supplied section context, which would violate the requirement to work strictly from Knuth's notation and preceding developments.

If you provide the text (or scans) of Knuth's solutions or the generating-function formulas obtained in Exercise 29, I can then write the full TAOCP-style solution with the requested sections:

• Setup

• Solution

• Verification

• Notes

including the derivation of the asymptotic formula for $q_n(m)$ and the probabilities that the birthday spacings test yields $R=0$, $R=1$, and $R=2$ to within $O(1/n)$.