2
$\begingroup$

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?

$\endgroup$
5
  • $\begingroup$ As far as I can tell, we're simply selecting n chairs from a total of m -- thus, the answer is m choose n. $\endgroup$
    – user261214
    Feb 16 '17 at 14:21
  • $\begingroup$ But the table is a round one, that complicates the matter. $\endgroup$ Feb 16 '17 at 14:22
  • $\begingroup$ Ahh. If we can't distinguish rotations about the table, simply divide the answer by m. $\endgroup$
    – user261214
    Feb 16 '17 at 14:23
  • $\begingroup$ Hrm. That appears to yield your answer. I'll give this some thought. $\endgroup$
    – user261214
    Feb 16 '17 at 14:23
  • $\begingroup$ 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 $\endgroup$
    – Cato
    Feb 16 '17 at 14:29
1
$\begingroup$

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$.

$\endgroup$
2
  • $\begingroup$ Thanks for the solution. Also do you know where my reasoning went wrong? $\endgroup$ Feb 17 '17 at 1:17
  • $\begingroup$ Your first step is already faulty, because you didn't differentiate between guests and empty seats. By the way, could you accept my answer if it helped you? $\endgroup$ Feb 17 '17 at 12:40

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.