2
$\begingroup$

"There are 10 distinct balls that can be put into two identical urns such that no urn is empty. How many ways can that be done?"

I know how to do this question when the urns are distinct (its simply 9 choose 1), but when the urns are identical the first urn containing only 1 ball and the second urn containing 9 balls is the same thing as the first containing 9 balls and the second containing 1 ball. How do I take account for all the double counting?

Also, is there a more general formula that can account for any n number of identical urns?

$\endgroup$
1
$\begingroup$

$10$ distinct balls can be put into $2$ distinct urns in $2^{10}$ ways.   In doing so, each such arrangement has a symmetrical case.

Hence there are $2^{10} / 2!$ distinct ways to arrange $10$ distinct balls into $2$ indistinguishable urns. (Which simplifies to $2^9$.)

Generalising this to $k$ distinct balls and $n$ indistinguishable urns gives: $\dfrac{n^k}{n!}$ distinct ways of doing so (or $\dfrac{n^{k-1}}{(n-1)!}$ if you prefer).


With the added condition that neither urn is to be empty, for $10$ balls and $2$ urns we count $\frac{2^{10}}{2!}-1$, and for $k$ balls and $n$ urns the Principle of Inclusion and Exclusion gives:$$\sum_{j=0}^{\min(n,k)-1}\frac{(-1)^j n^{k-j}}{(n-j)!}$$

$\endgroup$
  • $\begingroup$ Just to add on. The number of ways to distribute $n$ distinct balls into $k$ identical boxes such that no box is empty is given by $S(n,k)$ , the Stirling numbers of the second kind. $\endgroup$ – Nicholas Oct 24 '15 at 15:03
  • $\begingroup$ I have to disagree! If $n = 3$, $k = 3$, then your first formula says that there are $9/2$ ways of putting the balls into urns :( $\endgroup$ – R. Suwalski Aug 26 '17 at 8:20

Your Answer

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