Stirling numbers of the second kind with max cardinality

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

-
 You mean "what's the number OF ways IF we bound the cardinality" ? At least 'k'? – leonbloy Feb 11 '11 at 15:30 I have modified the description of the question. – Fan Zhang Feb 11 '11 at 15:52 "max cardinality of all the partitioned sets is k" and keeping min cardinality = 1 ? – leonbloy Feb 11 '11 at 15:53 Every set must be non-empty, and the max one is k, while the min one must >= 1. – Fan Zhang Feb 11 '11 at 15:56

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

-

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

Looks pretty thorough.

-
 Hi Taylor: Thank you for your answer. – Fan Zhang Feb 11 '11 at 17:27