4
$\begingroup$

Fred needs to choose a password for a certain website. Assume that he will choose an 8-character password, and that the legal characters are the lowercase letters a, b, c, . . . , z, the uppercase letters A, B, C, . . . , Z, and the numbers 0, 1, . . . , 9. (a) How many possibilities are there if he is required to have at least one lowercase letter in his password? (b) How many possibilities are there if he is required to have at least one lowercase letter and at least one uppercase letter in his password? (c) How many possibilities are there if he is required to have at least one lowercase letter, at least one uppercase letter, and at least one number in his password? (Introduction to Probability, Blitzstein and Nwang, p.38)

Part a) is no problem, but I don't know how to define the events for b) and c). Any hint for defining the events to be able to use inclusion-exclusion?

EDIT1

Here is how I did part a).

The question is how many ways are there to choose a password having at least one lowercase letter.

  • Define $A_i$ as the set of all passwords with lowercase letter at the $i^{th}$ position.
  • $|A_i| = 26^1 \; 62^{8-1}$
  • $|A_i \cap A_j| = 26^2 \; 62^{8-2}$
  • $|\cap_{i=1}^8 A_i| = 26^i \; 62^{8-i}$

\begin{equation} |\cup_{i=1}^8 A_i| = \sum_{i=1}^8 \binom{8}{i} 26^i \; 62^{8-i} (-1)^{i+1} \end{equation}

I would like to solve the other parts in exactly the same manner, however, I don't know how to define my sets $A_i$ etc. in this case.

EDIT2

I try part c) with @AlexR's approach:

$|C| = |\Omega| - (|\neg U| + |\neg L| + |\neg N|) + (|\neg U \cap \neg L| + |\neg U \cap \neg N| + |\neg L \cap \neg N|) - |\neg U \cap \neg L \cap \neg N| = 62^8 - (36^8 + 36^8 + 52^8) + (10^8 + 26^8 + 26^8) - 0^8$

The probability of this to happen would be $0.7312$.

$\endgroup$
  • $\begingroup$ For part (b) Count all possibilities and then subtract the no. of possibilities;no upper case letters or no lower case letters Part (c) is can be done similarly $\endgroup$ – Extremal Dec 8 '14 at 16:09
  • $\begingroup$ Why do you have the factor $(-1)^{i+1}$? $\endgroup$ – Jonas Dahlbæk Dec 8 '14 at 19:10
  • $\begingroup$ @user161825 as I understand it, alternating + and - always occurs in inclusion-exclusion problems. $\endgroup$ – NoBackingDown Dec 8 '14 at 19:13
  • $\begingroup$ I don't understand; as far as I can tell, that corresponds to counting passwords with an odd number of lower case letters negatively. Maybe I am mistaken, but I think you just have to remove that factor. $\endgroup$ – Jonas Dahlbæk Dec 8 '14 at 19:25
4
$\begingroup$

(b): How many passwords are there minus how many passwords are there with no uppercase or no lowercase letter?
(c): How many passwords are there minus how many passwords are there with no uppercase or no lowercase letter or no number?

Notation: $$\Omega := \{ p\ |\ p\text{ is an } 8 \text{-digit password from the alphabet } [A-Z,a-z, 0-9]\}\\ U := \{p \in\Omega\ |\ p\text{ contains an uppercase letter}\} \\ L := \{p \in\Omega\ |\ p\text{ contains a lowercase letter}\} \\ \neg U := \Omega \setminus U = \{p\ |\ p\text{ is an } 8 \text{-digit password from the alphabet } [a-z,0-9]\} \\ \neg L := \Omega \setminus L = \{p\ |\ p\text{ is an } 8 \text{-digit password from the alphabet } [A-Z,0-9]\}$$ We trivially have $$|\Omega| = 62^8, |\neg U| = |\neg L| = 36^8$$

Example for (a):
$$|A| = |L| = |\Omega| - |\neg L| = 62^8 - 36^8$$

Example for (b):
Now there are $36$ non-uppercase and $36$ non-lowercase characters as well as $10$ non-letters so $$|B| = |U\cap L| = |\Omega| - |\neg U| - |\neg L| + |\neg U \cap \neg L| = 62^8 - 36^8 - 36^8 + 10^8$$ by inclusion-exclusion.

Can you do (c) now?

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ I added my solution to a) in my original question. Could you please show me how to define my sets systematically? In this ways, it's easier for me to learn the mechanics and general thinking behind it. $\endgroup$ – NoBackingDown Dec 8 '14 at 18:42
  • $\begingroup$ You approach will quickly let you hit a wall. I can systematically give names to the sets involved in (b) if you want, though. $\endgroup$ – AlexR Dec 8 '14 at 18:43
  • $\begingroup$ I understand, your approach greatly reduces the complexity of the problem. But considering just part a), what is actually the connection between both approachs? I can't see it how they fit together. $\endgroup$ – NoBackingDown Dec 8 '14 at 19:02
  • $\begingroup$ @Dominik You try to count $L$ directly by partition into non-disjoint subsets and removing their intersection, $$|L| = \sum |A_i| - \sum |A_i \cap A_j| + \sum |A_i \cap A_j \cap A_k| - \ldots$$ This quickly adds a lot of terms. Especially if you want to intersect $U\cap L$ in (b). $\endgroup$ – AlexR Dec 8 '14 at 19:04
  • $\begingroup$ Thank you for the clarification. I now tried part c) in my edited question. $\endgroup$ – NoBackingDown Dec 8 '14 at 19:36
