1
$\begingroup$

Given a set of $n$ people, find a formula for the number of ways to seat $r$ of them around a circular table, where seatings are considered the same if every person has the same two neighbors without regard to which side these neighbors are sitting on.

What I have so far is:

We can see that there is $\binom{n}{r}$ ways to seat $r$ people out of $n$. But how do I do the second part? I've seen people do examples online with a divisor, but how does it work in this case?

$\endgroup$
2
  • $\begingroup$ Lets say that your n people are sorted by age. When you put the people in the table, always put the older person facing north in the table. Now put the other people, notice that now the circle becomes a line! $\endgroup$
    – Phicar
    Oct 15, 2020 at 3:18
  • $\begingroup$ Nice observation! To be hones't I do see how this relates with the divisor? I see that you have people to the left and right, and we may have over counted them. How do I get rid of this over counting? $\endgroup$
    – user750949
    Oct 15, 2020 at 3:23

1 Answer 1

1
$\begingroup$

"Around a circular table, where seatings are considered the same if every person has the same two neighbors without regard to which side these neighbors are sitting on" means that (1) we care only about relative — not absolute — positions, and that (2) clockwise and counter-clockwise arrangements are not distinguished from each other.

In other words, ABC, BCA, CAB, and BAC, ACB, CBA are all equivalent arrangements.

If considering just condition $1$:

  • In a row, there would have been $r$ ways of assigning the leftmost seat. In a circle however, there is no such seat, so we divide the number of arrangements in a row $^nP_r$ by this $r$.

  • In other words: around a circle, all arrangements are equivalent under rotation.

  • Yet another framing: $^nC_r$ ways to choose $r$ people from the $n$, then $1$ way to seat any one of the chosen $r$ people at any seat at the circular table, then $(r-1)!$ ways to seat the remaining people relative to that first person seated.

  • So: $$^nC_r\times1\times(r-1)!=\frac{n!}{(n-r)!r}=\frac{^nP_r}{r}$$ ways to arrange the people in a circular table if clockwise and anticlockwise arrangements are regarded as different.

  • Here's the beacon Prof. Scott's fantastic explanation:
    https://math.stackexchange.com/a/1508539/21813

But when taking both conditions $1$ & $2$ into account, the above expression needs to be halved to compensate for the double-counting. So the total number of ways is $$\frac{^nC_r (r-1)!}2=\frac{n!}{2r(n-r)!}=\frac{^nP_r}{2r}.$$ (This is sometimes called arranging on a 'ring', because turning a ring over to obtain the reverse ordering of beads isn't considered a new "arrangement".)

$\endgroup$
2
  • 1
    $\begingroup$ Shouldn't this be $\frac{nPr}{2r}$ to account for the condition "without regard to which side these neighbors are sitting on"? That sounds like, referring to the example you gave, EDCBA et al would also be equivalent arrangements to ABCDE. $\endgroup$
    – A.J.
    Oct 15, 2020 at 5:46
  • $\begingroup$ @A.J. Thanks for pointing out that! I've just corrected the answer. $\endgroup$
    – ryang
    Oct 15, 2020 at 6:27

You must log in to answer this question.