Large $n,k$ asymptotics for Stirling numbrs of the first kind $\left[ \matrix{n\\k}\right]$

Question

$\left[ \matrix{n\\k}\right]$ is the notation for Stirling numbers of the first kind. This is the number of distinguishable ways to break$n$ objects into $k$ cycles. (Warning - Mathematica's StirlingS1 function is $(-1)^{n-k}$ times the usual definition of $\left[ \matrix{n\\k}\right]$.

I wanted to find an asymptotic expansion for $\left[ \matrix{n\\k}\right]$, good for general (large) $n$ and $k$. This seems to be a lot too tough, so I will stick to my original motivating problem:

Find the large-$n$ asymptotic behavior of $\left[ \matrix{2n\\n}\right]$.

We can, by the recursion relation, immediately see that $\left[ \matrix{2n\\n}\right]$ grows at least as fast as $(n-1)!$, and in fact it is easier to work with the behavior of $$S(n) = \frac1{n!}\left[ \matrix{2n\\n}\right]$$

The term ratio $$ R[n] \equiv \frac{ \left[ \matrix{2n+2\\n+1}\right] } {(n+1) \left[ \matrix{2n\\n}\right]} $$ seems to go to as $$ R[n] \approx \exp\left( 2.2805 + \frac{0.0103}{\log n} - 0.0011 \log\left( \frac{\log 2}{\log n}\right) + O(1/n) \right) $$ and since this was obtained by working with modest values of $n$ (around $500$) it is plausible that the last two coefficients are actually zero and the term ratio goes to a constant with order $1/n$ corrections. Still, this does not get me to the desired asymptotic form for $\left[ \matrix{2n+2\\n+1}\right]$.

I appear to be stuck.

Answer 1

The exponential generating function for the signed Stirling numbers of the first kind $s(n, k)$ is $\ln^k(x + 1)/k!$, so we have $$s(n, k) = \frac {n!} {k!} [z^n] \ln^k(z + 1) = \frac {n!} {2 \pi i k!} \int_{|z| = \epsilon} \frac {\ln^k(z + 1)} {z^{n + 1}} dz.$$ We want to apply the steepest descent method to $e^{n \phi(z)}/z$ with $\phi(z) = -2 \ln z + \ln \ln(z + 1)$. The stationary point of $\phi$ is at $$\alpha = -\frac 1 {2 W_{-1} {\left( -\frac 1 {2 \sqrt e} \right)}} - 1,$$ so we need to take a branch of $\phi$ which is analytic at $\alpha$. Since $(2 n)!/n! \sim \sqrt 2 \, (4 n/e)^n$, we get the asymptotic estimate $$(-1)^n s(2 n, n) \sim -\frac {\sqrt 2} {2 \pi i \alpha} \sqrt {-\frac {2 \pi} {\phi''(\alpha) n}} \left( -4 n e^{\phi(\alpha) - 1} \right)^{\! n}, \quad n \to \infty.$$ The negative square root corresponds to going through the saddle point in the direction $-i$. The result is the same as in Claude's answer.

Answer 2

If you look at sequence $A187646$ in $OEIS$ (have a look here), you will find much more than a very good asymptotics proposed by Vaclav Kotesovec in 2011. It write $$\color{blue}{\left[ \matrix{2n\\n}\right]\sim\frac 1 {\sqrt {2\pi}}\left(\frac{2n}{e(1-z) z}\right)^n \sqrt{\frac{1-z}{n (2 z-1)}}}$$ where $z=0.715331862959\cdots$ is the solution of equation $$z=2 (z-1) \log (1-z)\implies \color{blue}{z=1+\frac{1}{2 W_{-1}\left(-\frac{1}{2 \sqrt{e}}\right)}}$$

Computing for a few values $$\left( \begin{array}{ccc} n & \text{approximation} & \text{exact} \\ 10 & 3.88957\times 10^{14} & 3.81922\times 10^{14} \\ 20 & 1.09365\times 10^{36} & 1.08361\times 10^{36} \\ 30 & 6.64905\times 10^{59} & 6.60815\times 10^{59} \\ 40 & 1.28216\times 10^{85} & 1.27623\times 10^{85} \\ 50 & 3.19507\times 10^{111} & 3.18322\times 10^{111} \\ 60 & 6.08632\times 10^{138} & 6.06750\times 10^{138} \\ 70 & 6.27422\times 10^{166} & 6.25758\times 10^{166} \\ 80 & 2.74026\times 10^{195} & 2.73389\times 10^{195} \\ 90 & 4.22408\times 10^{224} & 4.21536\times 10^{224} \\ 100 & 1.99489\times 10^{254} & 1.99118\times 10^{254} \end{array} \right)$$

The relative error is $<1$% for $n>18$, $<0.1$% for $n>187$, $<0.01$% for $n>1866$.

Based on the asymptotics, $$R[n] = \frac{ \left[ \matrix{2n+2\\n+1}\right] } {(n+1) \left[ \matrix{2n\\n}\right]}$$ for large values of $n$ $$\log(R[n])=\log \left(\frac{2}{(1-z) z}\right)-\frac{1}{n}+\frac{7}{12 n^2}+O\left(\frac{1}{n^3}\right)$$

which makes $$\lim_{n\to \infty } \, R[n]=-\frac{8 \Big[W_{-1}\left(-\frac{1}{2 \sqrt{e}}\right)\Big]^2}{2 W_{-1}\left(-\frac{1}{2 \sqrt{e}}\right)+1}\approx 9.82163$$ while your approximation would lead to $e^{2.2805}=9.78157$.

Approximate and rigorous calculations of $R[n]$ give the following values $$\left( \begin{array}{ccc} n & \text{approximation} & \text{exact} \\ 100 & 9.724466302 & 9.724645076 \\ 200 & 9.772786357 & 9.772831597 \\ 300 & 9.789008963 & 9.789029152 \\ 400 & 9.797142176 & 9.797153556 \\ 500 & 9.802029138 & 9.802036430 \\ 600 & 9.805290049 & 9.805295117 \\ 700 & 9.807620710 & 9.807624436 \\ 800 & 9.809369495 & 9.809372348 \\ 900 & 9.810730127 & 9.810732383 \\ 1000 & 9.811818928 & 9.811820755 \end{array} \right)$$

Edit

Based on the exact values given in the above table and using quick and dirty nonlinear regression :

• for your model $$R[n]=\exp\left(a+\frac{b}{\log (n)}+c \log \left(\frac{\log (2)}{\log (n)}\right) \right)$$ ($SSQ=2.256\times 10^{-6}$) the results are $$\begin{array}{clclclclc} \text{} & \text{Estimate} & \text{Standard Error} & \text{Confidence Interval} \\ a & +2.522185 & 0.008303 & \{+2.501868,+2.542502\} \\ b & -0.519993 & 0.015108 & \{-0.556962,-0.483025\} \\ c & +0.071063 & 0.002672 & \{+0.064524,+0.077601\} \\ \end{array}$$

• for the model $$R[n]=\exp\left(a+\frac{b}{n}+\frac{c}{n^2} \right)$$ ($SSQ=3.705\times 10^{-14}$) the results are $$\begin{array}{clclclclc} \text{} & \text{Estimate} & \text{Standard Error} & \text{Confidence Interval} \\ a & +2.284587 & 7.28 \times 10^{-9} & \{+2.284587,+2.284587\} \\ b & -0.999960 & 4.29 \times 10^{-6} & \{-0.999971,-0.999950\} \\ c & +0.759431 & 3.89 \times 10^{-4} & \{+0.758478,+0.760383\} \\ \end{array}$$