Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Suppose two seating arrangements are considered equivalent if one can be obtained from the other by rotation. How many equivalence classes are there?

I'm having trouble understanding the problem conceptually, can someone explain it in an intuitive and succinct manner?

share|improve this question

2 Answers 2

up vote 1 down vote accepted

Suppose that you seat the $8$ people around the table in some order. Now each of them moves one place clockwise. No one is in the same seat as before, but they’re still in the same order: the arrangement has simply been rotated one place clockwise. If they repeat the manoeuvre, each of them will be in yet another seat, but they will still be in the same order. In fact, they won’t return to their original seats until they’ve repeated the manoeuvre $8$ times. There are therefore $8$ different seatings (including the original one) that preserve the original order and that are obtained from the original order by having the people move some number of seats clockwise. These $8$ seatings are equivalent under rotation: any one of them can be obtained from any of the others by having each person move a certain number of seats clockwise. One such set of $8$ seatings is an equivalence class of this notion of equivalence under rotation.

It may make things a little clearer to note that if two seatings are equivalent under rotation, each of the $8$ people has the same left and right neighbors in both seatings: everyone has simply moved around the table as a group.

There are $8!$ ways to arrange $8$ people in a line. If the seats at the table are numbered from $1$ through $8$, we can think of the seat numbers as positions in a line, and there are therefore $8!$ ways to seat the $8$ people around the table. But if we’re interested only in the order of the people around the table, rather than in their exact seat numbers, there are (as we just saw) $8$ different seatings that give the same circular order of the people. Thus, when we count these equivalence classes of rotationally equivalent seatings, we have to divide the total number of possible seatings by $8$. And the result is ... ?

share|improve this answer
    
Isn't this the same as solving for the number of solutions without repetition and the seats unordered, for which we have ${n\choose k}$? –  user1903336 Dec 18 '12 at 9:13
    
@user1903336: No, it’s not at all the same. The ordering is crucial, and there are no repetitions. It’s simply a matter of lumping the $8!$ permutations into groups of $8$ and then counting the groups. –  Brian M. Scott Dec 18 '12 at 9:15

Pick one of eight people to fill a seat. Now pick one of the remaining $7$ people to fill the next seat clockwise, and so on. That makes $8\cdot7\cdot\ldots\cdot2\cdot1=8!$ different arrangements in all. But there are $8$ arrangements in each equivalence class, which you can get by rotating an arrangement by $0$ to $7$ seats. (If you rotate it by $8$ seats it's the same again.)

Since there are $8!$ different arrangements and $8$ of them form an equivalence class, there are $8!/8=7!=5040$ equivalence classes.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.