(→Inclusion-Exclusion Principle (Basic)) |
|||
| Line 6: | Line 6: | ||
Subtracting <math>|B \cap C| </math> corrects the overcount. | Subtracting <math>|B \cap C| </math> corrects the overcount. | ||
| + | |||
| + | In general, | ||
| + | |||
| + | <math> |A(1) \cup A(2) \cup ... \cup A(n)| = </math> | ||
| + | |||
| + | <math> |A(1)| + |A(2)| + ... + |A(n)| </math> | ||
| + | |||
| + | <math> - |A(1) \cap A(2)| - |A(1) \cap A(3)| - ... - |A(n-1) \cap A(n)| </math> | ||
| + | |||
| + | <math> + |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)| </math> | ||
| + | |||
| + | <math> + (-1)^(n+1) |A(1) \cap A(2) \cap A(3) \cap ... \cap A(n)| </math> | ||
Revision as of 17:20, 7 September 2008
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)| $
