Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|improve this question
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|cite|improve this answer
Thanks, shouldn't k start from 1. – Novice Mar 22 '13 at 10:09
@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


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.