Inclusion-Exclusion Principle
The Inclusion-Exclusion Principle (PIE) is a counting technique used to calculate the size of the union of multiple sets when there is overlap between them. For two sets: |A ∪ B| = |A| + |B| - |A ∩ B|. For three sets: |A ∪ B ∪ C| = |A| + |B| + |C| - |A ∩ B| - |B ∩ C| - |A ∩ C| + |A ∩ B ∩ C|.
What You'll Learn
Introduction to Inclusion-Exclusion Principle
The Inclusion-Exclusion Principle (PIE) is a counting technique used to calculate the size of the union of multiple sets when there is overlap between them. For two sets: |A ∪ B| = |A| + |B| - |A ∩ B|. For three sets: |A ∪ B ∪ C| = |A| + |B| + |C| - |A ∩ B| - |B ∩ C| - |A ∩ C| + |A ∩ B ∩ C|.
Prerequisites
How to Solve Inclusion-Exclusion Principle Problems
Step 1: Identify the sets being counted
Step 2: Determine if the problem involves union of sets
Step 3: Apply inclusion-exclusion formula for the number of sets involved
Step 4: Calculate each term (individual set sizes, intersection sizes)
Step 5: Alternate addition and subtraction as per the formula
Step 6: For divisibility problems, use floor division to count multiples
Step 7: Present the final answer
Example Problem
Example: How many numbers from 1 to 100 are divisible by 2 or 3? Solution: Step 1: A = numbers divisible by 2, B = numbers divisible by 3 Step 2: |A| = ⌊100/2⌋ = 50, |B| = ⌊100/3⌋ = 33 Step 3: |A ∩ B| = numbers divisible by 6 = ⌊100/6⌋ = 16 Step 4: |A ∪ B| = 50 + 33 - 16 = 67 Answer: 67 numbers
Pro Tips & Tricks
- For two sets: |A ∪ B| = |A| + |B| - |A ∩ B|
- For three sets: add singles, subtract pairs, add triple
- For 'neither A nor B': total - |A ∪ B|
- For 'exactly one' problems: use inclusion-exclusion carefully
- In divisibility: |A ∩ B| = numbers divisible by LCM of divisors
- The principle works for any number of sets
Shortcut Methods to Solve Faster
Common Mistakes to Avoid
Practice Worksheets
Practice makes perfect! Work through these worksheets to master Inclusion-Exclusion Principle. Each worksheet contains 20 questions with detailed explanations. Start from Worksheet 1 and progress through increasing difficulty levels.
Exam Importance
Inclusion-Exclusion Principle is an important topic for various competitive exams. Here's how frequently it appears:
Ready to Master Inclusion-Exclusion Principle?
Start with Worksheet 1 and work your way up to expert level! Each worksheet includes: