Combinatorics, is this correct

[talolard]

Homework Statement

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.

Homework Equations

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.

 

[rasmhop]

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

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]

 

[talolard]

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

 

[talolard]

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

 

[Dick]

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.

 

[talolard]

Ok,
But what was wrong with the previous one?

 

[talolard]

I found the problem
for A123 i said there were 3 possible arangements but there are 3! possible aranegments.
Which brings us to 336

 

[Dick]

I found the problem
for A123 i said there were 3 possible arangements but there are 3! possible aranegments.
Which brings us to 336

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.

 

[talolard]

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.

 

[Dick]

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.

Ah, ok. I guess I'm easily confused. Glad you got it.