How to identify problems that need inclusion - exclusion principle

Question

So , I have pointed out that when a problem needs the principle of inclusion - exlcusion I sometimes miss that . For example " We need to identify how to disturb r different objects to 5 dinstict boxes such that there is at least one that remains empty. I initially thought : Well, it;s easier to compute the complementary fact "Any box remains empty" So first we need to make sure that every box is filled with at least 1 object . We pick 5 out of r , with C(r,5) ways and then we have (r-5) more objects to disturb . We can do that in:$ 5^{r-5} $ways. So final answer : $5^r - 5^{r-5}C(r,5)$. But then comes the solution of the book : $C(5,1)*4^r - C(5,2)*3^r+C(5,3)2^r-C(5,4)*1^r$ . I can see why : every term in the sum represents the fact: In case that: exaclty i box/xes remain empty. But why my approach is wrong? How should I have identified to use the inclusion - exclusion principle? Is "at least " a key word for such problems?

Answer 1

The problem with your approach is that it’s hard to count the distributions with no empty boxes. Yes, you can start by choosing $5$ objects and putting one of them in each box, but this can be done in $\binom{r}55!$ ways, not $\binom{r}5$ ways: which object goes into which box matters. And yes, there are then $5^{r-5}$ ways to distribute the remaining $r-5$ objects. But if you multiply these together, you’re counting many distributions more than once.

Suppose, for instance, that the objects are numbered $1$ through $10$. You might initially choose objects $1$ through $5$ and put them in that order into boxes $1$ through $5$, and then you might put objects $6$ and $7$ into box $1$ and objects $8,9$, and $10$ into box $3$. That produces this distribution:

$$\begin{array}{rcc} \text{Box:}&1&2&3&4&5\\ \text{Objects:}&1,6,7&2&3,8,9,10&4&5 \end{array}$$

But you might instead have started by choosing objects $2,4,5,6$, and $9$ and putting them into boxes $2,4,5,1$, and $3$, respectively. If you then put objects $1$ and $7$ into box $1$ and objects $3,8$, and $10$ into box $3$, you’d end up with exactly the same distribution, but you’d have counted it separately. In fact, you’d end up counting this distribution altogether $12$ times, because there are $3\cdot1\cdot4\cdot1\cdot1=12$ different sets of $5$ objects with which you could get it started.

Since the number of times a distribution is counted depends on the numbers of objects in each box, there’s no simple way to take it into account.

In general you’ll use inclusion-exclusion when you can’t easily avoid overcounting, as it’s a way to compensate for overcounting.. Here, for instance, it’s easy to see that there are $4^r$ distributions that leave box $1$ empty and $4^r$ distributions that leave box $3$ empty, but a moment’s thought shows that we can’t simply add those and say that there are $2\cdot 4^r$ distributions that leave box $1$ or box $3$ empty: the distributions that leave both of those boxes empty would then be counted twice. So we start by estimating that there are $\binom51$ ways to choose a box to be empty, and for each of those choices $4^r$ ways to distributet the objects to the remaining $4$ boxes, for a total estimate of $\binom514^r$ distributions, but then we start correcting for the overcounting.

There are $\binom52$ ways to choose $2$ boxes to remain empty, and for each of those choices there are $3^r$ ways to distribute the objects to the other $3$ boxes. Every one of those distributions was counted twice in the original estimate, so we have to subtract them to get an improved estimate of $\binom51r^r-\binom523^r$.

Unfortunately, the correction term $\binom523^r$ overcounts the overcounting: every distribution that leaves boxes $1,2$, and $3$ empty, for instance, gets counted once for leaving boxes $1$ and $2$ empty, once for leaving boxes $1$ and $3$ empty, and once for leaving boxes $2$ and $3$ empty. The initial estimate of $\binom514^r$ counted each of those distributions three times, once for each of the empty boxes, and the correction term also counted it three times, so our improved estimate isn’t counting it at all! Thus, we need make another correction to count the distributions that leave $3$ boxes empty. There are $\binom53$ ways to choose which $3$ boxes are to be empty and $2^r$ ways to fill the other $2$ boxes, so we have to add back in $\binom532^r$ to restore these distributions to the count, getting a further improved estimate of $\binom514^r-\binom523^r+\binom532^r$.

And it now turns out that distributions that leave $4$ boxes empty have been counted $4-6+4=2$ times altogether, so that we have to subtract them.

Note that the correction terms are alternately subtracted and added, so that the book’s solution, at least as you’ve reported it, is incorrect.

The inclusion-exclusion formula takes care of all of this fairly automatically, but you can always go back and see exactly how the counting works by making an analysis along these lines.

Answer 2

You (or the book) omitted the minus signs. The correct formula is: $$\sum_{k=1}^5 (-1)^{k+1} \binom{5}{k}(5-k)^r$$

As a check, you should get $5$ when $r=1$.

The idea is that you select which $k$ of the $5$ boxes are empty and then distribute the $r$ objects to the remaining $5-k$ boxes. But $(5-k)^r$ is an overcount because there might be other empty boxes besides the $k$ you specified.