0
$\begingroup$

All information needed is covered in the title.

Suppose I have 9 different balls and 3 different urns. I want to put the 9 balls into 3 different urns. Calculated the number of ways to put the 9 balls so that every urn has at least one ball at last.

At first, I calculated in the following way, $$\binom{9}{3}\times 3^6 = 61236$$

$\binom{9}{3}$ is to ensure every urn get one ball, then put the left balls into the 3 urns. However, the right answer is 18150.

Then I realize that there is some repetition in the counting. For example, the situation that I put ball 6 into urn 1 (in the first step), and then put ball 7 into urn 1 is the same as I first put ball 7 into urn 1 and then put ball 6 into the same urn. The question is how to remove the double counting? Is there another way to get the number of ways?

$\endgroup$

2 Answers 2

2
$\begingroup$

You can build this from the bottom up. There are seven unique partitions of nine, with three numbers in the partition:

  • 1 + 1 + 7 = 9 (This has 216 options)
  • 1 + 2 + 6 = 9 (This has 1,512 options)
  • 1 + 3 + 5 = 9 (This has 3,024 options)
  • 1 + 4 + 4 = 9 (This has 1,890 options)
  • 2 + 2 + 5 = 9 (This has 2,268 options)
  • 2 + 3 + 4 = 9 (This has 7,560 options)
  • 3 + 3 + 3 = 9 (This has 1,680 options)

Here is an example of how to calculate the above:

$ {9 \choose 1} \cdot {8 \choose 1} \cdot {7 \choose 7} = 9 \cdot 8 \cdot 1 = 72 $ (Choose 1 from the group of 9 for group 1, then choose 1 from the remaining 8 for group 2, and put all of the remaining 7 in the final group)

Think about why this is multiplied by 3. (How many permutations of 1,1,7 are there?)

Rinse and repeat, and the total adds up to 18150

$\endgroup$
0
0
$\begingroup$

Disregarding the condition that the urns are not allowed to be empty we find $3^{9}=19683$ possibilities.

There are $3$ urns, hence $3$ ways to put all balls in the same urn.

There are $\binom{3}{2}=3$ ways to choose two specific urns.

After making that choice there are $2^{9}-2$ ways to put all balls in these chosen urns in such a way that both urns will be not empty.

That gives $3\left(2^{9}-2\right)=1530$ possibilities.

So what remains are $19683-3-1530=18150$ possibilities.


More structurally with inclusion/exclusion and symmetry:

$$|\Omega|-|A\cup B\cup C|=$$$$3^9-|A|-|B|-|C|+|A\cap B|+|A\cap C|+|B\cap C|-|A\cap B\cap C|=$$$$3^9-3|A|+3|A\cap B|-|A\cap B\cap C|=$$$$3^9-3\cdot2^{9}+3\cdot1^9-0=$$$$18150$$

This where:

$\Omega=\left\{ 1,2,3\right\} ^{9}$ i.e. the set of all possibilities (i.e. disregarding the condition).

$A=\left\{ \langle\omega_{1},\dots,\omega_{9}\rangle\in\Omega\mid\forall i\;\omega_{i}\neq1\right\} $ i.e. the set where urn $1$ is empty.

$B=\left\{ \langle\omega_{1},\dots,\omega_{9}\rangle\in\Omega\mid\forall i\;\omega_{i}\neq2\right\} $ i.e. the set where urn $2$ is empty.

$C=\left\{ \langle\omega_{1},\dots,\omega_{9}\rangle\in\Omega\mid\forall i\;\omega_{i}\neq3\right\} $ i.e. the set where urn $3$ is empty.

$\endgroup$

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.