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

  • 0
    I made an edit--changing each "inf" to "$\infty$"--so please let me know if that isn't what was intended.2012-11-05
  • 0
    @CameronBuie Thanks2012-11-05

1 Answers 1

2

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.

  • 0
    26.8.42 and 26.8.43 require that $n$ is at most $k^{1/2}$, right?2012-11-05
  • 0
    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...2012-11-05
  • 0
    @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$.2012-11-05