0
$\begingroup$

Suggestion: consider the multinomial coefficients in multi-index notation. I hope what I am doing below is correct!

a) $$\sum_{j\geq 1} {8\choose j}26^j 36^{8-j}=\underset{\alpha_1\geq 1\\|\alpha|=8}{\sum} {8\choose \alpha}26^{\alpha_1} 26^{\alpha_2}10^{\alpha_3},$$ where $\alpha\in\mathbb N_0^3$ ranges over multiindices $\alpha=(\alpha_1,\alpha_2,\alpha_3)$ with $\alpha_1\geq 1$ and $|\alpha|=\alpha_1+\alpha_2+\alpha_3=8$ by definition. Here, the counting goes as follows: there are ${8\choose \alpha}$ ways to pick $\alpha_1$ slots in which to put lowercase letters, $\alpha_2$ slots in which to put upper case letters and $\alpha_3$ slots in which to put numbers. For any single such choice, there is $26^{\alpha_1} 26^{\alpha_2}10^{\alpha_3}$ ways to put $j$ lowercase letters in the $\alpha_1$ chosen lower case slots, $\alpha_2$ upper case case letters in the chosen upper case slots and $\alpha_3$ numbers in the chosen number slots.

The sum can be evaluated by recalling that $$\underset{|\alpha|=8\\\alpha\in \mathbb N_0^d}{\sum}{8\choose \alpha}x^{\alpha}=(x_1+\ldots+x_d)^8.$$ In particular $$ \underset{\alpha_1\geq 1\\|\alpha|=8}{\sum} {8\choose \alpha}26^{\alpha_1} 26^{\alpha_2}10^{\alpha_3}=\underset{|\alpha|=8}{\sum} {8\choose \alpha}26^{\alpha_1} 26^{\alpha_2}10^{\alpha_3}-\underset{\alpha_1=0\\|\alpha|=8}{\sum} {8\choose \alpha} 26^{\alpha_2}10^{\alpha_3}=62^8-36^8 $$

b) \begin{align*}\underset{\alpha_1\geq 1\\\alpha_2\geq 1\\|\alpha|=8}{\sum} {8\choose \alpha}26^{\alpha_1} 26^{\alpha_2} 10^{\alpha_3}&=-\underset{|\alpha|=8}{\sum} {8\choose \alpha}26^{\alpha_1} 26^{\alpha_2} 10^{\alpha_3}+2\underset{\alpha_1\geq 1\\|\alpha|=8}{\sum} {8\choose \alpha}26^{\alpha_1} 26^{\alpha_2} 10^{\alpha_3}\\ &\hspace{2cm}+\underset{\alpha_1=0\\\alpha_2=0\\|\alpha|=8}{\sum} {8\choose \alpha}26^{\alpha_1} 26^{\alpha_2} 10^{\alpha_3}=-62^8+2(62^8-36^8)+10^8. \end{align*}

c) $$\underset{\alpha_1\geq 1\\\alpha_2\geq 1\\\alpha_3\geq 1\\|\alpha|=8}{\sum} {8\choose \alpha}26^{\alpha_1} 26^{\alpha_2} 10^{\alpha_3}.$$ In order to evaluate the sum, we can evoke the inclusion-exclusion principle for sums. Let $\Omega$ denote those multiindeces in $\mathbb N_0^3$ for which $|\alpha|=8$. Then we have $$\Omega=\{\alpha_1=0\}\cup \{\alpha_2=0\}\cup \{\alpha_3=0\}\cup \{\alpha_1,\alpha_2,\alpha_3\geq 1\}.$$ We have to perform the sum over elements from $\{\alpha_1,\alpha_2,\alpha_3\geq 1\}$. Accordingly, we use the analog of the inclusion-exclusion principle for sums to arrive at $$ \sum_{|\alpha|=8}=\sum_{\alpha_1=0}+\sum_{\alpha_2=0} + \sum_{\alpha_3=0}+\sum_{\alpha_1,\alpha_2,\alpha_3\geq 1}-\sum_{\alpha_1=\alpha_2=0}-\sum_{\alpha_2=\alpha_3=0}-\sum_{\alpha_3=\alpha_1=0}+\sum_{\alpha_1=\alpha_2=\alpha_3=0}. $$ A different approach, more akin to what we did in b), would be to use $$ \Omega=\{\alpha_1\geq 1\}\cup \{\alpha_2\geq 1\}\cup \{\alpha_3\geq 1\}. $$ The result is the same, but the calculations are more daunting.

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ You may want to write out $$\binom{8}{\alpha} = \frac{8!}{\alpha_1!\alpha_2!\alpha_3!}$$ $\endgroup$ – AlexR Dec 8 '14 at 19:39
  • $\begingroup$ So that would be the solution by directly counting? As I'm new to those problems, how does direct counting compare with inclusion exclusion? $\endgroup$ – NoBackingDown Dec 8 '14 at 19:46
  • $\begingroup$ As far as I can tell from comparing AlexR's solution to part b) to my own, the inclusion-exclusion principle seems to be an elegant way to get the counting right. $\endgroup$ – Jonas Dahlbæk Dec 8 '14 at 20:08
  • $\begingroup$ @user161825 With your approach, I get for c): $62^8 - 2(62^8-36^8) - (62^8-52^8) + (10^8+26^8+26^8) - 0^8$. But that's not the same as with the other approach? $\endgroup$ – NoBackingDown Dec 8 '14 at 20:22

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.