Inclusion-exclusion principle for three sets

The inclusion-exclusion principle was discussed previously for two sets.

We can also have a situation in which three or more sets share some common elements.  The Venn diagram below illustrates this. There may be subsets that are non-empty pairwise intersections of the sets and we are assuming that there is a non-empty intersection of all the sets.

Suppose we wish to count the elements in sets $A$A, $B$B and $C$C. This is the number of elements in $A$A or $B$B or $C$C. As a first approximation we might say the sum is $#\left(A\cup B\cup C\right)=#A+#B+#C$#(A∪B∪C)=#A+#B+#C. However, some of the elements would have been counted more than once. 

To see what must be done to allow for the multiple counting, focus on the red dot. The sum $#A+#B+#C$#A+#B+#C includes this element three times. The dots in the pairwise intersections have been counted twice, so we should remove $#(A\cap B)$#(A∩B), $#(A\cap C)$#(A∩C) and $#(B\cap C)$#(B∩C).

However, this removes the red dot three times. Therefore, we must add the three-way intersection $#(A\cap B\cap C)$#(A∩B∩C) back into the sum.

Hence, we conclude that 

$#\left(A\cup B\cup C\right)=#A+#B+#C-#(A\cap B)-#(A\cap C)-#(B\cap C)+#(A\cap B\cap C)$#(A∪B∪C)=#A+#B+#C−#(A∩B)−#(A∩C)−#(B∩C)+#(A∩B∩C)

 

The pattern can be extended similarly for cases where there are four or more intersecting sets.

 

Example 1

Given three sets $A$A, $B$B and $C$C such that $#A=11,#B=10,#C=10,#(A\cap B)=4,#(A\cap C)=3,#(B\cap C)=5$#A=11,#B=10,#C=10,#(A∩B)=4,#(A∩C)=3,#(B∩C)=5, and $#(A\cup B\cup C)=21$#(A∪B∪C)=21, how many elements are in the intersection of all three sets?

Since

$#\left(A\cup B\cup C\right)=#A+#B+#C-#(A\cap B)-#(A\cap C)-#(B\cap C)+#(A\cap B\cap C)$#(A∪B∪C)=#A+#B+#C−#(A∩B)−#(A∩C)−#(B∩C)+#(A∩B∩C)

we have

$21$21	$=$=	$11+10+10-4-3-5+#(A\cap B\cap C)$11+10+10−4−3−5+#(A∩B∩C)
	$=$=	$19+#(A\cap B\cap C)$19+#(A∩B∩C)
$2$2	$=$=	$#(A\cap B\cap C)$#(A∩B∩C)

This result corresponds to the diagram above.

 

Example 2

Subjects in a certain observational study could have any combination of up to three characteristics, $A,B$A,B and $C$C. In all, $153$153 subjects were observed.

It was found that $17$17 of the subjects had all three characteristics, $35$35 had characteristics $A$A and $B$B, $41$41 had characteristics $A$A and $C$C, and $53$53 had characteristics $B$B and $C$C. The researchers counted $51$51 instances of each separate characteristic.

Estimate the probability that in a similar population a subject would have none of the characteristics.

Using the inclusion-exclusion principle, we have 

$#(A\cup B\cup C)$#(A∪B∪C)	$=$=	$51+51+51-35-41-53+17$51+51+51−35−41−53+17
	$=$=	$41$41

Thus, $41$41 of the subjects had at least one of the characteristics. The number with none of the characteristics must have been $153-41=112$153−41=112.

Therefore the probability estimate for observing none of the characteristics should be $\frac{112}{153}\approx0.73$112153​≈0.73.