5
$\begingroup$

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:

( http://en.wikipedia.org/wiki/Stirling_numbers_of_the_second_kind#Simple_identities )

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$?

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

See the asymptotic approximations 26.8.42 and 26.8.43 here. That page also gives further references. See also this article and this slide show.

$\endgroup$
  • $\begingroup$ 26.8.42 and 26.8.43 require that $n$ is at most $k^{1/2}$, right? $\endgroup$ – Shr Nov 5 '12 at 9:54
  • $\begingroup$ 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... $\endgroup$ – Gottfried Helms Nov 5 '12 at 10:15
  • $\begingroup$ @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$. $\endgroup$ – joriki Nov 5 '12 at 10:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.