📚 Advanced Study Notes – Seating Arrangements
(Reasoning Ability – ACT, MIT‑Level Treatment)
1. Introduction
A seating arrangement problem asks: How many ways can a set of people be seated under given constraints?
Typical constraints involve:
| Type | Example | Symbolic Notation |
|---|---|---|
| Adjacency | Person A must sit next to B | (A\leftrightarrow B) |
| Separation | C must not sit next to D | (C\not\leftrightarrow D) |
| Position | E must sit in an odd numbered seat | (E\in{1,3,5,\dots}) |
| Order | F must be left of G | (F < G) |
Why is this important?
- It is a micro‑study of permutation counting with constraints.
- It introduces tools that appear in combinatorial optimisation, graph theory, and probability.
We will build the theory from first principles, prove key results, discuss edge cases, and finish with a hard problem that ties everything together.
2. Basic Definitions & Notation
| Symbol | Meaning | Example |
|---|---|---|
| (n) | Number of people (or seats) | (n=8) |
| (\mathcal{S}_n) | Symmetric group on (n) elements (all permutations) | (\mathcal{S}_3={123,132,213,231,312,321}) |
| (\pi(i)) | Seat number of person (i) under permutation (\pi) | (\pi(A)=5) |
| (P(A\leftrightarrow B)) | Event that (A) and (B) are adjacent | |
| (C_n) | Number of circular seatings of (n) distinct people | (C_n=(n-1)!) |
Linear vs Circular seatings
- Linear – people sit in a row, seat indices (1,\dots,n).
- Circular – people sit around a table; seat indices are modulo (n).
Two seatings that differ only by rotation are considered identical.
3. Fundamental Counting Principles
3.1 Counting without constraints
- Linear: (n!) permutations.
- Circular: ((n-1)!) (divide by (n) to factor out rotations).
3.2 Inclusion–Exclusion Principle (IEP)
Given events (E_1,\dots, E_k), the number of permutations avoiding all (E_i) is
[ \left|\bigcap_{i=1}^k \overline{E_i}\right| = \sum_{J\subseteq{1,\dots,k}} (-1)^{|J|}\left|\bigcap_{j\in J}E_j\right|. ]
Proof Sketch: By expanding the product (\prod_{i}(1-\mathbf{1}_{E_i})) and summing over all permutations.
4. Linear Arrangements with Adjacency Constraints
4.1 “Must sit together”
Treat the pair as a single block.
- If pair ((A,B)) must sit together, the block can be in two orders: (AB) or (BA).
- Reduce the problem to (n-1) objects: ((n-1)!\times 2).
Generalisation: (k) people must form a single block: ((n-k+1)!\times k!).
4.2 “Must not sit together”
Use IEP:
- Total permutations: (n!).
- Count permutations where (A) and (B) are adjacent: treat as block → ((n-1)!\times 2).
- Subtract: (n! - 2(n-1)!).
For multiple forbidden pairs, compute intersections carefully.
4.3 “Distance constraints”
Let (d_{AB}) be the distance (number of people between).
If we require exactly (k) people between (A) and (B):
- Place (A) at any of the (n-k-1) seats that allow (k) spaces.
- (B) is forced to the seat (k+1) seats away (two possible directions).
- Remaining (n-2) people can be permuted arbitrarily: ((n-2)!).
Thus: ((n-k-1)\times 2\times (n-2)!).
5. Circular Arrangements
5.1 Simple “must sit together”
Same as linear but with ((n-1)!) base:
[ \text{Count} = \frac{(n-1)!}{n}\times 2 = (n-2)!\times 2. ]
Proof: Treat block as single object → ((n-1)) objects around a circle → ((n-2)!) arrangements. Multiply by 2 for internal order.
5.2 “Must not sit together”
Count all circular permutations: ((n-1)!).
Count forbidden ones: treat (A) and (B) as a