Seating‑Arrangement Reasoning – Advanced University Notes
MIT‑Level Treatment – From First Principles to Edge Cases
1. Introduction
Seating‑arrangement problems are a staple of reasoning‑ability sections in competitive exams.
They test combinatorial thinking, logical deduction, and the ability to translate verbal constraints into mathematical models.
Goal of these notes
- Build a rigorous, systematic framework for tackling any seating‑arrangement problem.
- Introduce advanced combinatorial tools (inclusion–exclusion, rook polynomials, generating functions, graph–theoretic methods).
- Highlight subtle edge cases that often trip candidates.
- End with a challenging problem that requires the full arsenal.
Notation
n– total number of people.k– number of distinct “seat types” (e.g., left/right, even/odd).C(n, k)– binomial coefficient.p(n)– number of permutations ofndistinct objects (n!).S(n, k)– Stirling numbers of the second kind (partitions).
2. Foundations – From First Principles
2.1 Counting Basics
| Situation | Formula |
|---|---|
| Linear arrangement (distinct people, distinct seats) | n! |
| Circular arrangement (rotations considered identical) | (n-1)! |
| Circular arrangement with a fixed reference seat | n! |
| Linear arrangement with indistinguishable people | n! / (n₁! n₂! …) |
| Circular arrangement with indistinguishable people | 1 / (n₁! n₂! …) Σ (n! / prod) * (-1)^k … (see inclusion–exclusion below) |
2.2 Permutations with Restrictions
Constraints are usually of the form:
- Adjacency: “A must sit next to B.”
- Separation: “A must not sit next to B.”
- Relative order: “A must sit left of B.”
- Position: “C must be in seat 3.”
- Parity: “All females sit on odd seats.”
We model these constraints as graph relations or set constraints.
3. Linear Arrangements – A Systematic Approach
3.1 Basic Cases
| Constraint | Strategy | Result |
|---|---|---|
| Fixed seat (e.g., D in seat 5) | Remove that seat → (n-1)! arrangements for the rest. |
(n-1)! |
| Adjacent pair (A next to B) | Treat A–B as a block → (n-1)! * 2 (two internal orders). |
2·(n-1)! |
| Non‑adjacent pair (A not next to B) | Total n! minus adjacent cases. |
n! – 2·(n-1)! |
3.2 Inclusion–Exclusion for Multiple Constraints
When we have several “forbidden adjacencies” or “must‑be adjacencies”, inclusion–exclusion (IE) is the go‑to tool.
Theorem (IE for forbidden adjacencies).
Let E_i be the event that persons i and i+1 sit adjacent.
The number of linear arrangements with none of the E_i occurring is
[ N = \sum_{j=0}^{n-1} (-1)^j \sum_{\substack{S \subseteq {1,\dots,n-1}\ |S|=j}} (n-j)! \cdot 2^j ]
Proof Sketch.
- For a fixed subset
Sof adjacencies to be enforced, contract each adjacency into a block. - There are
n - |S|blocks →(n-|S|)!permutations. - Each contracted block has 2 internal orders.
- Sum over all subsets with alternating signs. ∎
Example – “No two of the four men sit together” (four men, k=4, n=total).
Apply IE to the 4 adjacency events among men.
3.3 Rook Polynomials for “No two in the Same Row/Column”
When seats are arranged in a matrix (e.g., 3 rows × 5 seats) and the rule is “no two in the same row or column,” we can use rook polynomials.
Let R(x) be the rook polynomial of the board.
Then the number of ways to place n non‑attacking rooks (people) is the coefficient of x^n in R(x).
This is a powerful tool for problems that can be visualized as placing rooks on a chessboard.
4. Circular Arrangements – Handling Rotational Symmetry
4.1 Basic Circular Counting
- Fixed reference seat: treat as a linear arrangement →
n!. - Rotations equivalent: divide by
n→(n-1)!.
4.2 Constraints in Circular Context
- Adjacency
- Treat the adjacent pair as a block →
(n-1)!·2.
- Treat the adjacent pair as a block →
- Opposite seats (n even)
- Fix one person, then the opposite seat is determined →
(n-2)!.
- Fix one person, then the opposite seat is determined →
- Relative order (left/right)
- Fix a direction (clockwise).
- “A left of B” means
Aappears beforeBin the clockwise list → half of all arrangements →½·(n-1)!.