Help needed with alternative approach to solve the problem of counting passwords.

Question

In the book titled 'Combinatorics- A Guided Tour' by David Majur', there is stated on pg. #20, the problem, as also stated below.

How many $8$ char. passwords are there if each character is either an uppercase letter $A-Z$, a lowercase letter $a-z$, or a digit $0-9$, & where at least one uppercase & at least one lowercase letter are used.

The shorter, easier & usual approach is to use the Inclusion - exclusion principle, & take help by taking complements, as below:

Take the complement of the case of : 'at least one upper-case letter' & 'at least one lower-case letter'.
This leads to: $B ∪ C$; with $B$ = 'no upper-case letter'; $C$ = 'no lower-case letter'.

So, need take difference from the set of all possible passwords, leading to : $|A| - |B∪C|$.

Now, taking by inclusion-exclusion principle, the fact: $|B∪C|= |B|+|C|-|B∩C|$, leading to $|A| - |B|-|C|+|B∩C|$.
The values of $|A|, |B|, |C|, |B∩C|$ are: $|A|= 62^8, |B|=36^8, |C|=36^8, |B∩C|=10^8$.
$|A| - |B|-|C|+|B∩C| = 62^8 - 36^8 - 36^8 + 10^8 = 212,697,985,769,984.$

---

I wanted alternate approach that computes the actual passwords by applying product rule for each case, & then applying sum rule for adding up the different cases as shown below; but am unable to get the correct answer as shown below:

The cases are :
(a) At least one digit is there, e.g. 1Uppercase-1Lowercase-6Digit, denoted by 1U1L6D. All the options are:
(i) $1U1L6D = 26^2\cdot 10^6$, permutations : $$1U2L5D, 2U1L5D = 26^3\cdot 10^5$$ $$1U3L4D, 3U1L4D = 26^4\cdot 10^4$$ $$1U4L3D, 4U1L3D = 26^5\cdot 10^3$$ $$1U5L2D, 5U1L2D = 26^6\cdot 10^2$$ $$1U6L1D, 6U1L1D = 26^7\cdot 10^1$$

=> $26^2\cdot 10^6+2\cdot (26^3\cdot 10^5 + 26^4\cdot 10^4 + 26^5\cdot 10^3 + 26^6\cdot 10^2 + 26^7\cdot 10^1)$

=> $259,512,830,720$

(b) No digit is there. All the options are:
$$1U7L, 7U1L = 26^8$$ $$2U6L, 6U2L = 26^8$$ $$3U5L, 5U3L = 26^8$$ $$4U4L = 26^8$$ $$5U3L, 3U5L = 26^8$$ $$6U2L, 2U6L = 26^8$$ $$7U1L, 1U7L = 26^8$$

=> $26^8\cdot 13 = 2,714,751,839,488$

The sum of the above two cases is: $259,512,830,720 + 2,714,751,839,488 = 2,974,264,670,208$.

---

Update : The responses have been incorporated in the below update:

(a) At least one digit is there, e.g. 1Uppercase-1Lowercase-6Digit, denoted by 1U1L6D. All the options are:
(i)

$1U1L6D :$ sel. positns.:$\binom{8}{1,1,6}$, ordering$ = 26^2\cdot 10^6$, permutations : $\binom{8}{1,1,6}26^2\cdot 10^6$,
$1U2L5D, 2U1L5D :$ sel. positns.:$\binom{8}{1,2,5}$, ordering$= 26^3\cdot 10^5$, permutations : $\binom{8}{1,2,5}26^3\cdot 10^5$,
$1U3L4D, 3U1L4D :$ sel. positns.:$\binom{8}{1,3,4}$, ordering$= 26^4\cdot 10^4$, permutations : $\binom{8}{1,3,4}26^4\cdot 10^4$,
$1U4L3D, 4U1L3D :$ sel. positns.:$\binom{8}{1,3,4}$, ordering$= 26^5\cdot 10^3$, permutations : $\binom{8}{1,3,4}26^5\cdot 10^3$,
$1U5L2D, 5U1L2D :$ sel. positns.:$\binom{8}{1,2,5}$, ordering$= 26^6\cdot 10^2$, permutations : $\binom{8}{1,2,5}26^6\cdot 10^2$,
$1U6L1D, 6U1L1D $ sel. positns.:$\binom{8}{1,1,6}$, ordering$= 26^7\cdot 10^1$, permutations : $\binom{8}{1,1,6}26^7\cdot 10^1$,

