Seating Arrangement – Advanced Reasoning Notes
(MIT‑style, first‑principles, rigorous, with edge‑cases and a research‑level challenge)
Goal – Master the combinatorial machinery that underpins seating‑arrangement questions: counting, constraints, symmetries, and algorithmic strategies.
1. Basics – From First Principles
1.1. Permutations as Functions
Let (S_n) be the symmetric group on ([n] = {1,2,\dots ,n}).
A linear seating of (n) distinct people is a bijection
[
\sigma : [n] \to [n], \qquad \sigma(i) = \text{person in seat } i.
]
The set of all such bijections has cardinality
[
|S_n| = n! .
]
If the seats are labelled but the people are identical, the number of arrangements collapses to (1).
1.2. Indistinguishable Objects
Suppose we have (m) people of type (A), (k) people of type (B), and the rest distinct.
The number of distinct seatings is the multinomial coefficient
[
\frac{n!}{m!,k!}.
]
This follows from the orbit–stabilizer theorem: the stabilizer of a labeling under the action of permuting identical objects has size (m!k!).
1.3. Circular Arrangements
A round table has no distinguished seat. Two seatings that differ by a cyclic rotation are considered identical.
The group of rotations is (C_n = \langle r \mid r^n = 1 \rangle).
By the orbit–stabilizer theorem,
[
\frac{|S_n|}{|C_n|} = \frac{n!}{n} = (n-1)! .
]
If the table also has a reflection symmetry (i.e., the arrangement is invariant under flipping), we further divide by (2) and obtain ((n-1)!/2) for (n>2).
2. Constraints – Modeling and Counting
2.1. Adjacency Constraints
| Type | Model | Counting Tool |
|---|---|---|
| Must sit together | Treat the group as a super‑person. | Reduce (n) by size of group, multiply by internal permutations. |
| Must not sit together | Use Inclusion–Exclusion (IE) over “forbidden adjacencies”. | IE or rook polynomials. |
| Exactly (k) seats apart | Fix relative positions; treat as “distance” constraint. | Combinatorial enumeration via stars‑and‑bars with gaps. |
Example – Two people must sit together in a line
Let (n) people, (A) and (B) must sit together.
- Glue (A) and (B) into a block (AB).
- Seat the block + remaining (n-2) people → ((n-1)!) ways.
- Inside the block, (A) and (B) can swap → multiply by (2!).
Total: (2!(n-1)!).
2.2. Distance Constraints
Let (d \ge 1) be the exact number of seats between two specified people (X) and (Y).
- In a line of (n) seats, there are (n-d-1) positions for the leftmost of the two.
- After fixing (X) and (Y), seat the other (n-2) people: ((n-2)!).
- Multiply: ((n-d-1)(n-2)!).
2.3. Grouping Constraints
Suppose you have groups (G_1,\dots ,G_r) with