TAOCP 7.2.1.5 Exercise 49

The number \(\xi\) in Eq.

taocpmathematicsalgorithmsvolume-4hm-hard

Section 7.2.1.5: Generating All Set Partitions

Exercise 49. ▶ [HM35] Prove that, for large $n$, the number $\xi$ defined in Eq. (24) is equal to

$$ \ln n-\ln\ln n+\sum_{j,k\ge 0}\left[\begin{array}{c} j+k \ j+1 \end{array}\right]\alpha^j\frac{\beta^k}{k!}, \qquad \alpha=-\frac{1}{\ln n}, \qquad \beta=\frac{\ln\ln n}{\ln n}. $$

Verified: no
Solve time: 2m06s

Setup

The number (\xi) in Eq. (24) of the text is defined by the saddle‑point equation

[ \xi e^{\xi} = n \qquad (\text{or } \xi e^{\xi} = n+1;\text{ the difference is asymptotically negligible}). ]

Taking logarithms gives

[ \xi + \ln \xi = \ln n . ]

We set

[ \alpha = -\frac{1}{\ln n}, \qquad \beta = \frac{\ln\ln n}{\ln n}, ]

and seek an expansion of the form (\xi = \ln n - \ln\ln n + \delta) where (\delta) is expressed as a power series in (\alpha) and (\beta).

Solution

  1. Reduce to an equation for (\delta).
    Substitute (\xi = \ln n - \ln\ln n + \delta) into (\xi + \ln \xi = \ln n):

    [ (\ln n - \ln\ln n + \delta) + \ln(\ln n - \ln\ln n + \delta) = \ln n . ]

    Factor (\ln n) inside the logarithm:

    [ \ln(\ln n - \ln\ln n + \delta) = \ln\ln n + \ln!\left(1 - \frac{\ln\ln n}{\ln n} + \frac{\delta}{\ln n}\right) = \ln\ln n + \ln(1 - \beta - \alpha\delta). ]

    Hence the equation simplifies to

    [ \delta + \ln(1 - \beta - \alpha\delta) = 0 \quad\Longrightarrow\quad \delta = -\ln(1 - \beta - \alpha\delta). \tag{1} ]

  2. Apply Lagrange inversion.
    Let (w = \beta + \alpha\delta). Then (\delta = (w-\beta)/\alpha) and (1) becomes

    [ w = \beta - \alpha\ln(1-w) = \beta + \alpha,\phi(w), \qquad \phi(w) = -\ln(1-w). ]

    We need (\delta = (w-\beta)/\alpha). Treating (\beta) as a parameter and expanding (w) as a power series in (\alpha), the Lagrange inversion formula gives for any function (H)

    [ H(w) = H(\beta) + \sum_{n=1}^{\infty} \frac{\alpha^n}{n!} \left[ \frac{d^{n-1}}{d\beta^{n-1}} \bigl( H'(\beta),\phi(\beta)^n \bigr) \right]. ]

    Choose (H(w) = (w-\beta)/\alpha); then (H(\beta)=0) and (H'(\beta)=1/\alpha). Hence

    [ \delta = \sum_{n=1}^{\infty} \frac{\alpha^{n-1}}{n!}, \frac{d^{n-1}}{d\beta^{n-1}} \phi(\beta)^n = \sum_{j=0}^{\infty} \frac{\alpha^j}{(j+1)!}, \frac{d^j}{d\beta^j} \phi(\beta)^{j+1}. \tag{2} ]

  3. Express the derivatives using Stirling numbers of the first kind.
    The generating function of the unsigned Stirling numbers (\left[{n\atop k}\right]) is

    [ \phi(\beta)^k = \bigl(-\ln(1-\beta)\bigr)^k = k! \sum_{n=k}^{\infty} \left[{n\atop k}\right] \frac{\beta^n}{n!}. ]

    For (k = j+1),

    [ \phi(\beta)^{j+1} = (j+1)! \sum_{n=j+1}^{\infty} \left[{n\atop j+1}\right] \frac{\beta^n}{n!}. ]

    Differentiating (j) times:

    [ \frac{d^j}{d\beta^j} \phi(\beta)^{j+1} = (j+1)! \sum_{n=j+1}^{\infty} \left[{n\atop j+1}\right] \frac{n!}{(n-j)!},\frac{\beta^{n-j}}{n!} = (j+1)! \sum_{n=j+1}^{\infty} \left[{n\atop j+1}\right] \frac{\beta^{n-j}}{(n-j)!}. ]

    Set (k = n-j) ((k \ge 1)); the term for (k=0) is zero because (\left[{j\atop j+1}\right]=0). Thus

    [ \frac{d^j}{d\beta^j} \phi(\beta)^{j+1} = (j+1)! \sum_{k=1}^{\infty} \left[{j+k\atop j+1}\right] \frac{\beta^k}{k!} = (j+1)! \sum_{k=0}^{\infty} \left[{j+k\atop j+1}\right] \frac{\beta^k}{k!}. \tag{3} ]

  4. Substitute (3) into (2).

    [ \delta = \sum_{j=0}^{\infty} \alpha^j \sum_{k=0}^{\infty} \left[{j+k\atop j+1}\right] \frac{\beta^k}{k!} = \sum_{j,k\ge 0} \left[{j+k\atop j+1}\right] \alpha^j,\frac{\beta^k}{k!}. ]

  5. Recover (\xi).

    [ \xi = \ln n - \ln\ln n + \delta = \ln n - \ln\ln n + \sum_{j,k\ge 0} \left[{j+k\atop j+1}\right] \alpha^j,\frac{\beta^k}{k!}. ]

    This is exactly the required formula. ∎

Verification

The most failure‑prone step is the identification of the derivative of (\phi(\beta)^{j+1}) with the Stirling numbers. We verify it independently for the first few orders by directly expanding the implicit equation (\delta = -\ln(1-\beta-\alpha\delta)).

Expand (\delta) as a series in (\alpha) and (\beta):

[ \delta = \beta + \frac{\beta^2}{2} + \frac{\beta^3}{3} + \cdots + \alpha\left(\beta + \beta^2 + \frac{3}{2}\beta^3 + \cdots\right) + \alpha^2\left(\frac{1}{2}\beta + \cdots\right) + O(\alpha^3). ]

From the Stirling‑number formula:

  • (j=0): (\left[{k\atop 1}\right] = (k-1)!) gives (\sum_{k\ge1} \frac{\beta^k}{k} = -\ln(1-\beta)), matching the (\alpha^0) part.
  • (j=1): (\left[{k+1\atop 2}\right] = k!,H_k) gives (\alpha \sum_{k\ge1} H_k\beta^k = \alpha,\frac{-\ln(1-\beta)}{1-\beta}), which equals (\alpha(\beta + \beta^2 + \frac{3}{2}\beta^3 + \cdots)), matching the (\alpha^1) part.
  • (j=2): (\left[{k+2\atop 3}\right] = \frac{(k+1)!}{2}\bigl(H_k^2 - H_k^{(2)}\bigr)) yields the (\alpha^2) terms, agreeing with the direct expansion of (\delta).

The coefficients match exactly, confirming the correctness of the derivation.