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 have $n$ distinct colored balls and $m$ similar bags( with the condition $n \geq m$ ). In how many ways can we place these $n$ balls into given $m$ bags?

My Attempt: For the moment, if we assume all the balls are of same color - we are counting partitions of $n$ into at most $m$ parts( since each bag looks same - it is not a composition of $n$, just a partition ).

But, given that each ball is unique, for every partition of $n$ ----> $\lambda : \{\lambda_1,\lambda_2, \cdots \lambda_m\}$, we've $\binom{n}{\lambda_1} * \binom{n-\lambda_1}{\lambda_2}*\binom{n-\lambda_1-\lambda_2}{\lambda_3}* \cdots * \binom{\lambda_{m-1}+\lambda_{m}}{\lambda_{m-1}}*\binom{\lambda_m}{\lambda_m}$ ways of arranging the balls into $m$ given baskets. We need to find this out for every partition of $n$ into $m$ parts.

Am i doing it right?

I'm wondering whether there is any closed form formula for this( i know that enumerating the number of partitions of $n$ is also complex. But, i don't know, the stated problem seemed simple at the first look. But, it isn't? Am i right? ).

P.S. I searched for this question thinking that somebody might have asked it earlier. But, couldn't find it. Please point me there if you find it.

share|improve this question

1 Answer 1

up vote 1 down vote accepted

This is counting the maps from an $n$-set (the balls) to an $m$-set (the bags), up to permutations of the $m$-set (as the bags are similar). This is just one of the problems of the twelvefold way, and looking at the appropriate section you find that the result can only be expressed as a sum of Stirling numbers of the second kind, namely $\sum_{k=0}^m\genfrac\{\}0{}nk$. The $k$ in fact represents the number of nonempty bags here.

share|improve this answer
    
Thanks, shouldn't k start from 1. –  Novice Mar 22 '13 at 10:09
1  
@Novice: No $k$ should start from $0$ so that the formula will remain true for the case $n=0$. In fact $\genfrac\{\}0{}n0=\delta_{n,0}=0^n$. –  Marc van Leeuwen Mar 22 '13 at 10:46

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.