Results 1 to 6 of 6

Math Help - Permutation and Combination

  1. #1
    jjc
    jjc is offline
    Newbie
    Joined
    Feb 2008
    Posts
    4

    Permutation and Combination

    How many ways can you arrange 8 people in a row so that any two of the three people, A, B and C are together and all 3 of them cannot be together? The answer gives as (3C2 x 2! x 7!) - (3! x 6!) - (3C2 x 2! x 6C1 x 5!) = 21600

    why?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Flow Master
    mr fantastic's Avatar
    Joined
    Dec 2007
    From
    Zeitgeist
    Posts
    16,948
    Thanks
    5
    Quote Originally Posted by jjc View Post
    How many ways can you arrange 8 people in a row so that any two of the three people, A, B and C are together and all 3 of them cannot be together? The answer gives as (3C2 x 2! x 7!) - (3! x 6!) - (3C2 x 2! x 6C1 x 5!) = 21600

    why?
    Well, my reasoning would be:

    (a) Get how many arrangements have any two of A, B or C sitting together and don't worry about whether the third is with them or not.

    (b) Get how many arrangements have all three of A, B and C sitting together.

    Then subtract (b) from (a) ....

    (a) = (number of ways of choosing a 'unit' of two from the three) times (number of ways of arranging within the 'unit') times (number of ways of arranging the 'unit' and the remaining six people) = {3 \choose 2} \, 2! \, 7!

    (b) = (number of ways of arranging within a 'unit' of three) times (number of ways of arranging the 'unit' of three and the remaining five people) = 3! \, 6!

    So I get {3 \choose 2} \, 2! \, 7! - 3! \, 6!

    At the moment I can't really see where the third term comes from .... someone better at arranging than I am might jump in and explain .....
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Super Member

    Joined
    May 2006
    From
    Lexington, MA (USA)
    Posts
    11,683
    Thanks
    615
    Hello, jjc!

    I agree with Mr. F . . . I don't understand that third term.


    How many ways can you arrange 8 people in a row
    so that any two of the three people, A, B and C are together
    and all 3 of them cannot be together?

    The answer is: . \left[{3\choose2}\cdot2!\cdot7!\right) - [3!\cdot 6!] - \underbrace{\left[{3\choose2}\cdot 2!\cdot {6\choose1} \cdot 5!\right]}_{{\color{red}???}} \;= \;21,600
    My reasoning is the same . . .


    Select two of them to sit together.
    There are: . {\color{blue}{3\choose2}} ways . . . say, A and B,
    . . They can be ordered in {\color{blue}2!} = 2 ways: . AB or BA.

    Duct-tape the two together.
    . . There are 7 "people" to arrange: . {\color{blue}7!} ways.

    Hence, there are: . {\color{red}{3\choose2}(2!)(7!)} ways for some two to sit together.

    But this includes the cases where all three sit together.
    . . We must deduct these cases.


    Duct-tape the three together.
    . . The three can be ordered in {\color{blue}3!} ways.
    There are 6 "people" to arrange: {\color{blue}6!} ways.

    Hence, there are: . {\color{red}(3!)(6!)} ways for all three to sit together.


    Therefore, there are: . {3\choose2}(2!)(7!) - (3!)(6!) \;=\;\boxed{{\bf{\color{blue}25,920}} \text{ ways}}

    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,605
    Thanks
    1574
    Awards
    1
    I agree with the other two about the third term. But I disagree about the answers they came up with.
    The given answer, 21600, is correct.

    There are 6 ways, (AB, AC, BA, BC, CA, CB), for two of the three to sit together.
    Now we have in the pattern _D_E_F_G_H_ six places to put one of those pairs and the five places to put the remaining third-person out so that the three are not seated together.
    That gives (6)(6)(5)(5!)=21600.

    So I think the given answer is correct, but I cannot understand the why of makeup of those three terms.

    Post Script
    There are {6 \choose 3}(5!)(3!) ways to separate A, B, & C.
    There are (8!)-{6 \choose 3}(5!)(3!) ways that at least two of those are together. But this number also includes cases in which all three are together.
    So There are (8!)-{6 \choose 3}(5!)(3!)-(3!)(6!)=21600.
    Last edited by Plato; February 16th 2008 at 05:59 AM.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Flow Master
    mr fantastic's Avatar
    Joined
    Dec 2007
    From
    Zeitgeist
    Posts
    16,948
    Thanks
    5
    Quote Originally Posted by Plato View Post
    I agree with the other two about the third term. But I disagree about the answers they came up with.
    The given answer, 21600, is correct.

    There are 6 ways, (AB, AC, BA, BC, CA, CB), for two of the three to sit together.
    Now we have in the pattern _D_E_F_G_H_ six places to put one of those pairs and the five places to put the remaining third-person out so that the three are not seated together.
    That gives (6)(6)(5)(5!)=21600.

    So I think the given answer is correct, but I cannot understand the why of makeup of those three terms.

    Post Script
    There are {6 \choose 3}(5!)(3!) ways to separate A, B, & C.
    There are (8!)-{6 \choose 3}(5!)(3!) ways that at least two of those are together. But this number also includes cases in which all three are together.
    So There are (8!)-{6 \choose 3}(5!)(3!)-(3!)(6!)=21600.
    Arrangements under restriction always cause trouble - to me, anyway.

    I'm sorry Plato - I don't follow your reasoning here. Or rather, I don't see why your reasoning (which I don't follow) is correct whereas the reasoning of Soroban and myself is wrong ..... I guess I've got a problem with the Minority Report

    (Mind you, I've only just woken up and am eating breakfast ....)
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,605
    Thanks
    1574
    Awards
    1
    Quote Originally Posted by mr fantastic View Post
    I don't see why your reasoning (which I don't follow) is correct whereas the reasoning of Soroban and myself is wrong ..... I guess I've got a problem with the Minority Report
    Well my answer does agree with the answer given by the text. I got the same by two different ways.
    It took me a moment to realize the mistake in yours and Soroban’s reasoning.
    Here it is.
    The difference in the two solutions is 25920 - 21600 = 4320.
    That happens to be the same numbers as 6(6!).
    That means that you both have counted the three sitting together twice.
    Here is how that was done. Think of counting the strings that begin “ABC…”
    That string is counted once when counting strings containing the pair AB: \boxed{AB}C \cdots .
    The same string is counted again when you both counted stings using the pair BC: A\boxed{BC} \cdots.
    Thus in counting the pair strings {3 \choose 2}(6!)(2) you have counted the strings containing the three together twice each.
    Now {3 \choose 2}(6!)(2) - (2)(6)(6!)=21600.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Permutation and Combination
    Posted in the Statistics Forum
    Replies: 3
    Last Post: October 21st 2008, 07:14 AM
  2. combination/permutation
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: October 16th 2008, 11:40 PM
  3. permutation and combination
    Posted in the Statistics Forum
    Replies: 1
    Last Post: October 11th 2008, 07:42 AM
  4. Permutation and Combination
    Posted in the Statistics Forum
    Replies: 2
    Last Post: September 28th 2008, 09:37 PM
  5. Combination/Permutation
    Posted in the Statistics Forum
    Replies: 6
    Last Post: September 11th 2007, 03:42 PM

Search Tags


/mathhelpforum @mathhelpforum