Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
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

2 Answers 2

up vote 2 down vote accepted

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

share|improve this answer

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

Looks pretty thorough.

share|improve this answer
    
Hi Taylor: Thank you for your answer. –  Fan Zhang Feb 11 '11 at 17:27

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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