Method for counting objects that is often employed in everyday life, yet was only formalised by Poincaré at the beginning of the 20th century. Suppose you have (finite) sets A1,...,An, and you wish to determine the number of elements N in their union
N = |A1 ∪ ... ∪ An|.
Here
|A| is the number of elements in a set
A.
- If all sets are pairwise disjoint, then N = B1 = |A1|+...+|An|. In any case, this is an upper bound on the total number of elements:
|A1 ∪ ... ∪ An| ≤
|A1|+...+|An|.
- Note that we've counted any element in more than one set more than once, so we should really deduct from the above the sizes of all intersections of pairs: B2 = |A1∩A2|+...+|A1∩An| + ... + |An-1∩An|.
If no 3 sets intersect, then N=B1-B2, and in any case
|A1 ∪ ... ∪ An| ≥
(|A1| + ... + |An|) -
(|A1∩A2| + ... + |An-1∩An|.
- But now we've deducted back every element which appears in any three of the sets three times, and deducted it three times, so we need to add it back! So B1-B2 is a lower bound on N, and we'd better add B3, the sum of the sizes of all triple intersections.
- Obviously, this logic continues at each stage. Defining Bk as the sum of the sizes of all intersections of k-tuples of sets, we see that N = B1 - B2 + ... - (-1)n Bn. And all the partial sums bracket the correct value!
So if we know how to calculate (or estimate) the sizes of intersections of sets, we can calculate (or estimate) the size of their union!
For a nontrivial application, you might read about counting permutations with no fixpoints.