# 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

Let $a_m(n,k)$ be the number of set partitions of $n$ elements into $m$ non-empty partitions with maximum size $k$ each. Then the following recurrence relation is valid for $k\geq 1$: \begin{align*} a_k(n+1,m)&=ma_k(n,m)+a(n,m-1)-\binom{n}{k}a(n-k,m-1)\qquad n,m\geq 1 \end{align*} with boundary conditions \begin{align*} a_k(n,m)&=a_k(n,m)=0\, \qquad\qquad n<m,n>km\\ a_k(n,n)&=1\, \qquad\qquad\qquad\qquad\quad n\geq 0\\ a_k(n,1)&= \begin{cases} 1&\qquad\qquad\qquad\quad 1\leq n\leq k\\ 0&\qquad\qquad\qquad\quad n>k \end{cases}\\ a_k(0,m)&=a_k(n,0)=0\qquad\qquad\ \, n,m>0\\ \end{align*}

A proof can be found in this answer.