Lakshadweep Patwari / Lekhpal /Reasoning Ability

Seating arrangement

Non-Verbal & Puzzles · free study notes

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 of n distinct 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:

  1. Adjacency: “A must sit next to B.”
  2. Separation: “A must not sit next to B.”
  3. Relative order: “A must sit left of B.”
  4. Position: “C must be in seat 3.”
  5. 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 S of 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

  1. Adjacency
    • Treat the adjacent pair as a block → (n-1)!·2.
  2. Opposite seats (n even)
    • Fix one person, then the opposite seat is determined → (n-2)!.
  3. Relative order (left/right)
    • Fix a direction (clockwise).
    • “A left of B” means A appears before B in the clockwise list → half of all arrangements → ½·(n-1)!.

Your note

Page 1

Doubt hai is topic me?

Free AI teacher se poocho — 24/7, step by step.