1
$\begingroup$

$A,B,C,D$ and $E$ are five persons who are to be seated around a circular table such that $A$ and $B$ must sit together and $C$ and $D$ must never sit together. In how many ways can they be seated?

My Attempt:

Step 1:

First we make $(AB)$ and $E$ sit which can be done in $2$ ways since $A$ and $B$ can arrange themselves in $2!=2$ ways.

Step 2:

One of $C$ and $D$ can be put into gaps between $E$ and $A$ and the other can be put into the gap between $B$ and $E$ for which there are obviously $2$ ways.

To obtain total number of ways it appears that we should multiply number of ways in Step 1($=2$) and number of ways in Step 2($=2$) ways, i.e. total number of ways $=2\times 2=4$.

But it is easy to notice that in these $4$ ways two of the arrangements are rotation of the other two.

So should the answer be $4$ or should it be $2$.

In general what should be the approach?

Say we have $10$ persons sitting around a circular table with $3$ of them wanting to sit together only whereas $4$ other persons do not want to sit next to each other?

Should the rotation of a particular arrangement be construed as same or different?

$\endgroup$
  • 2
    $\begingroup$ The rotation of a particular arrangement is the same. In other words, a rotation doesn't create a distinct arrangement. $\endgroup$ – learning Nov 11 '17 at 1:16
  • 1
    $\begingroup$ The four arrangements you described are ABCED, ABDEC, BACED, and BADEC. These are all rotationally distinct, so the answer is four. $\endgroup$ – Mike Earnest Nov 11 '17 at 2:20
3
$\begingroup$

$A$, $B$, $C$, $D$ and $E$ are five persons who are to be seated around a circular table such that $A$ and $B$ must sit together and $C$ and $D$ must never sit together. In how many ways can they be seated?

There are four possible seating arrangements.

Seat E. Since A and B sit together and C and D are separated, C and D must both be adjacent to E. Therefore, choosing whether C or D sits to E's immediate left also determines who sits to E's immediate right and choosing whether A or B sits two seats to E's left also determines who sits two seats to E's right. Hence, there are $2 \cdot 2 = 4$ permissible seating arrangements, as shown below.

five_people_sitting_in_a_circle

Notice that none of these seating arrangements can be obtained from another by rotation.

Should the rotation of a particular arrangement be construed as the same or different?

By convention, a rotation of a particular arrangement is considered to be the same unless the seats are labeled or we are given a particular reference point (such as a special chair or the north end of the table).

Notice that we have already accounted for rotational invariance by measuring our seating arrangements relative to the position of E.

Say we have $10$ persons sitting around a circular table, with $3$ of them wanting to sit together and $4$ other persons who wish to be separated? In how many ways can they be seated?

We use the block of three people who wish to sit together as our reference point. Say the people are $A$, $B$, and $C$. In how many ways can they be arranged within the block?

$3!$

Suppose the four people who wish to be separated are $D$, $E$, $F$, and $G$. Since there are only seven seats left at the table, they must be seated in the seats that are $1$, $3$, $5$, and $7$ positions to the left of the block. In how many ways can they be seated?

$4!$

Let's call the remaining three people $G$, $H$, and $I$. In how many ways, can they be seated in the remaining three chairs?

$3!$

Therefore, by the Multiplication Principle, the number of permissible seating arrangements is

$3!4!3!$

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.