5
$\begingroup$

In how many ways can eight people, denoted $A,B,C,D,E,F,G,H$ be seated about a square table that seats two people on each side?

My approach:

Since each side of the table seats two people, there are $2$ possible arrangements for two people sitting on a side (for example, $AB$ and $BA$). Given $8$ people, there are $8!$ ways to arrange them, and to avoid over counting rotations, we have $\frac{8!}{8}$ ways to arrange $8$ people around the table. So we have a total possible arrangements of $$2*\left(\frac{8!}{8}\right)=\frac{8!}{4}=10,080.$$


If two of the eight people, say $A$ and $B$, do not get along well, how many different seatings are possible with $A$ and $B$ not sitting next to each other?

My approach:

There are two cases to consider by which $A$ is next to $B$, the first case $AB$ and the second case $BA$ (but they don't have to be on the same side of the square when this happens). These two cases give us $2*6!$ possible arrangements.


Is my approach to these problems correct? My approach to the second one feels incomplete, or even incorrect. As there must be a two step process, as I must find the number of arrangements by which the condition is met and also avoid over counting the rotations.

$\endgroup$
  • 1
    $\begingroup$ Does sitting together also allow for sitting adjacent at a corner (e.g. if the layout is a chessboard, the table on b2-c2-c3-b3; is a2 & b1 together, or just b1 & c1 [plus rotations])? $\endgroup$ – sjb Oct 16 '15 at 9:12
5
$\begingroup$

Consider the complement: how many ways can they be seated such that $A$ and $B$ must sit next to each other? Well, imagine gluing the couple together as a single superperson $\boxed{AB}$. Note that we could also permute the two people within the superperson, so there are $2!$ ways to do this. Next, we must now permute the $7$ people, giving us $7!$ possibilities. But because a square can be rotated four times, we overcounted by a factor of $4$. Putting everything together and subtracting from the result from the first problem, we obtain: $$ \frac{8!}{4} - \frac{2!7!}{4} = \frac{8 \cdot 7! - 2 \cdot 7!}{4} = \frac{6 \cdot 7!}{4} = \frac{3 \cdot 7!}{2} = 7560 $$

$\endgroup$
  • $\begingroup$ I did upvote your answer, but I later realized that this approach is wrong, and gives incorrect result. The answer below is the correct one. In your approach, the mistake is in the step where you're calculating number of cases where A and B are always together. $\endgroup$ – patentfox Nov 22 '15 at 13:44
1
$\begingroup$

A and B sitting next to each other on same side gives us 2(6!), A and B sitting next to each other on different side gives us another 2(6!) therefore total no of arrangements where A and B not sitting next to each other =2(7!)-2(6!)-2(6!) =7200

$\endgroup$
  • 1
    $\begingroup$ doesn't it look weird to you that you get a different answer than that accepted one? $\endgroup$ – Surb Jul 29 '15 at 13:13
  • $\begingroup$ This should be the accepted answer. This has correct approach and gives the correct final answer. $\endgroup$ – patentfox Nov 22 '15 at 13:41
1
$\begingroup$

So I see you divide by 8 to avoid over-counting rotations...but only for odd rotations does the actual orientation change (i.e. if they move over two spaces at once, no change in relative orientation) and odd is one half the possible rotations, of eight, making 4 total.....so accounting for the number of possible permutations divided by the repeat factor, the total is 8!/4.....and there's no need to multiply by 2 for reverse orientations because they are all accounted for by the permutation calculation....so you got the right answer but only because you made two mistakes that cancelled each other out

$\endgroup$
  • $\begingroup$ It's not quite like a circular table though, because although A and B can't sit next to each other on the same side, they can be next to each other as long as they are on different edges. This means that we just have to remove 1/2 of all the possibilities when A and B are next to each other. The number of ways for A and B to be next to each other is 2 x 2/8 [C] = 2x[8!/(2!6!)] = 56....take 1/2 of this to get 28. Thus we say the number of ways to orient them without A and B next to each other on the same edge of the table is (1 - 1/28)(8!/4) = (27/28)x(8!/4) $\endgroup$ – whorton May 4 '16 at 7:00
  • $\begingroup$ Actually, I should have multipled that 1/28 by a factor of 8 for all the different sets of 2 in a cyclic set of 8....that would give 8/20 to subtract from 1, bringing us to (20/28)(8!/4) = 7200 $\endgroup$ – whorton May 4 '16 at 7:18
1
$\begingroup$

With seats unnumbered, and seating next to each other on different sides treated as adjacent,
it virtually becomes a circular table.

$A$ can be seated anywhere as reference point. $B$ can't sit on the adjacent seat on either side, so has only $5$ choices.

The rest can be permuted in $6!$ ways, thus ans $= 5*6! = 3600$


Note: It is incorrect to multiply by $2$ for $AB-BA$, that is taken care of automatically.

$\endgroup$
0
$\begingroup$

a) 8 People can sit 8! different ways. A possible arrangement will be considered not changed if we rotate it 90°, 180° and 270° so in this 8! every 4 cases counted as 1. Therefore the answer is $$ \frac{8!}{4} = 10080$$

b) For A there are 8 possible seats. Then for B there will be 6 seats available ( all seats except beside A). Fore the rest since there is no restriction the number of available seats will be 6,5,4,3,2,1, in order. Therefore there will be 8*6*6*5*4*3*2*1* arrangements, but again there are 4 symmetric arrangements. So the answer is: $$ \frac{8*6*6*5*4*3*2*1}{4} = 8640$$

c) For A there are 8 possible seats again. Then for B there will be 4 seats available ( all seats except beside and opposite of A). Fore the rest since there is no restriction the number of available seats will be 6,5,4,3,2,1, in order. Therefore there will be 8*4*6*5*4*3*2*1* arrangements, but again there are 4 symmetric arrangements. So the answer is: $$ \frac{8*4*6*5*4*3*2*1}{4} = 5760$$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy