0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ How many ways are there to distribute 17 distinct objects into 7 distinct boxes with exactly 0 empty box? $\endgroup$ – Calvin Lin Apr 12 '20 at 17:16
  • $\begingroup$ Your approach in both attempts is incorrect. A corrected approach will likely involve stirling numbers of the second kind in some manner. $\endgroup$ – JMoravitz Apr 12 '20 at 17:20
0
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Thanks Calvin, you have made me understand where I am going wrong. Its how my methods are suffering from over-counting of ways. I have read the link also that you have made a reference to ik n your post, which again helped me understand it further. $\endgroup$ – Praveen Jha Apr 12 '20 at 20:11
  • $\begingroup$ But Calvin, even after knowing where is my mistake, I am still finding in hard to solve this question, may be because there are 13 number of boxes and 17 objects which is making is complex for me to solve using inclusion-exclusion principle. If you can help me with a thorough solution of this question, it would be really helpful for me Calvin. $\endgroup$ – Praveen Jha Apr 12 '20 at 20:16
0
$\begingroup$

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.

$\endgroup$

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.