# Approximating Stirling's number of the second kind to allow for large inputs

I'm looking for an approximation for Stirling's number of the second kind, $S_2(n,k)$, which counts the ways to partition a set of $n$ objects into $k$ non-empty subsets:

I need to compute $S_2(n,k)$ for values of $n$ up to $10^6$ and values of $k$ up to $10^5$ or so. Is this possible? Can we bound an error term for the approximation or at least say that the approximation becomes more accurate as $n \to \infty$ and/or $k \to \infty$?

• I made an edit--changing each "inf" to "$\infty$"--so please let me know if that isn't what was intended. – Cameron Buie Nov 5 '12 at 8:59
• @CameronBuie Thanks – Shr Nov 5 '12 at 9:02

• 26.8.42 and 26.8.43 require that $n$ is at most $k^{1/2}$, right? – Shr Nov 5 '12 at 9:54
• Nice links(+1). For a "poor man's" asymptotic beforehand I observed for small n,m (for instance $n,m \lt 200$) that $a(n,m)=\log_2 ({m! \over n!} s_2(n,m))$ produces nice nearly linear patterns and may have good asymptotics nearly linear in n and m. Don't know whether this is helpful anyway... – Gottfried Helms Nov 5 '12 at 10:15
• @Shr: No, on two counts. a) The notation $n=o\left(k^{1/2}\right)$ means not that $n\lt k^{1/2}$ but that $n\lt ck^{1/2}$ for some constant $c$. These are asymptotic results. b) That condition applies only to 26.8.43; it wouldn't make any sense for 26.8.42, since $n$ should be greater than $k$ in that case. In 26.8.42, $k$ is fixed and $n$ goes to $\infty$. – joriki Nov 5 '12 at 10:23