The Stirling number of the second kind, $S(n,k)$, is defined to be the number of ways one can partition an $n$-element set into exactly $k$ subsets. The sum over the values for $k$ from 1 to $n$ becomes the Bell number. One asymptotic approximation for $S(n,k)$ is $\frac{k^n}{k!}$.

I just wonder, what is the asymptotic approximations of partitioning an $n$-element set into at most $k$ subsets. That is,

$\sum_{k=1}^{p} S(n,k)$,

the sum over the values for $k$ from 1 to $p$, where $p$ is a constant? Is there any tighter approximation than $\frac{p^n}{(p-1)!}$?

  • $\begingroup$ "The asymptotic approximation for $S(n,k)$ is..." That's not "the" but just one asymptotic approximation, there are many others (depending on how $n,k$ grow). See eg mathoverflow.net/questions/162764/… or math.stackexchange.com/questions/229534/… Hence you should not ask for "the asymptotic approximation", but instead tell us how $n,k$ grow. For example, do both tend to infinity with constant $n /k $, or what? $\endgroup$ – leonbloy Feb 26 '16 at 13:45
  • $\begingroup$ Thanks. I have edited the question. For your second point, since $p$ is a constant (which is not proportional to n), therefore, the $\lim_{n\to\infty} n/k = \infty$. $\endgroup$ – wei wang Feb 26 '16 at 23:20

Your Answer

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

Browse other questions tagged or ask your own question.