Inclusion-Exclusion Principle (Basic)
Let B and C be subsets of a given set A. To count the number of elements in the union of B and C, we must evaluate the following:
$ |B \cup C| = |B| + |C| - |B \cap C| $
Subtracting $ |B \cap C| $ corrects the overcount.
In general,
$ |A(1) \cup A(2) \cup ... \cup A(n)| = $
$ |A(1)| + |A(2)| + ... + |A(n)| $
$ - |A(1) \cap A(2)| - |A(1) \cap A(3)| - ... - |A(n-1) \cap A(n)| $
$ + |A(1) \cap A(2) \cap A(3)| + |A(1) \cap A(2) \cap A(4)| + ... + |A(n-2) \cap A(n-1) \cap A(n)| $
$ + (-1)^(n+1) |A(1) \cap A(2) \cap A(3) \cap ... \cap A(n)| $
