Complementary Counting: Instead of counting what we want, count what we don't want and subtract from the total. Often easier when the restriction is "at least one" or "not all."
- Count the total possible outcomes
- Count the outcomes that violate the restriction
- Subtract: Desired outcomes = Total - Violating outcomes
Range: 1000 to 9999. Total = 9999 - 1000 + 1 = 9000.
Thousands digit: 1,2,3,4,5,6,8,9 (8 choices, can't be 0 or 7). Other digits: 0,1,2,3,4,5,6,8,9 (9 choices each). Total = 8×9×9×9 = 5832.
Numbers with at least one 7 = Total - Numbers with no 7s = 9000 - 5832 = 3168.
There are 3,168 four-digit numbers that contain at least one 7.
• Complementary counting: Count what we don't want, subtract from total
• Restriction handling: "At least one" often implies complementary approach
• Fundamental counting principle: Multiply independent choices
Inclusion-Exclusion Principle: For two sets A and B: |A ∪ B| = |A| + |B| - |A ∩ B|. This prevents double-counting elements in both sets.
|A ∪ B| = |A| + |B| - |A ∩ B| = 60 + 50 - 30 = 80.
Total people - People who like at least one = 100 - 80 = 20.
Coffee only: 60-30=30, Tea only: 50-30=20, Both: 30, Neither: 100-(30+20+30)=20.
There are 20 people who like neither coffee nor tea.
• Inclusion-exclusion: |A ∪ B| = |A| + |B| - |A ∩ B|
• Overcounting prevention: Subtract intersection to avoid double counting
• Complementary principle: Total - Desired = Undesired
Treating as a Unit: When objects must be adjacent, treat them as a single unit. Count arrangements of the unit with other objects, then arrange objects within the unit.
Instead of 5 people, we now have 4 units: the couple (as one unit) + 3 other individuals.
The 4 units can be arranged in 4! = 24 ways.
The two people in the unit can be arranged in 2! = 2 ways (AB or BA).
Total arrangements = 24 × 2 = 48.
There are 48 ways to seat 5 people in a row with 2 particular people sitting together.
• Treat as unit: Combine restricted objects into a single entity
• Multiplication principle: External arrangements × internal arrangements
• Adjacency restriction: Use grouping method for adjacent requirements
Counting with Restrictions: Methods for counting arrangements or selections when certain conditions must be met.
Complementary Counting: Counting desired outcomes by subtracting unwanted outcomes from total outcomes.
Inclusion-Exclusion Principle: A method to count elements in the union of sets by adding individual counts and subtracting overlaps.
Treating as Unit: Grouping objects that must satisfy adjacency conditions into a single entity.
- Identify the restriction: Determine what condition must be satisfied
- Choose appropriate method: Complementary, inclusion-exclusion, unit treatment, etc.
- Break down the problem: Separate the counting into manageable parts
- Apply the method: Execute the chosen strategy systematically
- Combine results: Use addition, subtraction, or multiplication as needed
- Verify: Check if the answer makes logical sense
• Complementary: Desired = Total - Undesired
• Inclusion-exclusion (2 sets): |A ∪ B| = |A| + |B| - |A ∩ B|
• Inclusion-exclusion (3 sets): |A ∪ B ∪ C| = |A| + |B| + |C| - |A ∩ B| - |A ∩ C| - |B ∩ C| + |A ∩ B ∩ C|
• Adjacent objects: (n-1)! × k! for k objects together in n positions
Multiple Simultaneous Restrictions: When several conditions must all be satisfied at once, count possibilities for each position while respecting all constraints.
Given digits: {1, 2, 3, 4, 5}. Even digits: {2, 4}. Odd digits: {1, 3, 5}.
First digit must be even: 2 choices (2 or 4).
Last digit must be odd: 3 choices (1, 3, or 5).
After choosing first and last digits, 3 digits remain for the middle 3 positions: 3! = 6 arrangements.
Total = 2 × 3 × 6 = 36.
There are 36 five-digit numbers that can be formed with the given restrictions.
• Simultaneous restrictions: Apply all constraints together
• Sequential counting: Address each position with its constraints
• Without replacement: Each digit used only once
Three-Set Inclusion-Exclusion: |A ∪ B ∪ C| = |A| + |B| + |C| - |A ∩ B| - |A ∩ C| - |B ∩ C| + |A ∩ B ∩ C|. This accounts for all possible overlaps between three sets.
|M ∪ P ∪ C| = |M| + |P| + |C| - |M ∩ P| - |M ∩ C| - |P ∩ C| + |M ∩ P ∩ C|
= 60 + 50 + 40 - 30 - 25 - 20 + 15 = 150 - 75 + 15 = 90
Total students - Students studying at least one subject = 100 - 90 = 10.
We added individual sets (overcounting), subtracted pairwise intersections (correcting overcount), added back triple intersection (correcting undercount).
There are 10 students who study none of the three subjects.
• Three-set inclusion-exclusion: |A∪B∪C| = |A|+|B|+|C| - |A∩B|-|A∩C|-|B∩C| + |A∩B∩C|
• Systematic correction: Add individual counts, subtract pairwise overlaps, add back triple overlap
• Complementary counting: Total minus desired gives undesired
Counting with Restrictions: Methods for counting arrangements or selections when certain conditions must be satisfied.
Complementary Counting: Counting desired outcomes by subtracting unwanted outcomes from total outcomes.
Inclusion-Exclusion Principle: A method to count elements in the union of sets by adding individual counts and subtracting overlaps.
Treating as Unit: Grouping objects that must satisfy adjacency conditions into a single entity.
Simultaneous Restrictions: Multiple conditions that must all be satisfied at the same time.
- Problem analysis: Identify all restrictions and requirements
- Method selection: Choose appropriate technique (complementary, inclusion-exclusion, etc.)
- Constraint breakdown: Handle each restriction systematically
- Counting execution: Apply the chosen method step-by-step
- Result combination: Use arithmetic operations to find the final answer
- Verification: Check if the answer is reasonable and complete
• Complementary counting: Desired outcomes = Total outcomes - Undesired outcomes
• Two-set inclusion-exclusion: |A ∪ B| = |A| + |B| - |A ∩ B|
• Three-set inclusion-exclusion: |A ∪ B ∪ C| = |A| + |B| + |C| - |A ∩ B| - |A ∩ C| - |B ∩ C| + |A ∩ B ∩ C|
• Adjacent arrangements: (n-1)! × k! for k objects together in n positions
• n-set inclusion-exclusion: Alternating sum of all possible intersections
• Simple: Single restriction (at least one occurrence)
• Intermediate: Two overlapping categories (inclusion-exclusion)
• Advanced: Adjacency requirements (unit treatment)
• Complex: Multiple simultaneous restrictions
• Advanced: Three or more overlapping sets
• "At least one" often suggests complementary counting
• Overlapping categories require inclusion-exclusion to avoid double counting
• Adjacent requirements suggest treating objects as a single unit
• Multiple restrictions must be satisfied simultaneously
• Always verify that your answer respects all given constraints
Questions & Answers
Question: How do I know when to use complementary counting vs direct counting?
Answer: Use complementary counting when:
- The condition is "at least one," "not all," or "some but not all"
- Counting the undesired outcomes is simpler than counting desired ones
- You have many different ways to satisfy the condition
Use direct counting when the condition is straightforward to enumerate. For example, "numbers with at least one 7" is easier via complementary counting (total - numbers with no 7s) than direct counting.
Question: Why do we subtract the intersection in inclusion-exclusion? Isn't that removing too much?
Answer: When you add |A| + |B|, you count elements in A ∩ B twice - once in |A| and once in |B|. Since elements in the intersection should only be counted once in |A ∪ B|, you subtract |A ∩ B| to correct for this double counting.
Think of it as: "I counted them twice, so I need to remove one count to get the correct total."
Question: Can I use inclusion-exclusion with more than three sets? How does the pattern continue?
Answer: Yes! The inclusion-exclusion pattern continues with alternating signs:
- Start with sums of individual sets
- Subtract sums of all pairwise intersections
- Add sums of all three-way intersections
- Subtract sums of all four-way intersections
- Continue alternating until you reach the n-way intersection
For four sets: |A∪B∪C∪D| = |A|+|B|+|C|+|D| - |A∩B|-|A∩C|-|A∩D|-|B∩C|-|B∩D|-|C∩D| + |A∩B∩C|+|A∩B∩D|+|A∩C∩D|+|B∩C∩D| - |A∩B∩C∩D|