# Number of possible passwords - combinatorics

This question has been asked and answered before:

An online portal requires a user login with a password which must be from 6 to 8 characters long, where each character is a lowercase letter or a digit. A password must contain at least 1 digit. How many possible passwords are there?

All answers so far either use the inclusion exclusion pie or sum the number of words with exactly 1 digit (and thus 26 choices for all other characters) plus the words with exactly 2 digits and so on.

When I saw this problem in class my first thought was: we are only going to deal with words of length $$6$$ and then add the cases where the word length is $$7$$ or $$8$$ (as these choices are mutually exclusive). We can choose from $$26+10=36$$ options for each character except for one in each word, since one character must be a digit so we have $$10$$ choices for this specific character and $$6$$ positions in which this character can be. Thus we must have $$6\cdot10\cdot36^5$$ possible passwords, which I understand is wrong since all possible passwords with length 6 without the at least one digit constraint are $$36^6$$ which is less than what we calculated before.

Our professor emphasized the fact that we have at least one digit and not exactly one. However I fail to understand where I am wrong intuitively. I can see the numbers do not make sense but I cannot exactly understand where I am miscounting (maybe counting some combinations twice?).

• Think of the complement: $$n(\text{at least 1)}=n(\text{all possibilities})-n(\text{none}).$$ Commented Apr 12, 2021 at 0:26
• Subtract the number of passwords with no digits from the number of passwords you could form if there were no restrictions for each possible password length, then add the three cases. Commented Apr 12, 2021 at 0:29
• Your method counts each password with more than one digit multiple times, once for each time a digit appears in the password. Commented Apr 12, 2021 at 0:30
• @AndrewChin that's exactly the inclusion-exclusion pie. I understand that, however I'm trying to look at it from another perspective Commented Apr 12, 2021 at 0:37

## 1 Answer

The expression $$6\cdot10\cdot36^5$$ has a particular "special" character picked out as "the character which had to be a digit".

In a password like misha1 there is a unique character which is a digit, which must be that particular "special" character, so there is no problem.

But a password like 23fish has two digits, and either one of might be the special character. You count it once when you pick the first character as the digit character, put a 2 there, and fill in the rest with 3fish. You count it again when you pick the second character as the digit character, put a 3 there, and fill in the rest with 2_fish. A password like 456789 gets counted $$6$$ times.

You could correct your approach. If you think of $$6 \cdot 10 \cdot 36^5$$ as $$10 \cdot 36^5 + 10 \cdot 36^5 + 10 \cdot 36^5 + 10 \cdot 36^5 + 10 \cdot 36^5 + 10 \cdot 36^5$$ where the $$i^{\text{th}}$$ term counts the passwords where the $$i^{\text{th}}$$ character is a digit, it's easy to see that there's overlap. Instead, to avoid overlap, you could make the $$i^{\text{th}}$$ term count the passwords where the $$i^{\text{th}}$$ character is the first digit that occurs. Then we get $$10 \cdot 36^5 + 26 \cdot 10 \cdot 36^4 + 26^2 \cdot 10 \cdot 36^3 + 26^3 \cdot 10 \cdot 36^2 + 26^4 \cdot 10 \cdot 36 + 26^5 \cdot 10$$ and this is another expression for the correct number of $$6$$-character passwords with at least one digit.

I'm also going to include the "standard" approach for the sake of anyone else who finds this question, though I understand that you're already aware of it.

That's to count all $$6$$-character passwords, then subtract the ones which don't have any digits, leaving only the ones that do. We get $$36^6 - 26^6$$ as the answer with this approach.

• Thanks for your clear and precise answer. That was exactly the kind of explanation I was looking for! Commented Apr 12, 2021 at 0:47