Results 1 to 7 of 7

Math Help - Combinatorics Problem

  1. #1
    Newbie
    Joined
    May 2010
    Posts
    16

    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.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member
    Joined
    Mar 2008
    Posts
    934
    Thanks
    33
    Awards
    1
    Quote Originally Posted by mtdim View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    May 2010
    Posts
    16
    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?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Super Member
    Joined
    Mar 2008
    Posts
    934
    Thanks
    33
    Awards
    1
    Yes, that looks right.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Member oldguynewstudent's Avatar
    Joined
    Oct 2009
    From
    St. Louis Area
    Posts
    241
    Quote Originally Posted by mtdim View Post
    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?
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Newbie
    Joined
    May 2010
    Posts
    16
    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.
    Last edited by mtdim; May 1st 2010 at 05:33 PM.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Newbie
    Joined
    May 2010
    Posts
    16
    Quote Originally Posted by awkward View Post
    Yes, that looks right.
    Thanks!
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. problem in combinatorics
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: October 21st 2011, 08:23 AM
  2. Help with combinatorics problem
    Posted in the Advanced Statistics Forum
    Replies: 5
    Last Post: December 7th 2010, 03:35 PM
  3. Combinatorics problem
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: October 11th 2010, 11:52 AM
  4. Combinatorics problem
    Posted in the Statistics Forum
    Replies: 6
    Last Post: November 12th 2009, 07:05 AM
  5. Combinatorics Problem
    Posted in the Discrete Math Forum
    Replies: 9
    Last Post: March 5th 2008, 08:29 AM

Search Tags


/mathhelpforum @mathhelpforum