=> $\binom{8}{1,1,6}26^2\cdot 10^6 + 2\cdot (\binom{8}{1,2,5}26^3\cdot 10^5 + \binom{8}{1,3,4}26^4\cdot 10^4 + \binom{8}{1,3,4}26^5\cdot 10^3 + \binom{8}{1,2,5}26^6\cdot 10^2 + \binom{8}{1,1,6}26^7\cdot 10^1)$

==> $56\cdot 26^2\cdot 10^6$ + $2\cdot (168\cdot 26^3\cdot 10^5 + 0\cdot 26^4\cdot 10^4 + 280\cdot 26^5\cdot 10^3 + 168\cdot 26^6\cdot 10^ + 56\cdot 26^7\cdot 10^1)$

===> 37856000000+ $2\cdot (295276800000 + 1919299200000 + 3326785280000 + 5189785036800 + 4497813698560)$

====>$30,495,776,030,720$

$2U2L4D :$ sel. positns.:$\binom{8}{2,2,4}$, ordering$ = 26^4\cdot 10^4$, permutations : $\binom{8}{2,2,4}26^4\cdot 10^4$,
$2U3L3D, 3U2L3D :$ sel. positns.:$\binom{8}{3,2,3}$, ordering$= 26^5\cdot 10^3$, permutations : $\binom{8}{3,2,3}26^5\cdot 10^3$,
$2U4L2D, 4U2L2D :$ sel. positns.:$\binom{8}{2,2,4}$, ordering$= 26^6\cdot 10^2$, permutations : $\binom{8}{2,2,4}26^6\cdot 10^2$,
$2U5L1D, 5U2L1D :$ sel. positns.:$\binom{8}{1,2,5}$, ordering$= 26^7\cdot 10^1$, permutations : $\binom{8}{1,2,5}26^7\cdot 10^1$,

=> $\binom{8}{2,2,4}\cdot 26^4\cdot 10^4 + 2\cdot (\binom{8}{3,2,3}26^5\cdot 10^3 + \binom{8}{2,2,4}26^6\cdot 10^2 + \binom{8}{1,2,5}26^7\cdot 10^1)$

==> $420\cdot 26^4\cdot 10^4 +2\cdot ( 560\cdot 26^5\cdot 10^3 + 420\cdot 26^6\cdot 10^2 + 168\cdot 26^7\cdot 10^1)$

===> $1919299200000+ 2\cdot (6653570560000 + 12974462592000 + 22489068492800)$

====> $86153502489600$

$3U3L2D :$ sel. positns.:$\binom{8}{2,3,3}$, ordering$ = 26^6\cdot 10^2$, permutations : $\binom{8}{2,3,3}26^6\cdot 10^2$,
$3U4L1D, 4U3L1D :$ sel. positns.:$\binom{8}{3,4,1}$, ordering$= 26^7\cdot 10^1$, permutations : $\binom{8}{3,4,1}26^7\cdot 10^1$,

=> $560\cdot 26^6\cdot 10^2 + 2\cdot (280\cdot 26^7\cdot 10^1)$

==> $560\cdot (30891577600 + 80318101760)$

===> $560\cdot (111209679360) = 62277420441600$

Sum of all cases' counts in (a) : $178926698961920$

(b) No digit is there. All the options are:

