(→Inclusion-Exclusion Principle (Basic)) |
|||
| (6 intermediate revisions by 3 users not shown) | |||
| Line 1: | Line 1: | ||
| + | [[Category:MA375]] | ||
| + | [[Category:math]] | ||
| + | [[Category:discrete math]] | ||
| + | [[Category:lecture notes]] | ||
| + | |||
| + | =[[MA375]]: Lecture Notes= | ||
| + | Fall 2008, Prof. Walther | ||
| + | ---- | ||
==Inclusion-Exclusion Principle (Basic)== | ==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: | 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: | ||
| − | <math> |B \cup C| = |B| + |C| - |B \cap C| <math> | + | <math> |B \cup C| = |B| + |C| - |B \cap C| </math> |
| + | |||
| + | Subtracting <math>|B \cap C| </math> corrects the overcount. | ||
| + | |||
| + | In general, | ||
| + | |||
| + | <math>\displaystyle |A_1 \cup A_2 \cup ... \cup A_n| = </math> | ||
| + | |||
| + | <math>\displaystyle |A_1| + |A_2| + ... + |A_n| </math> | ||
| + | |||
| + | <math>\displaystyle - |A_1 \cap A_2| - |A_1 \cap A_3| - ... - |A_(n-1)\cap A_n| </math> | ||
| + | |||
| + | <math>\displaystyle + |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>\displaystyle + (-1)^(n+1)|A_1 \cap A_2 \cap A_3 \cap ... \cap A_n| </math> | |
| + | ---- | ||
| + | [[Main_Page_MA375Fall2008walther|Back to MA375, Fall 2008, Prof. Walther]] | ||
Latest revision as of 07:19, 20 May 2013
MA375: Lecture Notes
Fall 2008, Prof. Walther
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,
$ \displaystyle |A_1 \cup A_2 \cup ... \cup A_n| = $
$ \displaystyle |A_1| + |A_2| + ... + |A_n| $
$ \displaystyle - |A_1 \cap A_2| - |A_1 \cap A_3| - ... - |A_(n-1)\cap A_n| $
$ \displaystyle + |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| $
$ \displaystyle + (-1)^(n+1)|A_1 \cap A_2 \cap A_3 \cap ... \cap A_n| $
