Mathematics
The Principle of Inclusion-Exclusion for Counting Union of Sets
Quick fact
For three sets A, B, and C, the number of elements in their union is |A|+|B|+|C| − |A∩B| − |A∩C| − |B∩C| + |A∩B∩C|. This alternating pattern—add all, subtract pairwise, add triple—applies for any number of sets.
Why this is interesting
You have a bag of red marbles, a bag of blue marbles, and some that are both. How many distinct marbles are there in total? Simply adding the counts would count the mixed ones twice—so what's the right way?
Read the full explanation
Understanding The Principle of Inclusion-Exclusion for Counting Union of Sets
Imagine two overlapping circles in a Venn diagram. One circle contains students who play soccer, the other those who play basketball. Some students are in both circles. If you simply add the number of soccer players and basketball players, you've counted the dual-sport students twice. To fix this, you subtract the number who are in both sets once. That gives the correct total for the union. For three sets, the count gets trickier: adding all three counts the triple-overlap students three times, and then subtracting pairwise overlaps removes them too many times, so you must add back the triple intersection once. This 'add one, subtract two, add three' pattern continues for more sets, alternating signs.
A deeper explanation
The principle of inclusion-exclusion is a combinatorial formula that corrects overcounting when sets overlap. For two sets, the formula |A∪B| = |A| + |B| − |A∩B| works because every element in the intersection is counted twice when you add the sizes of each set, so you subtract it once. For three sets, the correct formula is |A∪B∪C| = |A|+|B|+|C| − |A∩B| − |A∩C| − |B∩C| + |A∩B∩C|. This pattern emerges from considering how many times each element is counted. An element in exactly one set is counted once in the first sum and never in the intersections, so it's fine. An element in exactly two sets (say A and B) is counted twice in the first sum and once in the intersection A∩B, so the net count is 2 − 1 = 1. An element in all three sets is counted three times in the first sum, three times in the pairwise intersections (once for each pair), and then added back once in the triple intersection, giving 3 − 3 + 1 = 1. The alternating sum ensures each element is counted exactly once. For n sets, the formula continues: sum of sizes of all sets, minus sum of sizes of all pairwise intersections, plus sum of sizes of all triple intersections, and so on with signs alternating. This is derived from the binomial theorem and is a foundational technique in combinatorics, probability, and number theory, enabling counting of elements avoiding certain properties.