📋 Prerequisites

• Counting Basics
• Permutations & Combinations

Sometimes counting what you want directly is messy, but counting what you don't want is easy. Complementary counting — subtracting the "bad" from the "total" — is one of the most powerful problem-solving techniques in combinatorics. When you see "at least one," think complement first.

📚 Key Concepts

The Complement Principle

If U is the set of all possible outcomes (the universe), and A is the set you care about, then:

\[ |A| = |U| - |A^{\mathsf{c}}| \]

Number of good outcomes = Total outcomes - Number of bad outcomes.

Simple idea, but it turns hard problems into easy ones.

When to Use Complementary Counting

Use complementary counting when:

• The problem says "at least one" or "at least k"
• The problem says "not all" or "not both"
• Direct counting requires many cases, but the complement has few cases
• The total is easy to compute

Classic trigger phrase: "at least one" — the complement is "none," which is usually a single case.

"At Least One" Problems

This is the #1 application. "At least one success" is hard directly (cases: 1 success, 2 successes, ...), but "zero successes" is one simple case.

Answer = Total - None

Example: roll 3 dice, probability of at least one 6. Total = \(6^{3}\) = 216. No sixes = \(5^{3}\) = 125. At least one six = 216 - 125 = 91.

Complementary Counting with Restrictions

Arrangement problems where something is forbidden:

Example: arrange 5 people, A and B cannot be adjacent.

\(Total: 5! = 120. Bad (A,B together): treat as block \\to 4! \\times 2! = 48. Good: 120 - 48 = 72.\)

This is often easier than the gap method, and a good way to verify gap-method answers.

Complementary Probability

Same idea applied to probability:

\[ P(A) = 1 - P(A^{\mathsf{c}}) \]

P(at least one success) = 1 - P(no successes)

Example: 30% \(chance of rain each day, independent. P(rain at least once in 5 days) = 1 - (0.7)^{5} \\approx 0.832.\)

Common Complement Translations

Strategy: Compare Direct vs Complement

Before diving in, quickly estimate: how many cases for direct? How many for complement?

Pick whichever has fewer cases. This 10-second check saves minutes.

Rule of thumb: if "at least one" appears, try complement first — it's usually the right move.

Watch Out: Over-Complementing

Make sure you're computing the correct complement. "At least one red AND at least one blue" \(\\neq\) "not all red and not all blue."

The complement of "at least one of each" is "missing at least one color" — which itself might need inclusion-exclusion (next module).

Always define clearly: what's the universe? What exactly is the bad set?

✏️ Example Problems