$1U7L, 7U1L :$ sel. positns.:$\binom{8}{1,7}$, ordering$ = 26^8$, permutations : $\binom{8}{1,7}\cdot 26^8$,
$2U6L, 6U2L :$ sel. positns.:$\binom{8}{2,6}$, ordering$ = 26^8$, permutations : $\binom{8}{2,6}\cdot 26^8$,
$3U5L, 5U3L :$ sel. positns.:$\binom{8}{3,5}$, ordering$ = 26^8$, permutations : $\binom{8}{3,5}\cdot 26^8$,
$4U4L :$ sel. positns.:$\binom{8}{4,4}$, ordering$ = 26^8$, permutations : $\binom{8}{4,4}\cdot 26^8$,
$5U3L, 3U5L :$ sel. positns.:$\binom{8}{3,5}$, ordering$ = 26^8$, permutations : $\binom{8}{3,5}\cdot 26^8$,
$6U2L, 2U6L :$ sel. positns.:$\binom{8}{2,6}$, ordering$ = 26^8$, permutations : $\binom{8}{2,6}\cdot 26^8$,
$7U1L, 1U7L :$ sel. positns.:$\binom{8}{1,7}$, ordering$ = 26^8$, permutations : $\binom{8}{1,7}\cdot 26^8$,

=> $4\cdot(\binom{8}{1,7}\cdot 26^8 + \binom{8}{2,6}\cdot 26^8 + \binom{8}{3,5}\cdot 26^8) + (\binom{8}{4,4}\cdot 26^8)$

==> $4\cdot(8\cdot 26^8 + 28\cdot 26^8 + 56\cdot 26^8) + (70\cdot 26^8)$

===> $4\cdot(1670616516608 + 5847157808128+ 11694315616256) + (14617894520320)$

====> $4\cdot (19212089940992) + 14617894520320= 76848359763968 + 14617894520320 = 91466254284288$

---

Sum of all cases' counts in (a) & (b) : $270,392,953,246,208$

Still mismatch is there as the sum crosses the correct value by $57,694,967,476,224$.

Answer 1

A possible way to use multiplicative principle to solve the problem is by using a recurrence relation.

Let $L[j]$ be the number of password of length $j$ that consists of at least $1$ lowercase letter and no uppercase letters at all.

We can write down $L[j]=36^j - 10^j$ immediately.

Or we can do it the longer way by observing that $$L[0]=0$$ and by multiplicative principle, we have

$$L[j] = 36L[j-1]+26(10^{j-1}).$$

We can solve the recurrence as follows:

\begin{align} L[j] &= 36L[j-1]+26(10^{j-1})\\ &=36^kL[j-k] + 26\sum_{r=0}^{k-1} 36^r(10^{j-1-r}) \\ &=26 \cdot 10^{j-1}\sum_{r=0}^{j-1} \left(\frac{36}{10} \right)^r \\ &= 26 \cdot 10^{j-1} \cdot\frac{\left( \frac{36}{10}\right)^j-1}{\frac{36}{10}-1} \\ &= 36^j - 10^j \end{align}

That was a warm up.

Similarly, we define $U[j]$ be the number of password of length $j$ that consists of at least $1$ uppercase letter and no lowercase letters at all.

By symmetry, $L[j]=U[j]$.

Now, let's define $A[j]$ to be the password of length $j$ that consists of at least $1$ uppercase and at least one lowercase letter.

We have $A[0]=0$ and

$$A[j]=62A[j-1] + 26L[j-1] + 26U[j-1]$$

Again, we can solve the recurrence relation.

\begin{align} A[j] &= 62A[j-1] + 52(36^{j-1}-10^{j-1}) \\ &= 62^k A[j-k] + 52 \sum_{r=0}^{k-1} 62^r(36^{j-1-r}-10^{j-1-r}) \\ &= 52 \sum_{r=0}^{j-1} 62^r(36^{j-1-r}-10^{j-1-r}) \\ &= 52 \left( 36^{j-1} \sum_{r=0}^{j-1}\left( \frac{62}{36}\right)^r- 10^{j-1}\sum_{r=0}^{j-1}\left( \frac{62}{10}\right)^r\right) \\ &= 52 \left( 36^{j-1}\cdot \frac{\left( \frac{62}{36}\right)^j-1}{\frac{62}{36}-1} - 10^{j-1}\cdot \frac{\left( \frac{62}{10}\right)^j-1}{\frac{62}{10}-1} \right) \\ &= 52 \left( 36^{j}\cdot \frac{\left( \frac{62}{36}\right)^j-1}{26} - 10^{j}\cdot \frac{\left( \frac{62}{10}\right)^j-1}{52} \right) \\ &= 2(62^j) - 2(36^j)-62^j +10^j \\ &= 62^j - 2(36^j) + 10^j \end{align}

