Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
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

1 Answer 1

up vote 1 down vote accepted

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.

share|improve this answer
    
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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