TAOCP 7.2.1.5 Exercise 55
In the asymptotic analysis of the Bell numbers \( \varpi_n \), the saddle-point method is applied to the generating function \(\Pi(z)=e^{e^z-1}\).
Section 7.2.1.5: Generating All Set Partitions
Exercise 55. [HM20] Suggest a good way to compute the number $\beta$ needed in (43).
Verified: no
Solve time: 6m03s
Solution
In the asymptotic analysis of the Bell numbers ( \varpi_n ), the saddle-point method is applied to the generating function (\Pi(z)=e^{e^z-1}). The dominant contribution comes from the point where the derivative of the exponent vanishes, leading to the saddle-point equation
[ \beta e^{\beta} = n \qquad (\text{or } n+1\text{, depending on the precise formulation}). ]
The number (\beta) needed in equation (43) is the unique positive solution of this equation. A good way to compute (\beta) is to use the Lambert (W) function: (\beta = W(n)). If the Lambert (W) function is not available, Newton's method on (f(\beta)=\beta e^{\beta}-n) converges quadratically. The iteration is
[ \beta_{k+1} = \beta_k - \frac{\beta_k e^{\beta_k} - n}{e^{\beta_k}(\beta_k+1)} = \frac{\beta_k^2 + n e^{-\beta_k}}{\beta_k+1}. ]
An excellent initial guess is (\beta_0 = \ln n - \ln\ln n), which follows from taking logarithms of (\beta e^{\beta}=n). For very large (n) the simpler fixed-point iteration (\beta_{k+1} = \ln n - \ln\beta_k) also converges rapidly.
\boxed{\text{Use Newton's method on } \beta e^{\beta} = n \text{ with initial guess } \beta_0 = \ln n - \ln\ln n.}