Handling Excess People with Indistinguishable Chairs in Circular Arrangements

Question

I'm grappling with a problem involving seating arrangements in a room that features two circles of chairs. One circle consists of 11 chairs, and the other has 7, making a total of 18 chairs. The twist is considering scenarios with 20 people, focusing on the case where the chairs are indistinguishable. The challenge I face is understanding how to approach the situation where there are more people than available chairs, especially under the constraint of indistinguishable chairs.

Here's the original problem statement:

---

A total of 18 chairs are arranged in a room, forming two circles. One of the circles contains 11 chairs. Calculate the different ways twenty people can be seated in each of the following cases:

1. Assuming the chairs are distinguishable.
2. Assuming the chairs are indistinguishable.

---

For the first part, with distinguishable chairs, the calculation was straightforward. For the circle of 11 chairs, selecting 11 out of 20 people and arranging them yields $\binom{20}{11} \times 10!$ ways. For the circle of 7 chairs, choosing 7 out of the remaining 9 people and arranging them yields $\binom{9}{7} \times 6!$ ways. Multiplying these together gives the total number of arrangements.

However, I'm puzzled about how to approach the second part, where the chairs are indistinguishable, and there are more people than the chairs available. The usual method of considering all arrangements as a single possibility doesn't seem to fit well with the excess of people.

I'm seeking insights or methodologies to approach this scenario effectively. How should one consider the arrangements when the chairs are indistinguishable and not everyone can be seated?

Answer 1

For round seating of $n$ people in $n$ chairs, the formula is $n!$ if the chairs are distinguishable (=numbered), and $\frac{n!}{n} =(n-1)!$ if indistinguishable (=unnumbered) because rotations don't change relative positions of the people.

Firstly form $3$ groups of $\binom{20}{11},\binom97, \binom22$ people

These groups get automatically labelled by size, call them group$A,B,C$

Now if the chairs are numbered, the people can be seated in $[1]:\binom{20}{11}11! \times\binom977!$ ways

and if unnumbered, in $[2]: \binom{20}{11}10! \times\binom976!$ ways

Answer 2

Short answer : When the chairs are indistinguishable, use the formula $(n-1)!$ for the number of circular permutations. When they are distinguishable, use $n!$.

So, as stated in the comments, you have solved the second part (not the first). Replace $10!$ and $6!$ with $11!$ and $7!$ respectively to get the answer to the first part.

---

Explanation

In linear permutations, there is a fixed start/end point. So, for example, if there are people to be seated, the chairs are distinguishable just by virtue of where they are kept in the line (i.e. their positions with respect to the start/end point). Even if they are indistinguishable otherwise.

This is not the case with circular permutations because there are no extremities. Any position can be taken as the start/end point. So when the chairs are indistinguishable, rotations don't result in different permutations. The positions of the people with respect to one another do not change and that is all the matters.

That means each unique circular arrangement gives $n$ unique linear arrangements (by rotation, we can have $n$ different starting points). Which is why the formula for circular arrangements when rotations don't matter is $\dfrac{n!}{n} = (n-1)!$.

On the other hand, when the chairs are distinguishable, you can't rotate without creating a new permutation. That's because even if the relative positions of people don't change, each person's chair gets changed. Such circular permutations behave just like linear permutations and so the formula is the same for both, $n!$.