People sitting around circular dinner tables

Question

Find the number of ways of seating n people A1 , A2 , ..., An in arbitrary number of circular tables of arbitrary sizes.

Yes, Circular permutations do not matter. For example, Around a circle A,B,C are three people who sit as ABC, BCA, CAB clockwise are considered equivalent and counted as just one configuration.

And tables are indistinguishable. So, only the configuration of people around the tables matters.

Here is how I counted for n = 4:

4 can be written as,

4 = (4-1)! ways = 6 (4 people around 1 table)

3+1 = (3-1)!*(1-1)! ways = 2 (4 people around 2 tables etc)

2+2 = (2-1)!*(2-1)! ways = 1

2+1+1 = (2-1)!(1-1)!(1-1)! ways = 1

1+1+1+1 = (1-1)!(1-1)!(1-1)!*(1-1)! ways = 1

so total I could count only 11 ways.(Maybe this is flawed in some way? because others think the number of configurations is n! )

Answer 1

Let $F(n)$ be the number of ways of seating $n$ people. We could start by carefully listing the ways, for a few small values of $n$. The listing should be almost explicit. We find that $F(1)=1$, $F(2)=2$, $F(3)=6$, and (perhaps) that $F(4)=24$. Despite the small amount of evidence, the conjecture $F(n)=n!$ is tempting.

We prove the conjecture, in principle by induction. Suppose that we know that for a specific $k$, $F(k)=k!$. Now George, the $(k+1)$-th person, comes along, late as usual. For every possible seating of the $k$ people, we can place George at the table of one of the $k$ people, and immediately to the right of that person ($k$ choices), or we can place George at a table by himself. Thus $$F(k+1)=kF(k)+F(k)=(k+1)F(k)=(k+1)!.$$ Since $F(1)=1$, we conclude that $F(n)=n!$ for all $n$.

Another way: We can use fancier language. For example, note that every permutation of the set $\{1,2,\dots,n\}$ can be expressed uniquely as a product of disjoint cycles. We explicitly include any $1$-cycles. The order in which the product is taken does not matter, since the cycles are disjoint.

Every product of disjoint cycles corresponds to a unique circular seating, and vice-versa. (The people in a cycle determine a table, and their cyclic order determines the order of seating at that table.) This gives an explicit bijection between the permutations of $\{1,2,\dots,n\}$ and the seatings. Thus the number of seatings is equal to $n!$, the number of permutations.

Answer 2

I’m going to expand on André’s second way; it can be done without getting as technical as cycle decompositions. At each table there is one person with the lowest number; call that person the leader of that table. When listing the people at one table, we’ll start with the leader and list the rest in order counterclockwise around the table. With eight people and three tables, for instance, we might have 3648 around one table, 5 alone at another, and 172 at the third. Now arrange the table lists in descending order of their table leaders; in my example 5 comes first, followed by 3648 and then 172. Finally, concatenate these lists to make one big list of all of the people in the room: 53648172.

Clearly this procedure always produces a well-defined permutation of the integers $1$ through $n$ (assuming that there are $n$ people in the room). We know that there are $n!$ such permutations. Thus, if we can show that the procedure is reversible $-$ that from every possible permutation of $1$ through $n$ we can reconstruct the seating arrangement $-$ we’ll have shown that there are $n!$ possible seating arrangements.

Rather than give a detailed argument, I’ll use an example to illustrate how to reconstruct the seating arrangement from a permutation. Suppose that $n=9$ and I start with the more less randomly chosen permutation $694872531$. Clearly $6$ must be a table leader, and in fact the largest-numbered table leader. Scan the permutation from left to right, starting with the $6$: as long as you encounter only numbers larger than $6$, they must be sitting at $6$’s table, but the first number smaller than $6$ has to be another table leader. In this example that means that the list for the first table must be $69$, and $4$ must be the leader of the second table. Continue in the same way: $8$ and $7$ are larger than $4$, so they must be sitting at $4$’s table, but $2<4$, so $2$ must be the next table leader. We now have lists for the first two tables, $69$ and $487$, and we know that $2$ is the leader of the third table. After a little more work in the same vein we have the complete set of table lists: $69$, $487$, $253$, and $1$. These lists completely specify who is sitting at each table and the order in which they are seated around that table.

Of course you should finish by convincing yourself that the original listing procedure and the reconstruction procedure really are inverses, but that’s pretty clear once you understand both procedures.