Question

5 balls are to be placed in 3 boxes. Each box can hold all 5 balls. In how many different ways can we place the balls so that no box remains empty if, (i) balls & boxes are different (iii) balls are different but boxes are identical (ii) balls are identical but boxes are different (iv) balls as well as boxes are identical

Answer 1

Answer on Question #56762 – Math – Combinatorics | Number Theory

5 balls are to be placed in 3 boxes. Each box can hold all 5 balls. In how many different ways can we place the balls so that no box remains empty if,

(i) balls & boxes are different

(ii) balls are different but boxes are identical

(iii) balls are identical but boxes are different

(iv) balls as well as boxes are identical

Solution

(i) balls and boxes are different.

Because

$$5 = 2 + 2 + 1, \ 5 = 3 + 1 + 1,$$

we can have the following two distributions:

(a) 3-1-1: one box gets three balls and the remaining two boxes get one ball each.

The number of ways to distribute the balls for this case is

$$3 * 2 * C _ {5} ^ {3} = 60,$$

where 3 is the number of ways to choose which box gets 3 balls (we have 3 boxes, thus 3 choices for that), $C_5^3 = \binom{5}{3} = \frac{5!}{3!2!}$ is the number of ways to choose which 3 balls out of 5 will go to that box, and 2 is the number of ways to distribute the remaining 2 balls in the remaining two boxes.

(b) 2-2-1: one box gets one ball and the remaining two boxes get two balls each. The number of ways to distribute the balls for this case is

$$3 * 5 * C _ {4} ^ {2} = 90,$$

where 3 is the number of ways to choose which box gets 1 balls (we have 3 boxes, thus 3 choices for that), 5 is the number of ways to choose which ball out of 5 will go to that box, and $C_4^2 = \frac{4!}{2!2!}$ is the number of ways to choose which 2 balls out of

4 balls left will go to the second box (the remaining 2 balls will naturally go to the third box).

Thus, the total number of required ways is

$$N = 60 + 90 = 150.$$

(ii) balls are different but boxes are identical.

When the boxes are identical, the distributions of 1, 1, 3 balls, 1, 3, 1 balls and 3, 1, 1 balls will be treated as identical distributions. Number of ways of distributing in this manner is

$$\frac{5!}{1!1!3!} = 20.$$

When the boxes are identical, the distributions of 1, 2, 2 balls, 2, 1, 2 balls and 2, 2, 1 balls will be treated as identical distributions. Number of ways of distributing in this manner is

$$\frac{5!}{2!2!1!} = 30.$$

Thus, the total number of required ways is

$$N = 20 + 30 = 50.$$

(iii) balls are identical but boxes are different.

First, consider the case, where empty box is allowed.

Total number of ways of distributing $r$ identical balls in $n$ different boxes is the same as the number of $r$-combinations of $n$ items, repetitions are allowed.

It is

$$C(n + r - 1, r) = \binom{n + r - 1}{r} = \binom{n + r - 1}{n - 1}.$$

Now consider the case, where no box is empty.

First take $n = 3$ balls and put one ball in each box. This leaves

$r - n = 5 - 3 = 2$ balls to distribute with no restrictions as in the previous case.

Thus, there are

$$\binom{(r - n) + n - 1}{n - 1} = \binom{r - 1}{n - 1} = \binom{5 - 1}{3 - 1} = \binom{4}{2} = \frac{4!}{2!2!} = \frac{4 \cdot 3}{2} = \frac{12}{2} = 6$$

ways.

**(iv)** balls as well as boxes are identical.

It is the number of partitions of $r$ into $n$ parts, that is, write $r$ as a sum of natural numbers, order is unimportant.

For $r = 5$, $n = 3$ the partitions are

$$5 = 2 + 2 + 1,$$ $$5 = 3 + 1 + 1.$$

The partition $2 + 2 + 1$ says put 2 balls in the first box, 2 balls in the second box and one ball in the third box. The partition $3 + 1 + 1$ says put 3 balls in the first box, 1 ball in the second box and 1 ball in the third box.

We have only 2 partitions, hence the total number of ways is 2.

Answer: (i) 150; (ii) 50; (iii) 6; (iv) 2.

www.AssignmentExpert.com