Counting passwords of length $8$ requiring special characters, numbers, uppercase, and lowercase letters

combinatorics

I want to count passwords of length $8$ requiring at least one of all of the following: digit, special character, uppercase letter, lowercase letter. There's $10$ digits, $15$ special characters, $26$ uppercase letters, and $26$ lowercase letters.

My approach:

Answer $=$ Total number of passwords $-$ Passwords without special character $-$ Passwords without uppercase letter $-$ Passwords without lowercase letter

Since there's $10+15+26+26=77$ total characters That's:

$$77^8-(77-10)^8-(77-15)^8-2(77-26)^8 \approx 5.198\cdot 10^{14}$$

Is this correct?

Best Answer

No, Inclusion-Exclusion is not that simple. See this article for an introduction to Inclusion-Exclusion. Then, see this answer for an explanation of and justification for the Inclusion-Exclusion formula.


For any set $~E~$ with a finite number of elements, let $~|E|~$ denote the number of elements in the set $~E.$

  • Let $~S~$ denote all of the passwords possible, if the requirements of digits, special characters, upper case letters, and lower case letters are ignored.

  • Let $~S_1~$ denote the subset of $~S~$ that violates the constraint that at least one digit must be present.

  • Let $~S_2~$ denote the subset of $~S~$ that violates the constraint that at least one special character must be present.

  • Let $~S_3~$ denote the subset of $~S~$ that violates the constraint that at least one lower case letter must be present.

  • Let $~S_4~$ denote the subset of $~S~$ that violates the constraint that at least one upper case letter must be present.

Then, the desired computation is

$$|S| - |S_1 \cup S_2 \cup S_3 \cup S_4|. \tag1 $$

  • Let $~T_0~$ denote $~|S|.$

  • For $~r \in \{1,2,3,4\},$

    let $~T_r~$ denote $\displaystyle \sum_{1 \leq i_1 < i_2 < \cdots < i_r \leq 4} | ~S_{i_1} \cap S_{i_2} \cap \cdots \cap S_{i_r} ~|.$

    That is, $~T_r~$ denotes the sum of $~\displaystyle \binom{4}{r}~$ terms.

Then, in accordance with Inclusion-Exclusion theory, the computation in (1) above equals

$$\sum_{r=0}^4 (-1)^r T_r. \tag2 $$

So, the problem reduces to computing $~T_0, ~T_1, ~T_2, ~T_3, ~T_4.$


$\underline{\text{Computation of} ~T_0}$

There are $~77~$ choices for each of $~8~$ letter positions.

Therefore,

$$T_0 = (77)^8.$$


$\underline{\text{Computation of} ~T_1}$

To compute $~|S_1|~$ note that there are $~67~$ choices for each of the $~8~$ character positions. This is because $~S_1~$ represents the subset of $~S~$ where all digits are excluded. This means that instead of there being $~77~$ choices for each character position, there are only $~(77 - 10) = 67~$ choices for each character position.

Therefore, $~|S_1| = (67)^8.$

Very similarly:

  • $~|S_2| = (62)^8.$

  • $~|S_3| = (51)^8.$

  • $~|S_4| = (51)^8.$

Therefore,

$$T(1) = |S_1| + |S_2| + |S_3| + |S_4| \\ = (67)^8 + (62)^8 + (51)^8 + (51)^8.$$


$\underline{\text{Computation of} ~T_2}$

Similar to the analysis in the previous section,
to compute $|S_1 \cap S_2|,~$ you must reason that with no digits or special characters, there are $~52~$ choices for each of the 8 character positions.

Therefore, $~|S_1 \cap S_2| = (52)^8.$

Similarly:

  • $~|S_1 \cap S_3| = (41)^8.$

  • $~|S_1 \cap S_4| = (41)^8.$

  • $~|S_2 \cap S_3| = (36)^8.$

  • $~|S_2 \cap S_4| = (36)^8.$

  • $~|S_3 \cap S_4| = (25)^8.$

Therefore,

$$T_2 = (52)^8 + (41)^8 + (41)^8 + (36)^8 + (36)^8 + (25)^8.$$


$\underline{\text{Computation of} ~T_3}$

$|S_1 \cap S_2 \cap S_3| = (26)^8,~$
since this represents the set where only capital letters are used in each of the $~8~$ character positions.

Similarly:

  • $|S_1 \cap S_2 \cap S_4| = (26)^8.$

  • $|S_1 \cap S_3 \cap S_4| = (15)^8.$

  • $|S_2 \cap S_3 \cap S_4| = (10)^8.$

Therefore,

$$T_3 = (26)^8 + (26)^8 + (15)^8 + (10)^8.$$


$\underline{\text{Computation of} ~T_4}$

$S_1 \cap S_2 \cap S_3 \cap S_4 ~$ represents the set of all 8 character sequences with no digits, special characters, lower case letters or upper case letters.

Therefore, $~S_1 \cap S_2 \cap S_3 \cap S_4 = \emptyset.$

Therefore,

$$T_4 = 0.$$


$\underline{\text{Final Computation}}$

$$T_0 = (77)^8.$$

$$T(1) = (67)^8 + (62)^8 + (51)^8 + (51)^8.$$

$$T_2 = (52)^8 + (41)^8 + (41)^8 + (36)^8 + (36)^8 + (25)^8.$$

$$T_3 = (26)^8 + (26)^8 + (15)^8 + (10)^8.$$

$$T_4 = 0.$$

The expression in (1) above equals

$$T_0 - T_1 + T_2 - T_3 + T_4.$$