Thread: 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.

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.

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?

Yes, that looks right.

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* *4*3*2*1

Does this look reasonable?

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.

Originally Posted by awkward

Yes, that looks right.

Thanks!