Learn / Library / Combinatorics

Nobody sits adjacent

CombinatoricsHard

A row has $10$ chairs. $4$ distinct people sit in $4$ different chairs so that no $2$ of them occupy neighbouring chairs. How many seatings are possible?

Checking an answer needs JavaScript. The hint and the solution open without it.

Hint

First choose which chairs are used, by placing the empty chairs and inserting people into the gaps.

Solution

Line up the $6$ empty chairs, which create $7$ gaps where a person may sit, with at most one person per gap.
Choosing $4$ gaps gives $(4 7) = 35$ sets of chairs with no neighbours.
The $4$ distinct people can be assigned to the chosen chairs in $4! = 24$ ways.
Multiplying gives $35 \times 24$ .
Hence the number of seatings is $840$ .

Answer: $840$

Next question Back to the library