# Combinatorics Problem

Printable View

• May 1st 2010, 03:32 PM
mtdim
Combinatorics Problem
Hello folks. I'm new here, but I was looking for a place where I could get some math help, as this problem has me completely stumped. It goes like this:

From the alphabet {a,b,c,d,e,f}, how many 20 letter "words" (i.e. arrangements) can be made such that no consecutive letters are the same and every letter appears at least once.

The question comes with a hint to use inclusion/exclusion, but since there are two criteria which much be satisfied, I'm not exactly sure about how to attack it this way. Should I consider each criteria separately, or do them together? Any tips would be greatly appreciated.
• May 1st 2010, 03:50 PM
awkward
Quote:

Originally Posted by mtdim
Hello folks. I'm new here, but I was looking for a place where I could get some math help, as this problem has me completely stumped. It goes like this:

From the alphabet {a,b,c,d,e,f}, how many 20 letter "words" (i.e. arrangements) can be made such that no consecutive letters are the same and every letter appears at least once.

The question comes with a hint to use inclusion/exclusion, but since there are two criteria which much be satisfied, I'm not exactly sure about how to attack it this way. Should I consider each criteria separately, or do them together? Any tips would be greatly appreciated.

Here is an approach which I think can be made to work.

First compute the number of words in which no consecutive letters are the same (without any restriction on the number of letters used).

Say a word has "property i" if it has no consecutive letters the same and also does not contain the ith letter in the set {a, b, c, d, e, f}.

Then use PIE to compute the number of words which have none of the forbidden properties.
• May 1st 2010, 04:54 PM
mtdim
Ah, thank you! For some reason I though that finding the intersections between the properties would be real tough, but I found it was actually quite simple once you suggested I just go ahead with it. For the record, the answer I got is:

6*5^19 - C(6,1)*5*4^19 + C(6,2)*4*3^19 - C(6,3)*3*2^19 + C(6,4)*2*1^19

Does that look right to you?
• May 1st 2010, 04:59 PM
awkward
Yes, that looks right.
• May 1st 2010, 05:10 PM
oldguynewstudent
Quote:

Originally Posted by mtdim
Ah, thank you! For some reason I though that finding the intersections between the properties would be real tough, but I found it was actually quite simple once you suggested I just go ahead with it. For the record, the answer I got is:

6*5^19 - C(6,1)*5*4^19 + C(6,2)*4*3^19 - C(6,3)*3*2^19 + C(6,4)*2*1^19

Does that look right to you?

I did not get that answer but I tried a different approach:

The 1st letter has 6 possibilities which gives the 2nd letter 5 possibilities. Now you've used 2 of the 6 letters, to make sure you use all 6 letters make the 3rd letter have 4 possibilities, the 4th letter have 3 possibilities, 5th letter have 2 possibilities, and the 6th letter have 1 possibility. Now letters 7-20 have 5 possibilities each so as not to duplicate the previous letter.

Putting it all together gives 6* $5^{15}$*4*3*2*1

Does this look reasonable?
• May 1st 2010, 05:20 PM
mtdim
oldguynewstudent, I think your method undercounts. For example, there are many cases where the 6*5^15 will cause all six letters to be used, meaning that, in those cases, lowering the other multiplicands to 4, 3, 2 and 1 unnecessarily omits certain words.
• May 1st 2010, 05:22 PM
mtdim
Quote:

Originally Posted by awkward
Yes, that looks right.

Thanks!