Answer 2

There are indeed $26^2\cdot10^6$ possibilities for $1U1L6D$ when it comes to choosing the characters.

But how about the number of arrangements?

E.g. a561F324 is another password than 361aF542, right?

If the $6$ digits are distinct then there are $8!$ arrangements, but if e.g. they are all the same then there are $2\binom82$ arrangements.

So the $1U1L6D$ passwords must be subdivided again, and this time based on the diversity of the digits. Then for each situation you must find the number of arrangements.

That will be quite a job.

Reasons enough to be happy with inclusion/exclusion :-).

Answer 3

You are missing cases. For instance, two uppercase letters, four lowercase letters, and two digits. You have also not accounted for the positions of the various types of characters within the sequence.

To determine the total number of cases, let $x_d$, $x_l$, and $x_u$ denote, respectively, the number of digits, lowercase letters, and uppercase letters that appear in the sequence. Then $$x_d + x_l + x_u = 8 \tag{1}$$ The requirement that at least one uppercase and at least one lowercase letter appear in the sequence means $x_u \geq 1$ and $x_u \geq 1$. Since there is no such requirement for the number of digits, $x_d \geq 0$.

Let $x_d' = x_d + 1$. Then $x_d'$ is a positive integer. Substituting $x_d' - 1$ for $x_d$ in equation 1 yields \begin{align*} x_d' - 1 + x_l + x_u & = 8\\ x_d' + x_l + x_u & = 9 \tag{2} \end{align*} Equation 2 is an equation in the positive integers. A particular solution of equation 2 corresponds to the placement of two addition signs in the eight spaces between successive ones in a row of nine ones. $$1 \square 1 \square 1 \square 1 \square 1 \square 1 \square 1 \square 1 \square 1$$ For instance, placing an addition in the third and fifth spaces yields $$1 1 1 + 1 1 + 1 1 1 1$$ which corresponds to the solution $x_d' = 3$ ($x_d = 2$), $x_l = 2$, $x_u = 4$. Thus, the number of cases is the number of ways we can select two of the eight spaces to be filled with addition signs, which is $$\binom{9 - 1}{3 - 1} = \binom{8}{2} = 28$$

Also, you have to account for the positions of the characters.

For the case of four uppercase and four lowercase letters, you must multiply the $26^4$ ways of selecting the uppercase letters and the $26^4$ ways of selecting the lowercase letters by the $\binom{8}{4}$ ways to choose the positions of the upper case letters and $\binom{4}{4}$ ways of filling the remaining four positions with the lowercase letters, so there are $$\binom{8}{4}26^4\binom{4}{4}26^4$$ such arrangements.

For the case of two uppercase letters, four lowercase letters, and two digits, in addition to selecting two uppercase letters in $26^2$ ways, four lowercase letters in $26^4$ ways, and two digits in $10^2$ ways, you must choose two of the eight positions for the uppercase letters, four of the remaining six positions for the lowercase letters, and fill the remaining two positions with digits. Hence, there are $$\binom{8}{2}26^2 \cdot \binom{6}{4}26^4 \cdot \binom{2}{2}10^2$$ such arrangements.

Answer 4

By now you must appreciate the power of the Principle of Inclusion / Exclusion! I can't resist pointing out that the problem can be solved even more simply with an exponential generating function (EGF).

The EGF for words formed with upper case letters and containing at least one letter is $(e^z)^{26}-1$. The EGF for words formed with lower-case letters and containing at least one letter is the same. The EGF for words formed with digits (0-9) is $(e^z)^{10}$. So the EGF for words containing at least one upper case letter, at least one lower case letter, and zero or more digits is $$\begin{align} f(z) &= (e^{26z}-1)^2 \; e^{10z}\\ &= e^{62z} - 2 e^{36z} + e^{10z} \end{align}$$ The number of ways to form an acceptable password of length 8 is the coefficient of $\frac{1}{8!} z^8$ in $f(z)$, which is $$\boxed{62^8 - 2 \times 36^8 + 10^8}$$