In an Olympic contest, there are $n$ teams. Each team is composed of $k$ students attending different subjects. How many ways are there to seat all the students at a round table such that $k$ students in a team sit together and there are no two students who attend the same subject seat next to one another?

My attempt:

Let $S_n$ denote the total way to seat all the student in $n$ teams with $k$ students on each team in a way that satisfies the problem.

Then I find that $\forall n \geq 2$ $S_{n+1}=\alpha.nS_n$ with $\alpha = 2(k-1)!-(k-2)!$ But there is problem for me to find $S_2$ because it may be non-relative to $S_1$. Help me!

  • 1
    $\begingroup$ I've tried to fix this English as best as I can. $\endgroup$ – Alexander Gruber Mar 3 '13 at 5:10
  • $\begingroup$ One thing I don't understand: does every student on a team attend a different subject? $\endgroup$ – Alexander Gruber Mar 3 '13 at 5:10
  • $\begingroup$ may be change "every" to "each" , do you understand? $\endgroup$ – Haruboy15 Mar 3 '13 at 5:13
  • $\begingroup$ I think so: there are $k$ subjects, and each student has a different subject, is that right? For example, a team could have three people A, B,and C, A attends subject 1, B attends subject 2, C attends subject 3. $\endgroup$ – Alexander Gruber Mar 3 '13 at 5:15
  • $\begingroup$ ok that 's my meaning , thanks you so $\endgroup$ – Haruboy15 Mar 3 '13 at 5:20

I came across a problem like this in a contest years ago. They have the solutions so I will give you the link. Look at question 10:

http://www.cemc.uwaterloo.ca/contests/past_contests/2009/2009EuclidContest.pdf (question paper)

http://www.cemc.uwaterloo.ca/contests/past_contests/2009/2009EuclidSolution.pdf (solution)

A formula was not needed to by derived to answer the question but somewhere in the solution they give the explicit formula.

  • 1
    $\begingroup$ I looked at both your problem and the contest problem again carefully and they are not identical. But this may still help since the nature of the problems are similar. $\endgroup$ – Pratyush Sarkar Mar 3 '13 at 5:37
  • 1
    $\begingroup$ You can use the same idea used in the solution of the contest problem but instead of $0$ and $1$, you have to use more digits/symbol for the subjecs, ie. $k$ symbols. Hope this helps you go in the right direction. $\endgroup$ – Pratyush Sarkar Mar 3 '13 at 5:41
  • $\begingroup$ thanks you so much , I see your meaning $\endgroup$ – Haruboy15 Mar 3 '13 at 5:46

I think that your recurrence isn’t quite right. If you start with an acceptable arrangement of $n$ teams, you can insert an $(n+1)$-st team in any of the $n$ slots between adjacent teams. The members of the new team can be permuted in $k!$ ways; $(k-1)!$ of these have an unacceptable person at one end, $(k-1)!$ have an unacceptable person at the other end, and $(k-2)!$ have an unacceptable person at both ends, so


i.e., we should have $\alpha=k!-2(k-1)!+(k-2)!$.

I’m assuming now that arrangements that differ only by a rotation of the table are considered the same. Then $S_1=(k-1)!$. There are at least two ways to see that $S_2=k!\alpha$.

  1. Start with any of the $(k-1)!$ arrangements of one team. There are $k$ slots into which we can insert the second team, and the argument given above shows that within its slot it can be arranged in $\alpha$ ways, for a total of $(k-1)!k\alpha=k!\alpha$ arrangements.
  2. There are $k!$ ways to seat the first team around half of the table, and by the argument given above there are $\alpha$ acceptable ways to seat the second team around the other half of the table.

Combine this with the recurrence $S_n=(n-1)\alpha S_{n-1}$ for $n\ge 3$, and you can easily get a closed expression for $S_n$ in terms of $n$ and $k$.

  • $\begingroup$ I think you have a small mistake in "find $S_2$" In the first or in the second way of yours you forget that two student at the slot you insert the second team, they can exchange the seat to each other. So $S_2$ must be $ \frac{k!.\alpha}{2}$ If you don't believe me, you can draw the case 2 team and 3 student in each team, there 're only 9 way not 18 way as your result. Now my way that : chose 2 stundents of k ones we have $C_k^2$ way there is $\alpha$ way to insert the second team to the slot between these stundent now $k-2$ stundent rest can exchange their seat, so have (k-2)! $\endgroup$ – Haruboy15 Mar 4 '13 at 6:08
  • $\begingroup$ In total $S_2=\alpha.\frac{k!}{2}$ $\endgroup$ – Haruboy15 Mar 4 '13 at 6:08

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.