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?
Identify problems that need inclusion – exclusion principle
combinatoricsdiscrete mathematicsinclusion-exclusion
Best Answer
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.