Seating Arrangement – Advanced Reasoning Notes
(A rigorous, MIT‑level treatment for RRB Railway “Reasoning” problems)
Audience – University students (MIT‑level), competitive exam aspirants.
Goal – Understand the mathematics from first principles and apply it to “seating‑arrangement” problems that appear in Railway Recruitment Board (RRB) reasoning papers.
1. Introduction
Seating‑arrangement questions ask you to count the number of admissible permutations of a set of people (or objects) on a row (or a circle) of seats, subject to constraints. Typical constraints include:
- Adjacency – “A cannot sit next to B,” “C must sit immediately after D,” etc.
- Grouping – “Couples must sit together,” “All males must be in the left half,” etc.
- Relative positioning – “E must be seated at least two places away from F.”
These problems combine combinatorial enumeration with logical deduction. The key tools are:
- Permutations & Combinations – the basic building blocks.
- Inclusion–Exclusion Principle (IEP) – for “no‑adjacency” or “at least one of many forbidden pairs” constraints.
- Derangements – a special case of IEP where no element can be in a forbidden position.
- Block‑contraction – for grouping constraints (treat a group as a single “super‑person”).
- Recursion / DP – for problems with many overlapping sub‑problems.
We’ll build all of these from scratch, prove their correctness, discuss edge cases, and finish with a challenging practice problem.
2. Problem Statement (Typical RRB Example)
Example
A train compartment has 10 seats in a single row:
• 4 couples (A‑a, B‑b, C‑c, D‑d) must sit together.
• No two couples may sit next to each other (i.e., there must be at least one empty seat between any two couples).
Question – How many distinct seating arrangements are possible?
We’ll first solve this concrete problem, then generalize.
3. Mathematical Foundations
3.1 Permutations
- Definition – A permutation of a set (S) of size (n) is a bijection (\pi:S\to S).
- Number – (n!).
3.2 Inclusion–Exclusion Principle (IEP)
Let (U) be a universal set, (A_1,\dots,A_m) be subsets of (U).
The cardinality of the complement of (\bigcup_{i=1}^m A_i) is
[ |U|-\sum_{i}|A_i|+\sum_{i<j}|A_i\cap A_j|-\cdots+(-1)^m|A_1\cap\cdots\cap A_m|. ]
Proof Sketch – By alternatingly adding and subtracting the sizes of intersections, we correct for over‑counting multiple times.
3.3 Derangements
A derangement of (n) objects is a permutation with no fixed points.
Formula (via IEP):
[ !n = n!\sum_{k=0}^{n} \frac{(-1)^k}{k!} \quad\text{(rounded to nearest integer)}. ]
3.4 Block Contraction
If a set of objects must stay together (like a couple), treat the set as a single “block.”
The internal arrangement of the block contributes a factor of (k!) if the block has (k) objects.
4. General Strategy for Seating Problems
| Step | Action | Rationale |
|---|---|---|
| 1 | Identify constraints – adjacency, grouping, relative positions. | Determines the structure of the forbidden set. |
| 2 | Reduce the problem size – contract groups into blocks if needed. | Simplifies counting. |
| 3 | Count unrestricted permutations of the reduced set. | Gives baseline. |
| 4 | Apply IEP to subtract arrangements violating each constraint. | Handles “no‑adjacency” or “invalid pair” constraints. |
| 5 | Deal with special cases – e.g., circular seating, empties, identical objects. | Adjust |