+0

# counting

+1
28
2

In how many ways can you distribute 10 indistinguishable balls among 8 distinguishable boxes, if at least one of the boxes must be empty?

Mar 21, 2023

#2
0

To solve this problem, we can use the principle of inclusion-exclusion.

First, we find the total number of ways to distribute the balls without any restrictions. This is equivalent to finding the number of ways to put 10 indistinguishable balls into 8 distinguishable boxes, which is given by the formula:

$${10 + 8 - 1 \choose 8 - 1} = {17 \choose 7} = 19,448$$

Next, we find the number of ways to distribute the balls such that no box is empty. This is equivalent to finding the number of ways to put 10 indistinguishable balls into 8 distinguishable boxes such that each box has at least one ball. We can think of this as a stars and bars problem with the additional constraint that each box must have at least one star (ball). Using the stars and bars formula, we get:

$${10 - 1 \choose 8 - 1} = {9 \choose 7} = 36$$

However, we are interested in the number of ways such that at least one box is empty. To find this, we use the principle of inclusion-exclusion. Let A be the event that box 1 is empty, B be the event that box 2 is empty, and so on up to H for box 8. Then the number of ways to distribute the balls such that at least one box is empty is given by:

$$\sum_{i=1}^{8} (-1)^{i-1} \binom{8}{i} {10 - i - 1 \choose 8 - 1}$$

where the $(-1)^{i-1}$ term comes from the alternating signs in the inclusion-exclusion formula.

Using this formula, we get:

$$\sum_{i=1}^{8} (-1)^{i-1} \binom{8}{i} {10 - i - 1 \choose 8 - 1} = 19,448 - 36\binom{8}{1} + \binom{8}{2} {1 \choose 7} - \binom{8}{3} {2 \choose 7} + \cdots + (-1)^{8-1} \binom{8}{8} {2 \choose 7}$$

Simplifying this expression gives:

$$19,448 - 8\times36 + 28\times0 - 56\times0 + 70\times0 - 56\times0 + 28\times0 - 8\times0 + 1\times0 = 19,064$$

Therefore, the number of ways to distribute 10 indistinguishable balls among 8 distinguishable boxes, if at least one of the boxes must be empty, is 19,064. Subaru Net

Mar 21, 2023
edited by Amandahertzog  Mar 21, 2023