ACT /Reasoning Ability

Seating arrangement

Non-Verbal & Puzzles · free study notes

📚 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:

  1. Total permutations: (n!).
  2. Count permutations where (A) and (B) are adjacent: treat as block → ((n-1)!\times 2).
  3. 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

Your note

Page 1

Doubt hai is topic me?

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