Skip to content
Tutorials Center
My learning

Topics

Lesson 7 of 36 ยท Counting Principles

Complement Counting and Casework

Count hard sets by counting what you do not want: the complement rule, at-least-one problems, and when to split into cases. Worked examples with Python checks.

Some sets are painful to count directly but easy to count from the opposite side. If you know the size of the whole universe and the size of the part you do not want, subtraction gives the answer. This is complement counting, and together with casework it solves a huge share of exam problems.

Complement rule. If U is the set of all outcomes and A a subset, then |A| = |U| - |A^c|, where A^c is everything in U that is not in A.

At least one

"At least one" is the classic trigger. How many 5-letter strings over {A, B} contain at least one A? Counting strings with exactly one A, two A's and so on is tedious. The complement is "no A at all", which is the single string BBBBB. So the answer is 2^5 - 1 = 31.

Python At least one A

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

A bigger example: dice

Roll two six-sided dice. How many outcomes have a sum of at least 3? The universe has 36 outcomes. The complement is "sum less than 3": only (1, 1) with sum 2. So 36 - 1 = 35.

For three dice and "at least one six": the universe is 6^3 = 216, the complement "no six" is 5^3 = 125, so the answer is 91.

Python Dice with complement

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Distinct digits and restrictions

How many 4-digit numbers have at least two equal digits? A four-digit number runs from 1000 to 9999, so 9000 of them. The complement is "all digits different": 9 choices for the first (1-9), then 9, 8, 7 for the others (zero allowed now, minus used ones): 9 x 9 x 8 x 7 = 4536. Answer: 9000 - 4536 = 4464.

Python Repeated digits

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Casework revisited

Complement counting is one strategy; casework is the other. In casework you split by some feature and count each case, then add (the sum rule). Choose it when the complement is not simpler.

Example: how many 3-digit numbers (100-999) are even and have no repeated digit? Split by the last digit, since it is the constrained one.

  • Last digit 0: first digit 9 choices (1-9), middle 8 left: 9 x 8 = 72.
  • Last digit 2, 4, 6 or 8 (4 cases): first digit cannot be 0 or the last digit, so 8 choices; middle digit cannot match either, so 8 choices: 8 x 8 = 64 each, 256 total.

Total: 72 + 256 = 328.

Python Even 3-digit numbers without repeated digits

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Choosing the strategy

flowchart TD
    Q{"Hard to count directly?"} -->|"has 'at least one'"| C["Count the complement"]
    Q -->|"one position restricted"| F["Fill that position first"]
    Q -->|"depends on a feature"| K["Split into cases, add"]
    C --> R["Subtract from the total"]

Pick the strategy by the wording; combine them when one is not enough.

When the complement involves overlapping conditions (for example "not divisible by 2, 3 or 5"), the cases of the complement overlap, and you move on to inclusion-exclusion.

A sanity check technique

Whichever strategy you use, run a quick check with a small version of the problem. For the digit problem above, restrict to 2-digit numbers (10-99), do the same reasoning, and test it by brute force. If the method fails on the small case, it will fail on the large one.

Python Test the method on a small version

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. How many 4-bit strings contain at least one 1?

    All 16 strings minus the single all-zero string: 15.
  2. 2. Three coins are flipped. How many outcomes show at least one head?

    2^3 - 1 = 7 (only TTT has no head).
  3. 3. When is complement counting most useful?

    If counting what you do not want is simpler, subtract it from the total.
  4. 4. How many 3-letter strings from {a, b, c, d} have not all letters equal?

    4^3 = 64 minus the 4 strings aaa, bbb, ccc, ddd gives 60.

Summary

  • Complement rule: |A| = |U| - |A^c|.
  • "At least one" is the usual signal to count the opposite.
  • Casework splits into exhaustive, exclusive cases and adds.
  • Test the method on a tiny version with brute force.

Next: Counting Functions and Subsets