1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thanks, shouldn't k start from 1. $\endgroup$ – Satish Thulva Mar 22 '13 at 10:09
  • 1
    $\begingroup$ @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$. $\endgroup$ – Marc van Leeuwen Mar 22 '13 at 10:46

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.