2
$\begingroup$

5 balls of different colours are to be placed in 3 boxes of different sizes. Each box can hold all 5 balls. The number of ways in which we can place the balls in the boxes so that no box remains empty.

My attempt:-

First choose 3 balls to be placed in 3 boxes so that none of them remain empty in ${{5}\choose{3}}\cdot3! = 60$ ways.

Now remaining 2 balls can go into any of the 3 boxes in $3\cdot3 = 9$ ways.

Total number of ways $= 60\cdot9 = 540$.

Where am I going wrong ?

$\endgroup$
  • 1
    $\begingroup$ When you place the last two balls, you are over counting. Your answer better be less than $243$. $\endgroup$ – Donald Splutterwit Oct 1 '17 at 10:51
3
$\begingroup$

There are three choices for each of the five balls. Hence, if there were no restrictions, the balls could be placed in the boxes in $3^5$ ways. From these, we must exclude those distributions in which one or more of the boxes is empty.

There are $\binom{3}{1}$ ways to exclude one of the boxes and $2^5$ ways to distribute the balls to the remaining boxes. Hence, there are $$\binom{3}{1}2^5$$ ways to distribute the balls so that one of the boxes is empty.

However, we have counted those distributions in which two of the boxes are empty twice, once for each of the ways we could have designated one of the empty boxes as the excluded box. We only want to exclude them once, so we must add these cases back.

There are $\binom{3}{2}$ ways to exclude two of the boxes and one way to place all the balls in the remaining box.

Hence, the number of ways the balls can be distributed so that no box is left empty is $$3^5 - \binom{3}{1}2^5 + \binom{3}{2}1^5$$ by the Inclusion-Exclusion Principle.

Where am I going wrong?

You count each distribution in which one box receives three balls and the others receive one three times, once for each way you could place one of those three balls first.

You count each distribution in which two of the boxes receive two balls and the other box receives one four times, once for each way you could place one of the two balls in each of the two boxes with two balls first.

Three balls in one box and one ball in each of the others: There are three ways to choose which box receives three balls, $\binom{5}{3}$ ways to choose which three balls are placed in that box, and $2!$ ways to distribute the remaining balls. Hence, there are $$\binom{3}{1}\binom{5}{3}2!$$ ways to distribute the balls so that three balls are placed in the same box.

Two boxes receives two balls and one box receives one ball: There are three ways to choose which box receives only one ball and five ways to choose the ball that is placed in that box. There are $\binom{4}{2}$ ways to choose which two of the remaining four balls are placed in the smaller of the two remaining boxes. The other two balls must be placed in the remaining box. Hence, there are $$\binom{3}{1}\binom{5}{1}\binom{4}{2}$$ ways to distribute the balls so that two boxes receive two balls and one box receives one.

Observe that $$\binom{3}{1}\binom{5}{3}2! + \binom{3}{1}\binom{5}{1}\binom{4}{2} = 3^5 - \binom{3}{1}2^5 + \binom{3}{2}1^5$$

Since you counted distributions in which one box receives three balls and the others receive one three times and distributions in which two boxes receive two balls and the other receives one four times, you obtained $$3\binom{3}{1}\binom{5}{3}2! + 4\binom{3}{1}\binom{5}{1}\binom{4}{2} = \binom{5}{3} \cdot 3! \cdot 3^2$$

$\endgroup$
  • $\begingroup$ Even though I know inclusion principle, I am not able to figure out when to apply it for permutation sums. Is there anyway to get a grip over it ? $\endgroup$ – Zephyr Oct 1 '17 at 11:26
  • 1
    $\begingroup$ In this case, you could avoid using the Inclusion-Exclusion Principle, as the second method I used demonstrates. Until you have applied the IEP to several problems, it can be tricky to figure out what you have to exclude. For instance, if you have to separate four red balls in an arrangement, you need to understand that two pairs of red balls could mean two separate pairs involving four red balls or two overlapping pairs formed by three consecutive red balls. I suggest applying the IEP to problems that you know how to solve in another way to test whether you are doing it right. $\endgroup$ – N. F. Taussig Oct 1 '17 at 11:34
2
$\begingroup$

To apply Inclusion-Exclusion, we let $S(i)$ be the set of arrangements where box $i$ is empty. Then $$ \begin{align} N(j) &=\sum_{|A|=j}\left|\,\bigcap_{i\in A} S(i)\,\right|\\ &=\underbrace{\ \ \ \binom{3}{j}\ \ \ }_{\substack{\text{number of}\\\text{ways to choose}\\\text{$j$ empty boxes}}}\underbrace{\ (3-j)^5\ \vphantom{\binom{3}{j}}}_{\substack{\text{number of}\\\text{maps into}\\\text{$3-j$ boxes}}} \end{align} $$ Inclusion-Exclusion says the number of arrangements with no boxes empty is $$ \begin{align} \sum_{j=0}^3(-1)^{j-0}\binom{j}{0}N(j) &=\sum_{j=0}^3(-1)^j\binom{3}{j}(3-j)^5\\ &=3^5-3\cdot2^5+3\cdot1^5-1\cdot0^5\\[12pt] &=150 \end{align} $$

$\endgroup$
1
$\begingroup$

We want to put $5$ distinguished balls into $3$ distinguished boxes, so our configuration space is of size $3^5$. We need to ensure each box has at least one ball. There are sufficiently few partitions of $5$ into $3$ parts that we can list them and calculate their multiplicities ... \begin{array}{l|l} Partition & Multiplicity \\ \hline (5,0,0) & 3 \\ (4,1,0) & 30 \\ (3,2,0) & 60 \\ (3,1,1) & \color{blue}{60} \\ (2,2,1) & \color{blue}{90} \\ \end{array} So there will be $\color{blue}{150}$ configurations.

$\endgroup$
  • $\begingroup$ Thank you for the answer. Can you tell me why is my approach wrong ? Why is it over counting ? If possible, can we arrive at the same answer using my approach? $\endgroup$ – Zephyr Oct 1 '17 at 10:37

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.