Learn / Library / Combinatorics

Round table, forbidden neighbours

CombinatoricsMedium

$8$ distinct people sit at a round table with identical chairs, and rotations of a seating are considered the same. $2$ specific people must not sit in adjacent chairs. How many distinct seatings are there?

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

Hint

Count all circular seatings, then remove those where the pair is adjacent.

Solution

The number of circular seatings of $8$ people is $7! = 5040$ .
For the bad seatings, glue the $2$ specific people into one block, which gives $7$ units around the table.
These units can be arranged in $6! = 720$ circular ways, and the pair can swap in $2$ ways, so there are $1440$ bad seatings.
Subtracting gives $5040 - 1440$ .
Hence the number of valid seatings is $3600$ .

Answer: $3600$

Next question Back to the library