What is wrong with my answer to this combinatorics question?

QUESTION: Each user on a computer system has a password, which is six characters long, where each character is an uppercase letter or a digit. Each password must contain at least one digit. How many possible passwords are there? (Modified version of an example Rosen Discrete Maths book)

MY ANSWER: since the password MUST have at least a digit then we can start by picking out this digit first which can be done in $$10$$ ways and the rest can be digits and letters which will be $$36$$(i.e $$10$$ digits + $$26$$ Uppercase letters) each case.

So the number of possible passwords is $$10 \times 36^{5} = 604,661,760$$

ANSWER FROM THE BOOK: We have to know all possible passwords $$= 36^{6}$$ and from this subtract passwords without a digit $$26^{6}$$
Therefore number of possible passwords = $$36^6 - 26^6 = 1,867,866,560$$

I understand why the second one is correct but i don't understand how the first one is wrong.

• You are computing the passwords that have a digit in the first position(see it as a cartesian product if you want $\{1,2,\cdots ,9\}\times \{1,2,\cdots ,9,a,\cdots ,z\}^5$), which is a different thing. Commented Nov 17, 2023 at 12:31
• As a general guideline: If a problem says you have to have at least $N$ of something (but you could have more) and your solution is to first pick $N$ choices of that thing and then choose the rest of the objects, it's probably wrong. Commented Nov 17, 2023 at 14:41

Your solution takes into account only the password that start with a number, the rest could be anything. You should multiply by $$6$$ to choose the position of that number. $$6\times 10\times36^5 = 3,627,970,560$$ This value is way to high. Why? A lot of password are counted multiple times. Such as

• choosing 1 as the first character (forced number) then the rest is abcd5 : 1abcd5
• choosing 5 as the last character (forced number) then the rest is 1abcd : 1abcd5

It will be hard to remove those multiple password since they depend on how many numbers there are.

• If there are one number in the password, it is counted only once, nothing to do here;
• If there are two numbers in the password, it is counted twice. How many password have exactly two numbers : $${6\choose2}\times10^2\times26^4=685,464,000$$;
• If there are three numbers in the password, it is counted three times. How many password have exactly three numbers : $${6\choose3}\times10^3\times26^3=351,520,000$$;
• If there are four numbers in the password, it is counted four times. How many password have exactly four numbers : $${6\choose4}\times10^4\times26^2=101,400,000$$;
• If there are five numbers in the password, it is counted five times. How many password have exactly five numbers : $${6\choose5}\times10^5\times26=15,600,000$$;
• If there are six numbers in the password, it is counted six times. How many password have exactly six numbers : $${6\choose6}\times10^6=1,000,000$$.

Numbers of different passwords that satisfy your condition: \begin{align}3,627,970,560-685,464,000 &-2\times351,520,000-3\times101,400,000\\ &-4\times15,600,000-5\times1,000,000=1,867,866,560\end{align}

Since it is a lot of work, it would have been simplier to evaluate how many passwords have 1 number, how many have two, etc. It would give us the same answer. \begin{align}{6\choose1}\times10\times26^5 &+{6\choose2}\times10^2\times26^4+{6\choose3}\times10^3\times26^3\\ &+{6\choose4}\times10^4\times26^2+{6\choose5}\times10^5\times26+{6\choose6}\times10^6=1,867,866,560\end{align}

I believe that your method would count "5ABCDE" the same as "ABCDE5" but clearly they are different.

If you want to take this approach, you are essentially designating a preferred role to the digit carrying position. In order to fix this, you would need to take 6 copies of what you computed (i.e., where the role of 'digit' position is each of the possible positions) and then apply inclusion-exclusion to remove the arrangements you've counted twice.

To illustrate this, let us think of the much simpler scenario where the passwords have just 2 entries. The correct result needs to be $$36^2-26^2=10\cdot 62=620$$.

If you do it your way, you have to look at the first position being a digit and the second arbitrary and vice-versa, giving $$2\cdot 10\cdot 36=720$$ possibilities. However, by doing this, you have counted the passwords that just consist of digits twice. There are $$10^2=100$$ of those, so the total number of valid passwords would indeed be $$720-100=620$$.