Each user on a computer system has a password, which is six characters long, where each character is an uppercase letter or digit. Each password must contain at least one digit. How many possible passwords are there?
Why am I incorrect in reasoning that the answer is $10*36^5$? If every password must contain a digit, then there are only $10$ ways to choose one character in the password and $36^5$ ways to choose the other 5 characters.
Best Answer
You’re not taking into account that the digit can occur in any of the six positions. There are $10\cdot36^5$ passwords that begin with a digit. There are also $10\cdot36^5$ passwords that end with a digit; some of these also begin with a digit and have already been counted, but some do not, so your figure of $10\cdot36^5$ is necessarily too small.
The easiest way to count the acceptable passwords is to note that there are $36^6$ six-character strings made up of upper-case letters and digits, and $26^6$ of them are made up entirely of letters, so there are $36^6-26^6$ that include at least one digit.
It is possible to count them directly, but the counting is more complicated. For each of the $6$ positions in the password there are $10\cdot36^5$ passwords having a digit in that position, so to a first approximation there are $6\cdot10\cdot36^5$ acceptable passwords. However, as noted in the first paragraph, this counts some passwords more than once. For each pair of positions in the password there are $10^2\cdot36^4$ passwords having digits in both of those positions, and all of these passwords have been counted twice. Since there are $\binom62$ pairs of positions, we must subtract $\binom62\cdot10^2\cdot36^4$ to get rid of the double-counting. Unfortunately, this overcompensates, and there are further corrections to be made. The net result, given by the inclusion-exclusion principle, is
$$\sum_{k=1}^6(-1)^{k+1}\binom6k10^k36^{6-k}\;.$$
Either way, the result is $1,867,866,560$.