Combinatorics Question: 8-Letter Passwords

[nyr91188]

Homework Statement

How many eight-letter passwords using the letters A-Z are there in which up to one letter is allowed to be used more than once?

Homework Equations

The Attempt at a Solution

I broke the problem up based on repetition of one letter: (26)₈ ways with no repetition, (8 choose 2)*26*(25)₆ ways with letter repeated once, (8 choose 3)*26*(25)₅ ways with letter repeated twice, and so on, until 26 ways with letter repeated 7 times filling all 8 spaces. Adding these 8, gives the total ways.

 

[Bacle2]

Do you mean _at most_ one repretition?

Maybe inclusion/exclusion would help: Count the number of ways in which you can get exactly 1 repetition, then exactly two repetitions,..., exactly 8 repetitions, and then use inclusion/exclusion starting with 26^8 possible combinations.

 

[nyr91188]

That's the exact question from the book. It means either no letters are repeated or one letter can be repeated as many times as you want.

I didn't learn inclusion/exclusion yet so I don't think we are supposed to use it.

So, I counted the ways in which there is no repetition, there is exactly one repetition, exactly 2 repetitions, and so on. Then, I added these up to give me the total ways in which one letter is allowed to be used more than once.

 

[Bacle2]

Well, if no letters are repeated, then you are just choosing 8 letters out of 8.

And then you could consider separately cases in which exactly one letter is repeated. You seem to be on the right track on your first post; I can't tell where you're stuck.

 

[nyr91188]

Sorry, I'm not really stuck. I just can't ever be sure that I'm even on the right track with these kind of problems. So, I just wanted to get some input to make sure I'm not way off. Thanks for your help.

 

[Bacle2]

No problem; if you post your answer in detail, maybe we can see better what (may be) wrong.

 

[nyr91188]

I did (26)₈ + (8 choose 2)*(26)₇ + (8 choose 3)*(26)₆ + (8 choose 4)*(26)₅ + (8 choose 5)*(26)₄ + (8 choose 6)*(26)₃ + (8 choose 7)*(26)₂ + 26

This is based on no repetition + exactly 1 rep. + exactly 2 rep. + exactly 3 rep. + exactly 4 rep. + exactly 5 rep. + exactly 6 rep. + exactly 7 rep.

For no rep., there are obviously (26)₈ ways.
For 1 rep., choose 2 places for repeating digits. Repeating digits can be chosen in 26 ways and the rest of the digits can be chosen in (25)₆ ways. Similarly, for the rest up to exactly 7 rep. in which there are of course 26 ways to have the password contain all of the same character.