2

How many $8$ character passwords are there if each character is either an uppercase letter A-Z, a lower case letter a-z, or a digit 0-9, and where at least one character of each of the three types is used?

So there are $26 \cdot 26 \cdot 10$ for the Uppercase, lowercase, and digit. Then we have $\binom{8}{3}$ ways to put them in the password. $\binom{8}{3} = 56$. Then the rest of the $5$ character slots can be anything. So $26+26+10 = 62$. So we have $62^5$. So wouldn't the answer just be $26^2 \cdot 10 \cdot 56 \cdot 62^5$?

N. F. Taussig
  • 76,571
Ryan Kwok
  • 137
  • Your calculation is hard to follow. What does "So there are 26⋅26⋅10 for the Uppercase, lowercase, and digit." mean? More significantly: you can't place the "one of each type" first and then toss the others in randomly without overcounting badly. Easier to do it by inclusion-exclusion. – lulu Jan 01 '20 at 01:30
  • Okay. Sorry but I'm not sure how to fix my mistake. Can you explain? Also, for the 102626, I meant it for the one of each type. So there are 26 possible for upper then lower then 10 possible for the digit. – Ryan Kwok Jan 01 '20 at 01:49
  • But then why write it as a product? That's just confusing. As to the more fundamental error, you can't "pre-choose" the one-of-each-type. Say your password was $Aa1AAAAA$. Which of those six $A's$ was the pre-chosen one? Indeed, you'll count this at least $6$ times, one for each $A$. But inclusion-exclusion works well for this sort of problem. Give that a try. – lulu Jan 01 '20 at 01:54
  • Oh okay. I didn't see the "at least" part. Sorry I really didn't know what I was doing. Thanks though. – Ryan Kwok Jan 01 '20 at 02:25
  • Yes, that "at least" should not be there (it belonged to a different sort of example which I ended up discarding). Your method would count $Aa1AAAAA$ exactly six times. – lulu Jan 01 '20 at 02:28

1 Answers1

2

You are counting each password multiple times, once each for the number of uppercase letters, lowercase letters, and digits that appear in the password.

There are $26 + 26 + 10 = 62$ ways each of the eight positions could be filled, so there are $62^8$ possible passwords. From these, we must subtract those in which there are no uppercase letters, no lowercase letters, or no digits.

Let $P$ be the set of all passwords. Let $U$, $L$, and $D$ be, respectively, the set of passwords that contain an uppercase letter, a lowercase letter, or a digit. Then we wish to find $$|U \cap L \cap D| = |P| - |U' \cup L' \cup D'|$$ By the Inclusion-Exclusion Principle,

$$|U' \cup L' \cup D'| = |U'| + |L'| + |D'| - |U' \cap L'| - |U' \cap D'| - |L' \cap D'| + |U' \cap L' \cap D'|$$

$|U'|$: $U'$ is the set of passwords that do not contain uppercase letters. That leaves $62 - 26 = 36$ characters we can use to fill each of the eight positions in the password. Hence, $|U'| = 36^8$.

$|L'|$: $L'$ is the set of passwords that do not contain lowercase letters. Hence, $|L'| = 36^8$.

$|D'|$: $D'$ is the set of passwords that do not contain digits. That leaves $62 - 10 = 52$ characters we can use to fill each of the eight positions in the password, so $|D'| = 52^8$.

$|U' \cap L'|$: $U' \cap L'$ is the set of passwords that contain neither uppercase nor lowercase letters. That means each position in the password must be filled with one of the ten digits, so $|U' \cap L'| = 10^8$.

$|U' \cap D'|$: $U' \cap D'$ is the set of passwords that contain neither uppercase letters nor digits. That means each position in the password must be filled with one of the $26$ lowercase letters, so $|U' \cap D'| = 26^8$.

$|L' \cap D'|$: $L' \cap D'$ is the set of passwords that contain neither lowercase letters nor digits. That means each position in the password must be filled with one of the $26$ uppercase letters, so $|L' \cap D'| = 26^8$.

$|U' \cap L' \cap D'|$: $U' \cap L' \cap D'$ is the set of passwords that contain no uppercase letters, no lowercase letters, and no digits, which is impossible, so $|U' \cap L' \cap D'| = 0$.

N. F. Taussig
  • 76,571