Seating strategy: how many ways can a group sit around a table?

A table seat choice can be the difference between a boring, wasted night and a fun, profitable one. I can recall two examples where seat choice made a big difference.

The first was a student-faculty dinner at Stanford where I had invited a math professor. The etiquette was to accompany a professor while getting food and walk to a table. The natural instinct, therefore, was to sit directly next to the invited professor. But this was a bad choice, as it was difficult to make eye contact and direct conversation. It also led to awkward moments where students spilled food and drinks on their professor. Lesson learned: always sit across the table!

The second came in a friendly poker game. After playing a few times, we quickly learned the importance of seating order, particularly when betting in no-limit Texas Hold’em. We have since paid careful attention to rotate seats for fairness.

The games of course led to a natural question: exactly how many ways can a group sit around a table? (essentially, how many different betting orders are there?)

There are a handful of ways to determine the answer. Here are a few that I like.

Method 1: Converting linear permutations into circular permutations

The case of two people is trivial: there is only one way.

How many ways can three people sit around a table? One way is to count permutations.

The easiest type of permutation to count is a “linear” list. Say the people around the table are sitting as person A, then person B, and finally person C. We can represent this order in a linear list as ABC.

Using this notation, we can count the number of possible lists. We simply note there are:

3 possible choices for the first spot (A, B, or C)
2 choices for the second
1 choice for the last spot

This means there are 3 x 2 x 1 = 6 = 3! ways to write the list. Specifically the list can be written as:

ABC
ACB
BAC
BCA
CAB
CBA

But this list is not our answer. At least some of these permutations represent the same seating order on a circular table. We can see this graphically:

The image above shows that the list orders ABC and CAB are the same arrangement on a circular table.

So we ask: what’s the relation between linear permutations and the circular ones we wish to count.

The relationship can be illustrated:

Evidently, each circular permutation for a three-person group can be written in 3 different ways. This makes sense: for each circular permutation, there are three different choices for the first letter of the linear permutation representation.

Thus, we can convert the number of circular permutations into linear ones by multiplying by 3. Or working in reverse, we can convert the number of linear permutations into circular ones by dividing by 3.

Combing all of this, we can deduce there are 3! / 3 = 2 ways to seat three people on a table. (The answers are ABC and ACB)

We can expand this logic to more people. We first count the number of linear permutations and then convert to circular ones.

For four people, the number of linear permutations can be counted. There will be 4 choices for the first spot, 3 choices for the second, 2 choices for the third, and 1 choice for the last. Therefore there will be 4 x 3 x 2 x 1 = 4! linear permutations.

We can then convert this into the number of circular permutations. As there are 4 people in the group, there will be 4 ways that each circular permutation can be written as a linear permutation–any of the four people can be written first in the list. So now to convert linear into circular we divide by 4 (again the number of people in the group).

Thus there will be a total of 4! / 4 = 6 ways to seat this group.

To generalize even further, we can see a pattern for n people. We can write the linear permutation in n! ways, but we have to divide by n to convert the linear permutations  into circular ones.

In the end, the formula simplifies as:

And viola, we have our answer.

Method 2: induction

An alternate way of solving this problem is mathematical induction.

Listing out a few cases of two, three, and four suggests the general formula (n – 1)! Now we can prove it.

Consider a group of n – 1 people who are about to get seating at a table in a restaurant. Let’s say at the very last minute one extra person comes. How many ways can the group be seated?

By the induction hypothesis, we know there are (n – 2)! ways for the initial group to sit. Where can the additional person sit? For any of these (n – 2)! arrangements, he can obviously sit between the first and second person, or between the second and third, or so on until the last position of being between the n - 1 person and the first person.

This is a total of n – 1 spots he can sit for any of those (n - 2)! arrangements. Therefore, this group of n people has this many arrangements:

And like mathemagic, induction proves the formula.

Method 3: seat-changing permutations

A final way I like to visualize the answer is a party-game type approach.

Consider for a moment that n people have sat at a circular table. How many ways can they switch seats and have at least one person sitting with different neighbors on left and right sides? This is another way of asking the number of circular permutations, so the answer to this question will answer our original question.

Some ways people switch will obviously not change the seating order. If everyone moves one seat to the right, then each person has the same neighbors and so the seating arrangement is the same.

Such rotations do not change the order of seating.

And this demonstrates a principle: motion is always relative to a reference point. To count the number of distinct seat trades, we must have a fixed reference point. Without loss of generality, we can choose any one person to be a reference point.

With one person firmly seated, every unique linear ordering of the remaining people change seats will be a unique circular permutation.

In other words, we want to know the number of linear permutations for n - 1 people. The answer is (n – 1)! and we’ve found the answer again.

Discussion questions

1. Imagine one of the seats at the table is broken and less desirable than the others. The other chairs are indistinguishable. How many distinct seating placements are there for a group of n?

2. Someone read this formula and gave a technical objection. He points out that certain circular permutations are almost the same. For instance, the distinct orders of 12345 and 15432 are “reflections” of each other: person 1 is sitting next to 2 and 5 in both cases but they are on different sides:

How many distinct orders are there if such “mirror” reflections don’t matter? (We care only about whom each person is sitting next to, and not whether the neighbor is on the left or the right side.)

3. Further reading: The order of the Garter which discusses seating at England’s oldest order of chivalry