|
||
| The Inclusion/Exclusion Principle
|
||
| When two tasks can be done simultaneously, the number of ways to do one of the tasks cannot be counted with the sum rule. A sum of the two tasks is too large because the ways to do both tasks (that can be done simultaneously) are counted twice. To correct this, we add the number of ways to do each of the two tasks, and then subract the number of ways to do both tasks.
This Principle can be shown in terms of sets. Let A1 and A2 be sets. Let T1 be the task of choosing an element from A1 and T2 the task of choosing an element from A2. There are |A1| ways to do T1 and |A2| ways to do T2. The number of ways to do either T1 or T2 is the sum of the number of ways to do T1 and the number of ways to do T2, minus the number of ways to do both T1 and T2. Since there are |A1 union A2| ways to do either T1 or T2 and |A1 intersection A2| ways to do both T1 and T2.
|
||
| Example 1: | How many strings of 5 digits are there that begin or end with a 1? | |
| Solution |
||
| Example 2: | Figure out how many elements would exist in the union of the sets A={1,2,3,4,5,6,7,8,9,10} and B={2,4,6,8,10,12,14} using the principle of inclusion/exclusion. Then write the set that is the union of the sets A and B. | |
| Solution |
||
| Example 3: | Assuming that any digit can be in any position, how many different possible social security numbers (SSNs) are there that either start with a 5, or that end in a 6? Note: A social security number is 9 digits in length and each digit can be any number from 0-9 |
|
| Solution |
||
|
|
||||
| previous page | home |
|
||