Math Core

Sometimes the things you want are messy to count, but the things you don't want are easy. Then count everything, count the unwanted cases, and subtract. This is complementary counting, and the words "at least one" are its calling card.

The idea

How many three-digit numbers have at least one repeated digit? Counting directly means cases: exactly two digits equal (in which positions?), or all three equal. Instead, count the opposite.

All three-digit numbers: $900$ (from $100$ to $999$ ).
Three-digit numbers with no repeated digit: $9 \cdot 9 \cdot 8 = 648$ .

So $900 - 648 = 252$ have at least one repeated digit.

Complementary counting

$\#(\text{what you want}) = \#(\text{everything}) - \#(\text{what you don't want})$

Use it when the complement is simpler, especially for "at least one," "not," and "at least two" questions.

The opposite of "at least one" is "none." The opposite of "at least two" is "zero or one." The opposite of "not all the same" is "all the same."

Worked example: At least one 7

How many four-digit numbers contain at least one digit $7$ ?

All four-digit numbers: $9000$ . Four-digit numbers with no $7$ : the first digit has $8$ choices (not $0$ , not $7$ ) and each other digit has $9$ choices (not $7$ ): $8 \cdot 9 \cdot 9 \cdot 9 = 5832$ .

So $9000 - 5832 = 3168$ contain at least one $7$ .

Worked example: At least one girl

A committee of $3$ is chosen from $5$ boys and $4$ girls. How many committees include at least one girl?

All committees: $\dbinom{9}{3} = 84$ . Committees with no girls (all boys): $\dbinom{5}{3} = 10$ . So $84 - 10 = 74$ include at least one girl.

Counting directly would take three cases (exactly $1$ , $2$ or $3$ girls): $\binom{4}{1}\binom{5}{2} + \binom{4}{2}\binom{5}{1} + \binom{4}{3} = 40 + 30 + 4 = 74$ . Same answer, more work.

Worked example: Avoiding a point

How many shortest paths go from $(0, 0)$ to $(4, 4)$ , moving right or up one unit at a time, and avoid the point $(2, 2)$ ?

All paths: $\dbinom{8}{4} = 70$ . Paths through $(2, 2)$ : $\dbinom{4}{2} \cdot \dbinom{4}{2} = 6 \cdot 6 = 36$ . Paths that avoid it: $70 - 36 = 34$ .

Common mistake

Make sure the "everything" count and the "unwanted" count use exactly the same rules. If the problem is about four-digit numbers, the complement must also be four-digit numbers (leading digit not $0$ ). Mixing "four-digit numbers" with "four-digit strings" is the classic slip.

Tip

When you can, check a complementary answer by counting directly on a smaller version of the problem. For example, with two-digit numbers: $90$ total, $8 \cdot 9 = 72$ with no $7$ , so $18$ contain a $7$ . Listing them ( $17, 27, \dots, 97$ and $70, \dots, 79$ , with $77$ counted once) gives $9 + 10 - 1 = 18$ .