Inclusion-Exclusion Principle for Three Sets

Counts how many elements lie in at least one of three sets using |A∪B∪C| = |A|+|B|+|C| − |A∩B| − |B∩C| − |C∩A| + |A∩B∩C|. It also reports how many lie in none of them, in exactly one, and in exactly two.

Given three groups, along with the size of every overlap between them, how many items belong to at least one group? The inclusion-exclusion principle answers this. Simply adding the three sizes overcounts, because anything in two groups is counted twice and anything in all three is counted three times.

Start with two sets

With two sets, adding the size of A to the size of B counts the members of both twice, so you subtract one copy.

AB=A+BAB|A \cup B| = |A| + |B| - |A \cap B|

With three sets the idea carries over, but now you have to watch out for subtracting too much.

ABC=A+B+CABBCCA+ABC|A \cup B \cup C| = |A| + |B| + |C| - |A \cap B| - |B \cap C| - |C \cap A| + |A \cap B \cap C|

Adding the triple overlap back at the end is the key step. Anything in all three sets is counted three times by A+B+C|A| + |B| + |C|, then subtracted three times by the three pairwise terms. That leaves it counted zero times, so those members vanish entirely. Adding one copy back restores them to exactly one count each.

Example

Work through the defaults: 100 people in total, 50 in A, 40 in B, 30 in C, with 20 in both A and B, 15 in both B and C, 10 in both C and A, and 5 in all three.

  1. Add the sizes: 50 + 40 + 30 = 120
  2. Subtract the pairwise overlaps: 120 − 20 − 15 − 10 = 75
  3. Add the triple overlap back: 75 + 5 = 80

So 80 people are in at least one group. With 100 people in total, 100 − 80 = 20 belong to none of them.

The other two figures follow from these. Each pairwise overlap still contains the 5 people who are in all three, so subtracting 5 from each of the three overlaps gives the number in exactly two groups: (205)+(155)+(105)=30(20 - 5) + (15 - 5) + (10 - 5) = 30 people. Taking the 30 and the 5 away from the 80 leaves those in exactly one group, 80305=4580 - 30 - 5 = 45 people. As a check, 45 + 30 + 5 = 80.

Keeping the inputs consistent

Numbers entered carelessly can describe a situation that cannot exist. The calculator detects these and reports the problem instead of returning a figure.

Survey results are the everyday use. Ask about three products and this formula tells you how many people bought at least one, and how many bought none. The same idea extends to four sets or more, with the signs alternating: add, subtract, add, subtract.