# How am I using the inclusion-exclusion principle wrongly?

I was trying to solve this problem (taken from Harvard's Stat 110 class) using the inclusion-exclusion principle:

A city with 6 districts has 6 robberies in a particular week. Assume the robberies are located randomly, with all possibilities for which robbery occurred where equally likely. What is the probability that some district had more than 1 robbery?

Here's how I tried to approach the problem:

Define $A_i$ as the event that more than $1$ robbery occurs in district $i$, with $1 \leq i \leq 6$.

Then, what we need to find is $P(A_1 \cup A_2 \cup A_3 \cup A_4 \cup A_5 \cup A_6)$.

By the inclusion-exclusion principle, this is equal to $\Sigma_{i=1}^{6}P(A_i)$ $-$ $\Sigma_{i<j} P(A_i \cap A_j)$ $+$ $\Sigma_{i<j<k} P(A_i \cap A_j \cap A_k)$ (the terms involving more than $3$ $A_i$s are not possible because there are only 6 robberies, and we can't have more than $1$ of them, when there are $>3$ districts).

Now, $\Sigma_{i=1}^{6}P(A_i) =$ $6 \times \frac{5}{6}$, since $2,3,4,5,$ or $6$ robberies can happen in each of the $6$ districts.

Also, $\Sigma_{i<j} P(A_i \cap A_j)$ = $6\choose2$ $\times$ $\frac{6}{36}$, since for each of the $6\choose2$ pairs of districts, the robbery counts can be $\{(2,2),(2,3),(2,4),(3,2),(3,3),(4,2)\}.$

Counting in a similar fashion, $\Sigma_{i<j<k} P(A_i \cap A_j \cap A_k) =$ $6\choose3$ $\times$ $\frac{1}{216}$.

But adding the above three terms gives me a probability greater than $1$. Where am I going wrong?

• 1 minus the probability that no district had more than one robbery. – IntegrateThis Oct 13 '17 at 7:01
• What makes you think that $P(A_1)=\frac56$? If $R_1$ denotes the number of robberies in district 1 then $P(A_1)=1-P(R_1=0)-P(R_1=1)$. Here e.g. $P(R_1=0)=\left(\frac56\right)^6$ – drhab Oct 13 '17 at 7:05
• But these events are not equiprobable. – drhab Oct 13 '17 at 7:09
• @IntegrateThis Of course, but that is not what the OP is after. He wants to know what he/she did wrong in applying inclusion/exclusion. – drhab Oct 13 '17 at 7:11
• @Zephyr: No district can have $0$ robberies in the complement, because you need to add up to get $6$ robberies and that's not possible with even a single district having $0$ robberies, when you are only allowed $0$ or $1$ robberies per district. – Train Heartnet Oct 13 '17 at 10:22

## 3 Answers

Personalize the robberies with the robbers.

There are $6$ of them. Each of them picks out randomly a district saying: "Yes, that will be the place for me to rob, hahaha..."

They know nothing about their colleague robbers and choose completely independent.

Then what is the probability that more than $1$ robbers will choose for district 1?

It is $1$ minus the probability that exactly $0$ robbers or exactly $1$ robber will choose for district 1.

District 1 will receive $0$ robberies if all robbers choose for another district. The probability that the first robber will do that is $\frac56$, the probability that the second will do that is also $\frac56$, et cetera.

Then the probability that all will do that is $\left(\frac56\right)^6$.

Likewise (but a bit more complicated) we can find that the probability that exactly one robber will choose for district 1 is $6\left(\frac16\right)\left(\frac56\right)^5$ so we end up with: $$P(A_1)=1-\left(\frac56\right)^6-6\left(\frac16\right)\left(\frac56\right)^5$$

• Aha, I get it now! So the reason why the numbers aren't equally likely is because the numbers ultimately depend on how the robbers decide to choose which districts to rob, and this ultimately depends on the number of robbers! I feel so dumb now! Thank you, @drhab! :) – Train Heartnet Oct 13 '17 at 7:47
• You are very welcome. If people really learn things then my time is not "robbed" but well spended. – drhab Oct 13 '17 at 7:49

The error in the OP's use of inclusion-exclusion has been addressed in drhab's answer, so I'll merely note that this problem does not require inclusion-exclusion at all. Because there are the same number of robberies as districts, the only way to avoid having two robberies in some district is to have exactly one robbery in each district, so we can jump immediately to the answer

$$1-{6!\over6^6}$$

or, if you prefer,

$$1-\left(5\over6\right)\left(4\over6\right)\left(3\over6\right)\left(2\over6\right)\left(1\over6\right)$$

(That is, to avoid two robberies in some district, the first robbery can occur anywhere, but subsequent robberies must occur in a remaining, unrobbed district.)

Although there are much more efficient ways to solve this problem, inclusion-exclusion can be made to work. The answer of drhab gives $P(A_1)$. Of the other terms needed, $P(A_1\cap A_2\cap A_3)$ is not very involved: it's just $\frac{6!}{2!\,2!\,2!}\frac{1}{6^6}$. The hard one is $$P(A_1\cap A_2)=\left(\binom{2}{1}\frac{6!}{4!\,2!}+\frac{6!}{3!\,3!}+\binom{2}{1}\binom{4}{1}\frac{6!}{3!\,2!\,1!}+\binom{4}{1}\frac{6!}{2!\,2!\,2!}+\binom{4}{2}\frac{6!}{2!\,2!\,1!\,1!}\right)\frac{1}{6^6},$$ which can also be done by complement using a second application of inclusion-exclusion: \begin{aligned} P(A_1\cap A_2)=1&-2\left(\left(\frac{5}{6}\right)^6+6\left(\frac{1}{6}\right)\left(\frac{5}{6}\right)^5\right)\\&+\left(\frac{4}{6}\right)^6+2\cdot6\left(\frac{1}{6}\right)\left(\frac{4}{6}\right)^5+\frac{6!}{1!\,1!\,4!}\left(\frac{1}{6}\right)\left(\frac{1}{6}\right)\left(\frac{4}{6}\right)^4. \end{aligned}