Completely effective error bounds for Stirling Numbers of the first and second kind via Poisson Approximation

Richard Arratia, Stephen DeSalvo

Published 2014-04-11, updated 2015-06-17Version 2

We provide completely effective error estimates for Stirling numbers of the first and second kind, denoted by $s(n,m)$ and $S(n,m)$, respectively. These bounds are useful for values of $m \geq n - O(\sqrt{n})$. An application of our Theorem 5 yields, for example, \[ s(10^{12},\ 10^{12}-2\times 10^6)/10^{35664464} \in [ 1.87669, 1.876982 ], \] \[ S(10^{12},\ 10^{12}-2\times 10^6)/10^{35664463} \in [ 1.30121, 1.306975 ]. \] The bounds are obtained via Poisson approximation, using an interpretation of Stirling numbers as the number of ways of placing non-attacking rooks on a chess board. As a corollary to Theorem 5, summarized in Proposition 1, we obtain two simple and explicit asymptotic formulas, one for each of $s(n,m)$ and $S(n,m)$, for the parametrization $m = n - t\, n^a$, $0 \leq a \leq \frac{1}{2}.$ These asymptotic formulas agree with the ones originally observed by Moser and Wyman in the range $0<a<\frac{1}{2}$, and they also agree with a recent asymptotic expansion by Louchard for $\frac{1}{2}<a < 1$, hence filling the gap at $a = \frac{1}{2}$: \begin{equation*} |s(n,m)| \sim \binom{\binom{n}{2}}{t\, n^a} e^{ - \frac{2}{3} t^2 n^{2a-1}}, \end{equation*} \begin{equation*} S(n,m) \sim \binom{\binom{n}{2}}{t\, n^a} e^{ - \frac{4}{3} t^2 n^{2a-1}}. \end{equation*} Finally, we generalize to rook and file numbers.