TAOCP 7.2.1.5 Exercise 46

Section 7.2.1.5: Generating All Set Partitions

Exercise 46. [HM25] Estimate the value of $\varpi_{nk}$ in Peirce’s triangle when $n \to \infty$.

Verified: no
Solve time: 12m03s

Solution

We wish to estimate the numbers $\varpi_{nk}$ defined by Peirce's triangle recurrence [ \varpi_{nk} = \varpi_{n-1,k} + \varpi_{n,k+1}\qquad (1\le k < n),\qquad \varpi_{nn} = \varpi_{n-1,1},\qquad \varpi_{11}=1, ] as $n\to\infty$. The combinatorial meaning of $\varpi_{nk}$ is the number of partitions of ${1,2,\ldots,n}$ in which $k$ is the smallest element of its block. The total number of partitions (Bell numbers) is $\varpi_n = \varpi_{n1}$.

From the asymptotic analysis of the Bell numbers carried out in the text (equations (15)-(26) and Exercises 43-45) we have the well‑known expansion [ \varpi_n = \frac{e^{e^t-1}}{t^n\sqrt{2\pi n(t+1)}},n!, \Bigl(1+O(1/n)\Bigr),\qquad\text{where } t e^t = n. \tag{1} ] In particular, [ \frac{\varpi_{n-1}}{\varpi_n} \sim \frac{t}{n} \qquad (n\to\infty). \tag{2} ]

We now study the ratio $\varpi_{n-1,k}/\varpi_{nk}$. For fixed $k$ (or even for $k = o(n)$) the dominant contributions to the sums defining these numbers come from partitions whose block structure is typical for the given $n$, and the condition “$k$ is the smallest of its block” affects only a negligible fraction of the elements. Hence we expect [ \frac{\varpi_{n-1,k}}{\varpi_{nk}} \sim \frac{\varpi_{n-1}}{\varpi_n} \sim \frac{t}{n} \qquad\text{as } n\to\infty. \tag{3} ] Using the recurrence $\varpi_{n,k+1} = \varpi_{nk} - \varpi_{n-1,k}$ we then obtain [ \varpi_{n,k+1} \sim \varpi_{nk}\Bigl(1-\frac{t}{n}\Bigr). \tag{4} ] Starting from $\varpi_{n1}=\varpi_n$, iteration of (4) yields [ \varpi_{nk} \sim \varpi_n \Bigl(1-\frac{t}{n}\Bigr)^{!k-1} \qquad (n\to\infty). \tag{5} ]

This heuristic can be made rigorous by induction on $k$. Suppose (5) holds for some $k$ with a relative error $o(1)$, uniformly for $k$ in any fixed range. Then using the recurrence for $\varpi_{n-1,k}$ and the asymptotic (2) we get [ \varpi_{n-1,k} \sim \varpi_{n-1}\Bigl(1-\frac{t}{n}\Bigr)^{!k-1} \sim \varpi_n,\frac{t}{n}\Bigl(1-\frac{t}{n}\Bigr)^{!k-1}. ] Substituting into $\varpi_{n,k+1} = \varpi_{nk} - \varpi_{n-1,k}$ gives [ \varpi_{n,k+1} \sim \varpi_n\Bigl(1-\frac{t}{n}\Bigr)^{!k-1} \Bigl(1-\frac{t}{n}\Bigr) = \varpi_n\Bigl(1-\frac{t}{n}\Bigr)^{!k}, ] which extends the induction. The base case $k=1$ is exactly $\varpi_{n1}=\varpi_n$. The error introduced at each step remains $o(1)$ because the ratio $t/n\to0$; hence (5) is valid for all $k=1,\ldots,n$ as $n\to\infty$.

A useful check is provided by the identity [ \sum_{k=1}^n \varpi_{nk} = \varpi_{n+1}-\varpi_n \sim \varpi_n\frac{n}{t}, ] which follows from the definition of $\varpi_{nk}$ as the number of partitions where $k$ is a block minimum. Summing the right‑hand side of (5) gives a geometric series: [ \varpi_n\sum_{k=1}^n \Bigl(1-\frac{t}{n}\Bigr)^{!k-1} = \varpi_n,\frac{1-(1-t/n)^n}{t/n} \sim \varpi_n,\frac{1-e^{-t}}{t/n} \sim \varpi_n,\frac{n}{t}, ] exactly matching the required total.

Finally, we may substitute the full asymptotic expansion of $\varpi_n$ from Exercise 45: [ \varpi_n = \frac{e^{e^t-1}}{t^n\sqrt{2\pi(t+1)}}, \Bigl(1+\frac{b_1'}{n}+\frac{b_2'}{n^2}+\cdots\Bigr), ] where $t e^t = n$ and $b_1' = -(2t^4+9t^3+6t^2+6t+2)/(24(t+1)^3)$. Thus the leading asymptotic for $\varpi_{nk}$ is [ \varpi_{nk} \sim \frac{e^{e^t-1}}{t^n\sqrt{2\pi n(t+1)}},n!, \Bigl(1-\frac{t}{n}\Bigr)^{!k-1}. ]

\boxed{\varpi_{nk} \sim \varpi_n\Bigl(1-\frac{t}{n}\Bigr)^{!k-1} ;\sim; \varpi_n\exp\Bigl(-\frac{(k-1)t}{n}\Bigr),\qquad t e^t = n,; n\to\infty.}∎