3
$\begingroup$

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

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

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

$\endgroup$
3
$\begingroup$

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

Looks pretty thorough.

$\endgroup$
  • $\begingroup$ Hi Taylor: Thank you for your answer. $\endgroup$ – Fan Zhang Feb 11 '11 at 17:27
0
$\begingroup$

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.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.