Charles Petzold

A friend from my PC Magazine days recently posted on Facebook a little mathematics anomaly that he encountered while trying to figure out the number of possible passwords under certain conditions. He began with the stipulation that a four-character password had to be constructed from characters from each of four groups: 26 uppercase letters (which I’ll abbreviate as U), 26 lowercase letters (L), 10 numeric digits (N), and 18 special characters (S), for a total of 80.

He began thinking about choosing a character from these 80, which happened to be uppercase. That left 54 characters to choose from. He picked another, which happened to be lowercase. That left 28. He chose another, which happened to be a numeric digit, leaving the remaining 18. Hence he calculated the number of possibilities as:

But then he wondered: What if the first character he chose from the 80 possibles was a special character, leaving 62 possibles, and the next was a numeric digit, leaving 52 possibles, and the next was a lowercase letter, leaving 26 possibles, and then an uppercase letter. By the same logic, the combinations would be:

Clearly something is wrong. But that’s one of the wonderful characteristics of math: If you don’t get the same answer regardless how you do it, you know you’ve messed up somewhere.

Here’s the fallacy:

If the first character picked is an uppercase letter, then that either happens randomly or deliberately. Two cases:

(1) If it happens randomly, then the calculation has to include a probability of that happening, which is $\frac{26}{80}$. And if the second character picked from the remaining 54 happens to be a lowercase letter, then the probability of that happening is $\frac{26}{54}$. The probability of the third character being a numeric digit is similarly $\frac{10}{18}$. The actual number of combinations of ULNS passwords is therefore:

Notice that numbers start canceling out like crazy, and you’re left with:

(2) If you’re deliberately choosing the first character from uppercase letters, then it’s not 80 possibilities but 26 possibilies. The total possibilities are the same whether you choose the characters in the order ULNS or SNLU or anything else. It’s also the total when the order of the characters in the password doesn’t matter:

Of course, order does matter with passwords, so this must be multiplied by the number of different orderings of U, L, N, and S. which is 4 possibilities for the first character, times 3 for the second, times 2 for the third, and 1 for the last, or $4\times 3\times 2\times 1=24$, which is conveniently abbreviated as 4! and called 4 factorial:

That is the total number of four-character passwords where all four character groups are included and order matters.

If you increase the length of the password beyond four characters but still require that it contain characters from the four character groups, the number of possible passwords increases (of course) but the math gets more complicated. Let’s begin with five characters but with the additional requirement that all five characters must be unique. The total is:

You’ve already chosen four of the possible 80 characters so if all the characters must be unique, the fifth character is from a pool of 76, and then the product is multiplied by 5! (or 120) to account for all the different orderings. Similarly, for six-character passwords with all unique characters:

In general, for N-character passwords where all the characters are unique, the number of possibilities is:

When duplicate characters are allowed (as is usually the case with passwords), the math starts getting messy. There are more characters to choose from for additional characters, but you’re also generating duplicate passwords that you don’t want to count in the total.

Maybe some other time.