1. What Is the Principle of Inclusion and Exclusion?
The principle of inclusion and exclusion (PIE) is a method used to find the number of elements in the union of sets. It helps avoid double-counting when sets overlap.
When two or more sets share common elements, counting them separately may add the same elements more than once. PIE fixes this by adding and subtracting overlaps carefully.
2. Why Do We Need PIE?
If two sets overlap, simply adding their sizes counts the intersection twice. PIE corrects this mistake and gives the accurate total number of elements.
2.1. Simple Idea
- Add the sizes of the sets.
- Subtract any common part counted twice.
3. PIE for Two Sets
For two sets A and B, the formula is:
3.1. Formula
\( |A \cup B| = |A| + |B| - |A \cap B| \)
3.2. Explanation
Add the number of elements in A and B, then subtract the common part because it was counted twice.
3.3. Example
If:
|A| = 10, \quad |B| = 8, \quad |A \cap B| = 3
Then:
|A \cup B| = 10 + 8 - 3 = 15
4. PIE for Three Sets
When dealing with three sets, overlaps become more complex. PIE adjusts by adding and subtracting twice-counted and thrice-counted parts.
4.1. Formula
|A \cup B \cup C| = |A| + |B| + |C| - |A \cap B| - |B \cap C| - |A \cap C| + |A \cap B \cap C|
4.2. Meaning
- Add individual set sizes.
- Subtract all pairwise overlaps.
- Add the triple overlap because it was subtracted too many times.
4.3. Example
If:
|A| = 20, \; |B| = 15, \; |C| = 12
|A \cap B| = 5, \; |B \cap C| = 4, \; |A \cap C| = 3
|A \cap B \cap C| = 2
Then:
|A \cup B \cup C| = 20 + 15 + 12 - 5 - 4 - 3 + 2 = 37
5. General Idea for More Sets
The principle continues for more sets by alternating between adding and subtracting intersections. As the number of sets increases, the formula becomes longer but follows the same pattern.
5.1. Pattern
- Add sizes of single sets
- Subtract sizes of pairwise intersections
- Add triple intersections
- Subtract four-way intersections
- Continue alternating...
6. Visual Understanding Using Venn Diagrams
Venn diagrams help show why we subtract and add overlaps. Overlapping regions appear multiple times when simply adding the sets, and PIE adjusts this by removing extra counts.
7. Important Points
Key ideas to remember about PIE:
7.1. Key Ideas
- PIE avoids overcounting when sets overlap.
- For two sets, subtract the intersection once.
- For three sets, add back the triple intersection.
- The formula grows but follows a clear pattern.
- Very useful in counting problems involving surveys, groups, and overlapping conditions.