Stirling numbers of the second kind with max cardinality

Question

We know that Stirling numbers of the second kind is the number of ways to partition a set of $n$ elements into $m$ nonempty sets.

My question is what's the number ways if the max cardinality of all the partitioned sets is $k$.

Answer 1

I you want for an exact closed formula, I suspect that it would be fairly complex, if it can be found - perhaps by generating functions.

If you are interested in approximate/asymptotic formulas for large values of $n, m$, (and $n/m \gtrsim 3$) you can try the following trick.

There are in total $m^n$ ways of placing distinct objects in $m$ distinct cells But we want the subset that consist of those configurations that have from 1 to $k$ objects in each cell.

To estimate the relative size of this subset, we notice that the experiment of placing randomly $n$ distinct objects (equiprobably) in $m$ distinct cells is asymptotically equivalent to throwing $m$ independent Poisson variables with mean $\lambda = n/m$. The probability that this configuration fits our restricted subset is

$ \displaystyle \left( \sum_{j=1}^k e^{-\lambda} \frac{\lambda^j}{j!} \right)^m $

From this we can estimate our desider number, multiplying this expression by $m^n$ ,and dividing by $m!$ if we want to consider the cells as undistinguishable, as Stirling numbers do. So

$\displaystyle S_k(n,m) \approx \frac{m^n}{m!} \left( e^{-\lambda} \sum_{j=1}^k \frac{\lambda^j}{j!} \right)^m $

with $\lambda = n/m$.

BTW setting $k = \infty$ we have an approximation of the standard Stirling numbers of the second kind (further simplified-approximated by the Stirling approximation of factorials).

$\displaystyle S(n,m) \approx \left( \frac{m}{e} \right)^{n-m} \; \frac{ \left( e^{\lambda} -1 \right)^m} {\sqrt{2 \pi \; m}} $

Answer 2

I Googled restricted partitions stirling and the third hit was http://dlmf.nist.gov/26.9

Looks pretty thorough.