Concept
How does counting the complement simplify an “at least one” condition?
Stephen Davies, Ph.D. Version 2.2.2 Through Discrete Mathematics A Cool Brisk Walk / Chapter 1
"Sometimes we have something difficult to count, but we can turn it around in terms of something much easier. Often this involves counting the complement of something, then subtracting from the total. Suppose a certain website mandated that user passwords be between 6–10 characters in length—every character being an uppercase letter, lowercase letter, digit, or special character (*, #, @, % or &)—but it also required each password to have at least one digit or special character. Without the “at least one digit or special character” part, there are 26 + 26 + 10 + 5 = 67 different choices for each character, so there are 67¹⁰ + 67⁹ + 67⁸ + 67⁷ + 67⁶ = 1,850,456,557,795,600,384 strings. It is easier to count the passwords that don’t satisfy the extra constraint: strings with 6–10 alphabetic-only characters. That is 52¹⁰ + 52⁹ + 52⁸ + 52⁷ + 52⁶ = 147,389,519,403,536,384 illegal passwords. Now subtract: total number of strings − number of illegal passwords = number of legitimate passwords. Therefore, 1,850,456,557,795,600,384 − 147,389,519,403,536,384 = 1,708,735,865,301,022,720 legitimate passwords. The lesson learned is that if counting the elements in some set involves accounting for a lot of different sticky scenarios, it’s worth a try to count the elements not in the set instead, and see if that’s easier."
Related Ideas
- Why do a set and its complement form a partition?Stephen Davies, Ph.D. Version 2.2.2 Through Discrete Mathematics A Cool Brisk Walk · Chapter 1
- What operations can be used to combine sets?Stephen Davies, Ph.D. Version 2.2.2 Through Discrete Mathematics A Cool Brisk Walk · Chapter 1
- How does the Fundamental Theorem of Counting determine the number of independent choices?Stephen Davies, Ph.D. Version 2.2.2 Through Discrete Mathematics A Cool Brisk Walk · Chapter 1
- How does counting mutually exclusive license-plate lengths illustrate addition and exponential growth?Stephen Davies, Ph.D. Version 2.2.2 Through Discrete Mathematics A Cool Brisk Walk · Chapter 1
- How do partitions simplify counting?Stephen Davies, Ph.D. Version 2.2.2 Through Discrete Mathematics A Cool Brisk Walk · Chapter 1
- What are the three basic situations behind most counting problems?Stephen Davies, Ph.D. Version 2.2.2 Through Discrete Mathematics A Cool Brisk Walk · Chapter 1
- How does the multiplication principle count costume choices with optional or unlimited accessories?Stephen Davies, Ph.D. Version 2.2.2 Through Discrete Mathematics A Cool Brisk Walk · Chapter 1
- How are all the subsets of a set formed?Stephen Davies, Ph.D. Version 2.2.2 Through Discrete Mathematics A Cool Brisk Walk · Chapter 1