Results 1 to 6 of 6

Math Help - Combinatorics question

  1. #1
    Junior Member
    Joined
    Dec 2010
    Posts
    62

    Combinatorics question

    IN how many ways can the letters in MISSISSIPPI be arranged so that no two Is are adjacent?

    The solution is allegedly {{8}\choose{4}} { 7! \over 2!4!1!}


    But I don't see the logic to this solution. Any insights would be greatly appreciated.

    Thanks, MD
    Last edited by Mathsdog; November 29th 2011 at 01:27 AM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor FernandoRevilla's Avatar
    Joined
    Nov 2010
    From
    Madrid, Spain
    Posts
    2,162
    Thanks
    45

    Re: Combinatorics question

    Hint: Consider the four I's as a block, then we have seven elements:

    \boxed{IIII}\;MSSSSP,\;\ldots,\; MS\;\boxed{IIII}\; SPSS,\ldots

    We have \frac{7!}{2!4!1!} arrangements of those seven elements. Now, move conveniently the four I's.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Dec 2010
    Posts
    62

    Re: Combinatorics question

    Hey, thanks for your reply FernanoRevilla. That makes sense. (n.b. I left an extra P out of MISSISSIPPI, but have now edited it in). But I still dont see where the  {8 \choose4} comes from. If the four had to remain in a block then the solution would be  {8 \choose 1} but if any of the positions can be chosen for any of the Is then some of these will contain adjacent Is and others will not eg. MISISISISPP It seems to me this will be included in the {8 \choose 4} factor. No?

    Thanks again, MD
    Last edited by Mathsdog; November 29th 2011 at 09:53 AM.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,663
    Thanks
    1616
    Awards
    1

    Re: Combinatorics question

    Quote Originally Posted by Mathsdog View Post
    IN how many ways can the letters in MISSISSIPPI be arranged so that no two Is are adjacent?
    The solution is allegedly {{8}\choose{4}} { 7! \over 2!4!1!}
    Reply #2, answered a different questiona: "all I's are adjacent'.
    For two Is are adjacent, consider "MSSSSPP" that string can be arranged is \frac{7!}{2!\cdot 4!} ways.
    Now look at "_M_S_S_S_S_P_P_" there are eight spaces into which the I's can be placed.
    Choose four if them: \binom{8}{4}.
    Last edited by Plato; November 29th 2011 at 05:57 AM.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor FernandoRevilla's Avatar
    Joined
    Nov 2010
    From
    Madrid, Spain
    Posts
    2,162
    Thanks
    45

    Re: Combinatorics question

    Quote Originally Posted by Plato View Post
    Reply #2, answered a different questiona: "all I's are adjacent'.
    No, considering all I's adjacent was a strategy. For that reason I said: now, move conveniently the four I's.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Super Member

    Joined
    May 2006
    From
    Lexington, MA (USA)
    Posts
    11,738
    Thanks
    645

    Re: Combinatorics question

    Hello, Mathsdog!

    In how many ways can the letters in MISSISSIPPI be arranged
    so that no two I's are adjacent?

    The solution is allegedly: {8\choose4} { 7! \over 2!4!1!}

    Arrange the letters \{P,P,S,S,S,S,M\} in a row.

    . . There are: {7\choose2,4,1} \:=\:\frac{7!}{2!\,4!\,1!} arrangements.


    Insert a space before, after and between the seven letters:

    . . \square\;X\;\square\;X\;\square\;X\;\square\;X\; \square \;X\;\square\;X\;\square\;X\;\square


    Choose 4 of the 8 spaces and insert the I's.

    . . There are:. {8\choose4} choices.


    Therefore, there are:. {8\choose4}\,\frac{7!}{2!\,4!\,1!} ways.

    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. combinatorics question
    Posted in the Discrete Math Forum
    Replies: 6
    Last Post: April 10th 2011, 10:37 AM
  2. Combinatorics question
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: January 17th 2011, 03:56 PM
  3. Question about Combinatorics
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: April 5th 2010, 04:13 AM
  4. Combinatorics question
    Posted in the Statistics Forum
    Replies: 2
    Last Post: December 16th 2008, 10:12 AM
  5. Combinatorics question
    Posted in the Advanced Math Topics Forum
    Replies: 5
    Last Post: December 8th 2007, 02:12 PM

Search Tags


/mathhelpforum @mathhelpforum