Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It only takes a minute to sign up.
Sign up to join this community
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?
"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".)
