Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I am working on a homework problem where I need to find the total number of passwords that have exactly 8 characters.

Constraints:

  • each character is either an uppercase letter (A..Z) or a digit (0..9)
  • each password must contain at least 2 digits

Here is what I have so far:

I know that each there are 8 characters in each password so the total number of passwords should be the product of the number of choices for each of the 8 slots, barring the constraints.

So for 6 of the slots I have 36 options, 26 letters and 10 digits, and for the other two slots I can only choose digits, since the constraints state that I must have at least 2 digits; this leaves me with this:

$36^6 \times 10 \times 10 = 217\, 678\, 233\, 600$

This gives me over 200 billion passwords(which seems really large), is there anyway that I can use the C(n,r) formula to verify this result?

Any help would be appreciated.

EDIT: New Solution

Taking your advice I computed the total number of passwords $P_t$ you could have with 8 characters, them computed the total with $i$ digits in any position in the password where $1 \leq i \leq 8$

$$P_t = 36^8 = 2,821,109,907,456$$

Let $Q_i$ be the total number of passwords with $i$ digits that appear anywhere in the string:

$$Q_0 = C(8,0) * 10^0 * 26^8 = \text{208,827,064,576}$$ $$Q_1 = C(8,1) * 10^1 * 26^7 = \text{642,544,814,080}$$ $$Q_2 = C(8,2) * 10^2 * 26^6 = \text{864,964,172,800}$$ $$Q_3 = C(8,3) * 10^3 * 26^5 = \text{665,357,056,000}$$ $$Q_4 = C(8,4) * 10^4 * 26^4 = \text{319,883,200,000}$$ $$Q_5 = C(8,5) * 10^5 * 26^3 = \text{98,425,600,000}$$ $$Q_6 = C(8,6) * 10^6 * 26^2 = \text{18,928,000,000}$$ $$Q_7 = C(8,7) * 10^7 * 26^1 = \text{2,080,000,000}$$ $$Q_8 = C(8,8) * 10^8 * 26^0 = \text{100,000,000}$$

Now since I am only looking for passwords where there are at least 2 digits, only $Q_1$ is invalid since it does not have at least 2 digits. So the total number of passwords with at least 2 digits is $\sum_{i=2}^{8} Q_i$ or just $(P_t - Q_1 - Q_0)$

$$\sum_{i=2}^{8} Q_i = Q_2 + Q_3 + Q_4 + Q_5 + Q_6 + Q_7 + Q_8 = 1,969,738,028,800$$

or

$$\begin{align*} P_t - Q_1 - Q_0 &= 2,821,109,907,456 - 642,544,814,080 - 208,827,064,576\\ &= 1,969,738,028,800 \end{align*}$$

share|improve this question
    
Why do you want to verify this using $\binom{n}{r} $? –  Quixotic Mar 19 '12 at 4:15
    
Since you mention this is homework, I suggest you add the "homework" tag. –  Alex Becker Mar 19 '12 at 4:18
    
@Foool I don't know if the answer is right, and am looking for a way to verify it. –  Hunter McMillen Mar 19 '12 at 4:20
    
@AlexBecker Thank you, I re-tagged the question. –  Hunter McMillen Mar 19 '12 at 4:20
1  
You never count in how many ways you are selecting which slots will be forced to have numbers in them; so you are only counting the number of passwords in which a specific two slots have numbers (say, last and penultimate slots). If you add a factor to account for that, you will end up overcounting. My suggestion: count the total number without restrictions, count the number of passwords with exactly one number and 7 letters; and count the number of passwords with all letters. –  Arturo Magidin Mar 19 '12 at 4:25

2 Answers 2

up vote 2 down vote accepted

The number may seem high, but it's actually too low. Just as a hint: You certainly have counted the password abcdef12. But did you count 12abcdefg?

share|improve this answer
    
I have revised my answer, please review it when you have time. –  Hunter McMillen Mar 19 '12 at 15:20
    
I think Arturo's comment to your revised version sums it up - it's correct, but a bit unnecessary extra work; you had $P_t$ already and only needed $Q_0$ and $Q_1$. –  Desiato Mar 19 '12 at 17:21

Hint: It is easier to count all the $8$ character passwords and subtract the ones that don't have two digits-how many total $8$ character strings are there? How many are there with no digits? For the $1$ digit ones, you have how many ways to choose where the digit goes?

share|improve this answer
    
I have revised my answer, please review it when you have time. –  Hunter McMillen Mar 19 '12 at 15:20
    
@HunterMcMillen: Looks good now. –  Ross Millikan Mar 19 '12 at 16:13

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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