1

It has always been an interesting question.

If we have $10$ chairs and a round table, how many ways are there of seating $10$ people?

I would say there are $10!$ ways to seat the people due to there being $10$ choices for the first $9$ for the second?

But people often say the number of ways is: $(n-1)!$, but which one is correct and why?

wythagoras
  • 25,026
Amad27
  • 10,465

2 Answers2

3

There are $6! = 720$ ways of seating six people in six chairs, BUT, when people speak of a "circular table" in this context, what they often have in mind is that the following two arrangements are the same since everyone has the same person to its left and the same person to its right in both arrangements. $$ \begin{array}{cccccccccc} & & A \\ & \nearrow & & \searrow \\ F & & & & B \\[6pt] \uparrow & & & & \downarrow \\ E & & & & C \\ & \nwarrow & & \swarrow \\ & & D \end{array} $$ $$ \vphantom{frac\int\int} $$ $$ \begin{array}{cccccccccc} & & F \\ & \nearrow & & \searrow \\ E & & & & A \\[6pt] \uparrow & & & & \downarrow \\ D & & & & B \\ & \nwarrow & & \swarrow \\ & & C \end{array} $$ This is a cyclic shift. One speaks of "modding out by cyclic shifts", which means two things are considered identical if the only difference between them is a cyclic shift.

Michael Hardy
  • 1
  • Nice Answer, it makes sense when you talk about the cyclic shift here. Is this graph theory? Also then, I asked a question here: http://math.stackexchange.com/questions/1367778/how-many-ways-are-there-to-shake-hands. But there the number of arrangements was $(n-1)!/2$ so that is even more confusing? – Amad27 Aug 03 '15 at 19:18
  • If this were about each person shaking hands with two other people, then we would mod out not only by cyclic shifts, but also by reversals of clockwise and counterclockwise. That would require dividing by $2$. ${}\qquad{}$ – Michael Hardy Aug 03 '15 at 19:25
  • Two questions (1) In the above your two diagrams, are those counted as ONE arrangement?

    (2) what do you mean by a "reversal" Suppose we had a table of $4$ people shaking hands. $ABCD$ people arranged in one circle. Fixing one point $A$ (top) makes the cycle fixable so we have $3!/2 = 3$ arrangements. Now why would we divide by $2$? I used this example so it would be easier. Thanks

     – Amad27 Aug 03 '15 at 20:42
  • **(2) Here: http://www.artofproblemsolving.com/school/mathjams-transcripts?id=355 If you scroll to problem $9$, the first two cases are the exact same with cyclic shift, then why are the considered different? – Amad27 Aug 03 '15 at 20:49
  • @Amad27 : When I look at that page, I don't see problems identified by numbers. – Michael Hardy Aug 03 '15 at 22:35
  • @Amad27 : I wrote about a reversal OF CLOCKWISE AND COUNTERCLOCKWISE. That is what I meant by "reversal". We would divide by $2$ because a list of the all orders in which people can be seated at a table would count every handshaking sequence twice, because if you reverse clockwise and counterclockwise you get the same combination of handshakes. ${}\qquad{}$ – Michael Hardy Aug 03 '15 at 22:47
  • but in $(n-1)!$ dont you already take care of the extras? Or you mean a sequence: $ABC$ as $CBA$? Also in the page please CTRL-F: 9. "Ten chairs are arranged in a circle. Find the number of subsets of this set of chairs that contain at least three adjacent chairs." and then scroll down a little bit to the cases (where DPatrick points out) – Amad27 Aug 04 '15 at 18:04
  • Please advice me one more time! – Amad27 Aug 06 '15 at 13:27
  • @Amad : Suppose $ABCDEF$ is one of the orders included in the list of ways to seat people at a circular table, that's equivalent to $BCDEFA$, and to $CDEFAB$, etc., but not to $FEDCBA$. However, as a hand-shaking combination, it is equivalent to $FEDCBA$. Reversing the order gives the same hand-shaking combination. Therefore, in the list of ways to seat people in a circle, every hand-shaking combination appears TWICE (thus $ABCDEF$ is one item in the list and $FEDCBA$ is another). So you have to divide the number of cyclic arrangements by $2$ to get the number of hand-shaking combinations. – Michael Hardy Aug 06 '15 at 20:15
  • okay thanks a lot this makes good sense now. But one question about this cyclic shift idea. In http://www.artofproblemsolving.com/school/mathjams-transcripts?id=355 If you CTRL-F: Ten chairs are arranged in a circle. Find the number of subsets of this set of chairs that contain at least three adjacent chairs. Then you see that two of the cases are the same just with cyclic shift, then why is this counted as an individual case? – Amad27 Aug 07 '15 at 17:56
  • @Amad27 : Because in that case the chairs are treated as distinguishable. In the problem in which one mods out by cyclic shifts, the people are treated as distinguishable and the chairs as indistinguishable. – Michael Hardy Aug 07 '15 at 18:35
  • I am understanding slowly (sorry) but I really appreciate the help. I think I am starting to see it. But I am still confused. If the chairs are distinguishable then we have chairs $A, B, C$ for example. But two questions. (1) How do you know the chairs are distinguishable? (2) If the distinguishability is there do they mean: $AB$_ and then $BC_$ is the two different cases? But then again, how do you know the chairs are distinguishable? – Amad27 Aug 07 '15 at 20:06
  • It was the chairs rather than the people that were indistinguishable in the first problem; hence it was the people, not the chairs, that were labeled $ABCDEF$. The number of ways to seat $n$ people on $n$ distinguishable chairs in a circle is $n!$; it is when the chairs become indistinguishable that it becomes $(n-1)!$. When the question is "Find the number of subsets that$\ldots$" then the fact that the word "subset" is used implies distinguishability. ${}\qquad{}$ – Michael Hardy Aug 07 '15 at 21:10
  • Okay I think I am good for the most part. So the two cases which look like a shift. The chairs are $A, B, C$ for example. and "" is a space (empty). We have _$BA$ or $AC$? or $AB$ and then $BA$? Are those possible? – Amad27 Aug 08 '15 at 10:29
  • I notice the question on hand-shaking also goes into the cases in which more than one connected component exists, so the answer is more than $(n-1)!/2$. ${}\qquad{}$ – Michael Hardy Aug 08 '15 at 18:33
  • in the problem with the "subsets," even if the chairs are distinguishable what does that have to do with the cyclic shift? – Amad27 Aug 09 '15 at 08:39
2

Since it is a round table, and the seats are identical, it doesn't matter if everyone moves one seat to the right or the left. So we fix one person on one chair, and we have 9 chairs left to put 9 people on for $9!$ ways.

wythagoras
  • 25,026