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
    @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
    @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