+0

# Counting

0
91
1

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 5, 2023

#1
+195
0

We can use the principle of inclusion-exclusion to count the number of ways to distribute the balls among the boxes.

First, let's count the total number of ways to distribute the 10 indistinguishable balls among the 8 distinguishable boxes, without any restrictions. This is equivalent to finding the number of non-negative integer solutions to the equation:

x1 + x2 + x3 + x4 + x5 + x6 + x7 + x8 = 10

where xi represents the number of balls in the ith box. By stars and bars, the number of solutions is:

(10 + 8 - 1) choose (8 - 1) = 816 ways

Now let's count the number of ways to distribute the balls such that no box is empty. We can use the principle of inclusion-exclusion to count the number of solutions in which one or more boxes are empty.

The number of solutions in which box 1 is empty is equivalent to finding the number of non-negative integer solutions to the equation:

x2 + x3 + x4 + x5 + x6 + x7 + x8 = 10

where xi represents the number of balls in the ith box (excluding box 1). By stars and bars, the number of solutions is:

(10 + 7 - 1) choose (7 - 1) = 330 ways

Similarly, there are 330 ways to distribute the balls such that box 2 is empty, and so on, for a total of 8 × 330 = 2640 ways.

However, we have double-counted the solutions in which two or more boxes are empty. To count these solutions, we can use the same approach as before.

The number of solutions in which boxes 1 and 2 are empty is equivalent to finding the number of non-negative integer solutions to the equation:

x3 + x4 + x5 + x6 + x7 + x8 = 10

where xi represents the number of balls in the ith box (excluding boxes 1 and 2). By stars and bars, the number of solutions is:

(10 + 6 - 1) choose (6 - 1) = 200 ways

Similarly, there are 200 ways to distribute the balls such that boxes 1 and 3 are empty, and so on, for a total of 28 × 200 = 5600 ways.

We have now counted all the solutions in which one or more boxes are empty, but we have subtracted the solutions in which two or more boxes are empty twice. So we need to add these solutions back in.

The number of solutions in which boxes 1 and 2 are empty, and boxes 3 and 4 are empty is equivalent to finding the number of non-negative integer solutions to the equation:

x5 + x6 + x7 + x8 = 10

where xi represents the number of balls in the ith box (excluding boxes 1, 2, 3, and 4). By stars and bars, the number of solutions is:

(10 + 4 - 1) choose (4 - 1) = 84 ways

Similarly, there are 84 ways to distribute the balls such that boxes 1 and 3 are empty, boxes 1 and 4 are empty, and so on, for a total of 70 × 84 = 5880 ways.

Therefore, the total number of ways to distribute the balls among the boxes such that at least one box is empty is:

816 - 2640 + 5880 = 14056

So there are 14056 ways to distribute the 10 indistinguishable balls among the 8 distinguishable boxes, if at least one of the boxes must be empty.

Mar 5, 2023