1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Combinatorics, is this correct

  1. Jun 11, 2010 #1
    1. The problem statement, all variables and given/known data
    6 children are sitting arounbd a round table, with each chair numbered from 1 to six. In how many ways can we rearange them so that no child sits across from the child who was across him before.


    2. Relevant equations



    3. The attempt at a solution
    Because the chairs are numbered it makes a difference where each child sits.
    To seat the 1st child, A, we have 6 options, and 5 open seats remain.
    To seat the child that previously sat across from A, A', we have 4 options. And 4 seats remain
    To seat the 3rd child, B, we have 4 options, and 3 open seats remain.
    To seat the child that previously sat across from B, B', we have 2 options. And 2 seats remain
    To seat the 5th child, C, we have 2 options, and 1 open seats remain.
    To seat the child that previously sat across from C,C', we have 1 option.

    Notice that by the way we sat the other children, C and C'can not be across from each other.

    in total there are 6*4*4*2*2= 384.
     
  2. jcsd
  3. Jun 11, 2010 #2
    This is incorrect.

    Label the positions 1a, 2a, 3a, 1b, 2b, 3c where 1a is across from 1b, 2a is across from 2b and 3a is across from 3b.

    Now let me make some choices according to your procedure:

    Let A sit at 1a.
    Let A' sit at 2a.
    Let B sit at 1b.
    Let B' sit at 2b.
    Let C sit at 3a.
    Then C' must sit at 3b which is across form C.



    Instead try consider both the children and chairs in pairs.

    At 1a, 1b we must choose one pair that does not sit here.
    At 2a, 2b we must choose one pair that does not sit here, but it cannot be the same as before as that would leave that pair to occupy 3a and 3b.

    Now just consider the ways to assign the kids to their pairs. For instance a valid assignment would be:

    1: AB (pair C left out)
    2: BC (pair A left out)
    3: AC (pair B left out)

    Now there are two ways to assign the two members of pair A to their seats, and similarily for B and C.



    EDIT: Didn't see the places were numbered.
    [STRIKE]As a final note consider the following two configurations of children (where of course the first and last person sit beside each other as it's a round table):

    ABCA'B'C'

    BCA'B'C'A

    Are these different? (remember the table is round)[/STRIKE]
     
  4. Jun 12, 2010 #3
    Thanks for the help,
    Heres another attempt, in that spirit:

    We denote 1a,1b,2a,2b,3a,3c the six seats around the table so that 1a is across from 1b. We have three pairs.
    There are 6! Ways to seat six children around the table.
    Let A1 be all of the ways that at least one pair of children from the previous arrangement still sit next to each other. We chose one pair from three that will sit across from each other, there are 6 ways to seat them so that they are across from each other and we have 4! Ways to arrange the rest.
    So |A!|=3*6*4!=432
    |All of the arangemnts|-|A1|=6!-432=144
     
    Last edited: Jun 12, 2010
  5. Jun 12, 2010 #4
    We denote 1a,1b,2a,2b,3a,3c the six seats around the table so that 1a is across from 1b. We have three pairs.
    There are 6! Ways to seat six children around the table.
    Let 1A be all of the ways that at least one pair of children from the previous arrangement sit across from each other in 1a and 1b. We chose one pair from three that will sit across from each other, there are 2 ways to seat them so that they are across from each other and we have 4! Ways to arrange the rest.
    So |A1|=3*2*4!=144
    Likewise for A2 and A3
    A12 is all the ways for one pair to be in 1a and 1b and another to be in 2a and 2b.
    There are 3 ways to chose 2 pairs from 3. there are two ways to place the pairs, and 4 ways for the internal aranagments. and 2 ways to seat the other two kids.
    So |A12|=3*4*2*2=48
    As above |A12|=|A13|=|A32|
    A123 is all of the ways that all of the pairs are still across from each other. There are 3 ways to place the pairs and 2 ways to arrange each pair so |A123|=3*8=24
    From the inclusion exclusion principle, all of the ways that at least one pair still sits across from each other is
    6!-3A1+3A12-A123=6!-3*144+3*48-24=408
    So all of the ways for no pair to be sitting next to each other is 6!-40=312
     
  6. Jun 12, 2010 #5

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    No, 312 is wrong. Let A, B, and C be any selected 3 of the children and a, b and c be the ones that sit across from them. Seat A, B and C first. There are two different ways to do this, i) none of A, B and C are across from each other or ii) a pair in A, B and C are across from each other. How many cases in i) and ii)? Now count the ways to seat a, b and c in each case.
     
  7. Jun 13, 2010 #6
    Ok,
    But what was wrong with the previous one?
     
  8. Jun 13, 2010 #7
    I found the problem
    for A123 i said there were 3 possible arangements but there are 3! possible aranegments.
    Which brings us to 336
     
  9. Jun 13, 2010 #8

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    I really can't follow what you are doing. But 336 is wrong too. The 384 in your first post correct, but I don't think the reasoning is correct. When you seat B, it makes a difference whether B sits across from A or not.
     
  10. Jun 13, 2010 #9
    Thanks Dick,
    Your right. 336 is all of the ways at least one pair is still sitting across from each other. 6!-336=384 is all the ways no pair is sitting across from each other.
    I apologize for writing unclearly, I'll recap the logic. Basically I used the inclusion exclusion principle to count in how many ways at least one pair was still across from each other. Then I subtracted that from all of the possibilities.
     
  11. Jun 13, 2010 #10

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    Ah, ok. I guess I'm easily confused. Glad you got it.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Combinatorics, is this correct
  1. Help with (dx^2/dy^2) (Replies: 9)

  2. Is this correct (Replies: 3)

  3. Are these correct (Replies: 3)

  4. Is it correct? (Replies: 0)

  5. Is this Correct (Replies: 10)

Loading...