Distinct objects in distinct boxes

Question

I have come across a question and it is -

How many ways are there to distribute 17 distinct objects into 7 distinct boxes with at least two empty boxes?

There are two ways I am following to answer this question.

1st METHOD : Two boxes that would remain empty is to be chosen in C(7, 2)=21 ways. Corresponding to this, each of the 17 objects have 5 boxes to choose from. Hence, 17 objects can be placed in the five boxes in 5^17 ways. So, total number of ways = 21 * (5^17)

2nd METHOD : First, I find the total number of ways in which 17 objects can be placed in 7 boxes - this gives (7^17) ways, since each object can go to any of the 7 boxes. Next, from these total number of ways, I want to subtract the count of those ways in which all boxes are occupied and also in which only 1 box is empty while rest are occupied.

The number of ways in which none of the boxes is empty is C(17, 7) * 7! * (7^10). In this, C(17, 7) is for choosing 7 objects each of which will be placed in one of the empty boxes and the 7! is because there are 7! Ways to place the chosen 7 objects in the boxes. Once the 7 boxes are filled with 7 objects, the remaining 10 objects can be placed in any of the 7 boxes in (7^10) ways.

Now I can go forward to calculate those ways in which only 1 box is empty, but I wouldn't do this because there happens to be a problem in my approach that I followed till now. The problem is total count calculated in para 1 is less than the count in which no boxes are empty, as is calculated in para 2. However it should be the opposite case.

Please help me know where I am going wrong in solving this question.

Thank you.

Answer 1

With method 1, you are double counting. E.g. the way of putting all 17 objects into the first box, is double counted ${ 6 \choose 2 } $ times (corresponding to picking any 2 of the remaining 6 boxes)

With method 2, the following statement isn't true:

The number of ways in which none of the boxes is empty is C(17, 7) * 7! * (7^10).

You are picking a "base" item in each non-empty box, but there isn't a way to do so. This results in a bunch of double counting, like the case where the first 11 objects are in bin 1 and the rest are individually in each bin. There are many ways to pick the "base" item in the first box.

---

In general, you will need to use the Principle of Inclusion and Exclusion

Answer 2

There are $7^{17}$ ways to distribute the balls to the boxes without restriction. Let us count how many of those are "bad" because there were zero or only one empty boxes. To do so, we use Stirling Numbers of the Second Kind.

The Stirling Number of the Second Kind, $\left\{\begin{matrix}n\\k\end{matrix}\right\}$, counts the number of ways of partitioning an $n$-element set into $k$ unlabeled non-empty parts. Multiplying the result by $k!$ then gives the number of ways of partitioning an $n$-element set into $k$ labeled non-empty parts.

The number of ways to distribute the balls such that there are no empty boxes is then:

$$\left\{\begin{matrix}17\\7\end{matrix}\right\}7!$$

The number of ways to distribute the balls such that there is exactly one empty box, first pick which of the boxes was to remain empty, then do the same as before:

$$7\cdot \left\{\begin{matrix}17\\6\end{matrix}\right\}6!$$

We get then as a final count:

$$7^{17} - \left\{\begin{matrix}17\\7\end{matrix}\right\}7! - 7\cdot \left\{\begin{matrix}17\\6\end{matrix}\right\}6!=14832686379847$$

Alternatively, we could have gone directly and added only the good cases, giving:

$$\sum\limits_{k=2}^7 \binom{7}{k}\left\{\begin{matrix}17\\7-k\end{matrix}\right\}(7-k)!$$

which equals the same as before.