# asymptotic approximation for the sum of stirling numbers of the second kind

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)!}$?

• "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? – leonbloy Feb 26 '16 at 13:45
• 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$. – wei wang Feb 26 '16 at 23:20