3
$\begingroup$

I am trying to practice some combinatorics problems before my discrete mathematics test, and I came up with the problem that I tried solving and would like to know if I am working in the correct path.

How many passwords can we make following these rules:

The length of the password must be exactly $8$ characters and the password must contain at least one digit and no more than $3$ digits (Only normal letters and digits are allowed).

Here is what I tried:

We have $26$ letters {$a,...,z$} and $10$ digits {$0,...,9$}.. with no restrictions, there are ${36}\choose{8}$ ways to choose the characters and arrange them in 8! ways.

Now to follow the question, we have 3 different cases that we need to calculate:

$7$ letters and $1$ digits ${26}\choose{7}$$*$${10}\choose{1}$ ways to choose them and then arrange them in $7!$

$6$ letters and $2$ digits ${26}\choose{6}$$*$${10}\choose{2}$ ways to choose them and then arrange them in $6!*2!$

$5$ letters and $3$ digits ${26}\choose{5}$$*$${10}\choose{3}$ ways to choose them and then arrange them in $5!*3!$

Final answer: We add the 3 cases together

Am I correct or is this answer $26^7*10^1+26^6*10^2+26^5*10^3$ correct, and why/what's the difference and when is each used?

$\endgroup$
  • 3
    $\begingroup$ Your original attempt is correct only in the case that we are not allowed to repeat any characters and the letters must occur before the numbers. That is not included in the stated rules so you are missing several examples such as $aaaaaa11$. Your second attempt would be correct (once correcting an apparent typo, $26^7\cdot 10+26^6\cdot 10^2+26^5\cdot 10^3$) in the event that characters are allowed to repeat however again requiring that all letters occur strictly before numbers. Again, that is not included in the stated rules. $\endgroup$ – JMoravitz May 29 '18 at 22:24
  • 3
    $\begingroup$ For a correct approach, first break into cases like you already have based on how many digits are used. Then when counting each case, first pick which locations are used by the digits. Then from left to right, choose which letter appears in spaces designated for letters and which digit is used in places designated for digits. $\endgroup$ – JMoravitz May 29 '18 at 22:25
  • $\begingroup$ A really great explanation, thanks! $\endgroup$ – Mr Pro Pop May 29 '18 at 22:38
2
$\begingroup$

A better attempt considers the 8 positions in the password, and split the problem into three disjoint cases: exactly $i$ digits where $i=1,2,3$.

To get every password with $i$ digits and $8-i$ lowercase letters, we pick the positions where the digits are going to come, in $\binom{8}{i}$ ways. At each of these positions we have 10 possibilities that we can choose independently, so $10^i$ options for those positions, and finally $26^{8-i}$ options for the remaining positions.

So in total we get $$\binom{8}{1}\cdot 10^1 \cdot 26^7 + \binom{8}{2}\cdot 10^2 \cdot 26^6 + \binom{8}{3}\cdot 10^3 \cdot 26^5$$

as the total number of passwords.

$\endgroup$
  • $\begingroup$ Thanks for that buddy. Just to make sure once again, these are possible arrangements when characters could be repeated, right? if I want to restrict it so that characters used couldn't be reused, I write it as in my first case exactly without removing anything but choosing the positions ${8}\choose{i}$, correct? Anyways, voted up and accepted the answer. $\endgroup$ – Mr Pro Pop May 29 '18 at 22:48
  • $\begingroup$ @MrProPop Yes, characters can repeat, no restrictions there. And your first case indeed chooses different characters and orders those, but that's a smaller set of passwords. $\endgroup$ – Henno Brandsma May 29 '18 at 22:51
  • $\begingroup$ Cool, cool, so for the first case ${8}\choose{1}$${26}\choose{7}$${10}\choose{1}$$7!$ and so on.. ? $\endgroup$ – Mr Pro Pop May 29 '18 at 22:55
  • $\begingroup$ @MrProPop Yes, along those lines. Note that $\binom{26}{7}7! = \frac{26!}{19!}$, which is the number of $7$-permutations out of $26$. $\endgroup$ – Henno Brandsma May 29 '18 at 23:00
  • $\begingroup$ Yeah indeed. I just wrote it down in that way for a simple step by step way of solving it clearly so that people could follow up on my work process easily, and thanks again, I totally covered how to solve such questions with(out) restrictions in different conditions ;) $\endgroup$ – Mr Pro Pop May 29 '18 at 23:05

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.