# How many different ways to seat n people in a round table of m seats?

Given a round table of $m$ seats, I want to seat $n$ people, where $0 \leq n \leq m$. And both the guests and the seats are not distinguishable.

I came up with the following solution, first, we try to arrange $n$ people together with $m-n$ seats in $(m-1)!$ ways because the table is a round table. Then because both the guests and the table are indistinguishable, we need to divide $(m-1)!$ by $n!(m-n)!$, which leads to my solution:$$\frac{(m-1)!}{n!(m-n)!}$$

But as I put numbers into $m$ and $n$, the number doesn't add up. For example, if I take $m=8$ and $n=2$, the above formula gives $\frac{7}{2}$, which is clearly not the case.

Can anyone tell me the correct solution for this problem?

• As far as I can tell, we're simply selecting n chairs from a total of m -- thus, the answer is m choose n.
– user261214
Feb 16 '17 at 14:21
• But the table is a round one, that complicates the matter. Feb 16 '17 at 14:22
• Ahh. If we can't distinguish rotations about the table, simply divide the answer by m.
– user261214
Feb 16 '17 at 14:23
• Hrm. That appears to yield your answer. I'll give this some thought.
– user261214
Feb 16 '17 at 14:23
• however, what if we had 4 chairs and 2 people - that seems to give $_{4}C_2 = 6$ arrangements - ok so far? But what are we going to divide 6 by to get the rotationally similar combinations which is 2 - we cannot divide 6 by 4
– Cato
Feb 16 '17 at 14:29

We can visualise the round table with $m$ seats and its symmetry as the cyclic group $C_m$. (we can not flip the table, thus no reflections are allowed)
Your seating problem can be restated as colouring the seats with 2 colours, one for when the seat has a person in it and one when it's empty. Take for example silver for seated and eggplant for empty. (I chose colours starting with s and e) This colouring problem can be solved with Polya's enumeration theorem. We need the cycle index of $C_m$ for Polya's theorem. Cycle index of $C_m$ is $$\frac{1}{m}\sum_{d \mid m} \varphi(d) x_d^{m/d}$$ where the sum is over all positive divisors $1 \leq d \leq m$ and $\varphi$ is the Euler totient function. For example the cylce index of $C_4$ is $\frac{1}{4}(x_1^4 + x_2^2 + 2 x_4)$.
Polya's method continues with replacing $x_d$ with $s^d + e^d$, so we get $$Z(s,e)=\frac{1}{m}\sum_{d \mid m} \varphi(d) (s^d + e^d)^{m/d}$$ Now the coefficient of $s^ne^{m-n}$ in $Z(s,e)$ is your amount of colourings with $n$ times colour $s$ and $m-n$ times colour $e$. Denote this coefficient as $S_m(n)$. So $S_m(n)$ is the amount of different seatings with $n$ guests on a table with $m$ seats. By a symmetry argument we get that $S_m(n)=S_m(m-n)$. The coefficient of $s^ne^{m-n}$ in $(s^d + e^d)^{m/d}$ is zero when $d \nmid n$ or $d \nmid (m-n)$. When $d \mid n$ and $d \mid (m-n)$, the coefficient is ${m/d \choose n/d}$, hence for an arbitrary $n$ we get that $$S_m(n) =\frac{1}{m}\sum_{\substack{d\mid m \\ d \mid n \\ d \mid (m-n)}} \varphi(d){m/d \choose n/d}$$
For $m=4$ we get that $Z(s,e)=\frac{1}{4}((s+e)^4 + (s^2+e^2)^2 + 2(s^4+e^4))$. If $n=0$, then $S_4(0)=\frac{1}{4}(1+1+2)=1$, $S_4(1)=\frac{1}{4}(4 + 0 + 0)=1$, $S_4(2)=\frac{1}{4}(6 + 2 + 0)=2$.
If you want to include flipping of the table, you have to do the same, but with the cycle index of $D_n$, the dihedral group of order $2n$.