The complementation principle

Sometimes, the “opposite” of an event could be easier to count. In such cases, we can use the technique of complements. Consider an event $E .$ The complement of the event is denoted by $E^{'}$ and represents the set of outcomes not in $E .$

Technique: the complementation principle

Let $n (E)$ represent the number of ways for an event $E$ to occur and $n (total)$ represent the total number of ways for everything to occur with no restrictions. If $n (E^{'})$ represents the number of ways for $E$ not to occur, then $n (E) = n (total) - n (E^{'}) .$

Example: counting using complements

Question

A five-digit number is formed using the digits 1,2,3,4,5,6,7,8,9. Repetitions are allowed.

How many of these numbers contain repeated digits?

Commentary

The condition of repeated digits is difficult to count directly. Consider, for example, the numbers 11234, 11223, 11134. There are so many possibilities to have repetitions!

Situations like this is where considering the complement simplifies the process. It is much easier to count the opposite: a number that does not contain any repetition.

Solution

Total number of ways $= 9^{5} = 59,049.$

Number of ways for numbers without repeated digits $= 9 \times 8 \times 7 \times 6 \times 5 = 15,120.$

Required number of ways $= 59,049 - 15,120 = 43,929 ∎ .$