How am I using the inclusion-exclusion principle wrongly?

Question

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?

Answer 1

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.)

Answer 2

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$$

Answer 3

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} $$