1
$\begingroup$

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$?

$\endgroup$
5
  • $\begingroup$ 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. $\endgroup$ – lulu Jan 1 '20 at 1:30
  • $\begingroup$ Okay. Sorry but I'm not sure how to fix my mistake. Can you explain? Also, for the 10*26*26, I meant it for the one of each type. So there are 26 possible for upper then lower then 10 possible for the digit. $\endgroup$ – Ryan Kwok Jan 1 '20 at 1:49
  • $\begingroup$ 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. $\endgroup$ – lulu Jan 1 '20 at 1:54
  • $\begingroup$ Oh okay. I didn't see the "at least" part. Sorry I really didn't know what I was doing. Thanks though. $\endgroup$ – Ryan Kwok Jan 1 '20 at 2:25
  • $\begingroup$ 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. $\endgroup$ – lulu Jan 1 '20 at 2:28
1
$\begingroup$

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$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.