# Seating people at a table, but some don't like each other

Here's a problem I've been struggling with:

8 people are seated at a circular table.
a) two people of the 8 do not get along well. How many ways can you arrange to seat the 8 people so the two troublesome ones are not seated next to each other?
b) three people of the 8 do not get along well. How many ways can you arrange to seat the 8 people so the three troublesome ones are not seated next to each other?

So, the base version of the question where you seat the original 8 is pretty simple, right? It's just 8!.

For a), I imagine you place one of the disliking people (8 options), which disqualifies 2 additional spots where the second disliker can't sit, leaving him with 5 options. For the rest of them, there's 6 spots for 6 people, so 6!, for a total of 8*5*6! = 28,800

For b) I imagined 2 distinct scenarios: Similarly to above, the first disliker has 8 options, and the second has 5 options. For the third disliker, however, it depends on the configuration of the other 2. If they are arranged with only one seat separating them, then the third disliker only has 3 options (8 minus 2 taken by other dislikers minus 3 unavailable because they're adjacent). However, if they have 2 or more seats separating them, then the third disliker only has 2 options (8 minus 2 taken by other dislikers minus 4 unavailable because they're adjacent). And then the other 5 have 5! options. So, would this look like (8*5*3*5!) + (8*5*2*5!) = 24,000? Is that the right answer? Or am I missing something?

• For (b), are arrangements where two of the troublesome ones sit next to each other but the third is not adjacent to that pair allowed? Dec 4 '17 at 4:47
• You are missing something at the very starting. The people are sitting on a circular table, so the base version's answer is not $8!$. Dec 4 '17 at 4:47
• @ParclyTaxel no, in the question NONE of the 3 can be adjacent to each other Dec 4 '17 at 4:52

A slightly different approach: I am going to assume the troublesome people in the first case are $A,B$ and in the second case $A,B,C$.

a) We make $A$ sit for first. Then we accomodate $B$: he/she may take place in five different ways. The remaining $6$ people can fill the free places in any way they like, so the answer is given by $5\cdot 6!=3600$.

b) We make $A$ sit for first. Then we accomodate $B$ and $C$: they have to take two non-adjacent places among five. In two configurations there are three empty places between $B$ and $C$; in four configurations there are two empty places between $B$ and $C$, in six configurations there is just one free place between $B$ and $C$. The remaining five people can sit in any way they like. Thus the answer is given by $(2+4+6)\cdot 5! = 1440$. Not by chance, $$2+4+6 = \left|\{(a,b,c)\in\mathbb{N}^+\times\mathbb{N}^+\times\mathbb{N}^+: a+b+c=5\}\right|.$$

c) By generalizing the approach above, if we have $n$ people to arrange around a circular table and $k\leq\frac{n}{2}$ of them do not like each other, we may accomodate them in

$$(k-1)!(n-k)!\cdot [x^{n-k}]\left(\frac{x}{1-x}\right)^k = (k-1)!(n-k)!\binom{n-k-1}{k-1}=\frac{(n-k-1)!(n-k)!}{(n-2k)!}$$ ways by stars and bars.

Without restrictions, there are $8!/8=7!$ arrangements because of the circular table. Alternatively, fixing one person not in the troublesome group at some seat, $7!$ results immediately. Now the question reduces to seating seven in a line that cannot be flipped.

With two roughs (troublesome people), the number of arrangements where they would be next to each other is $6\cdot2\cdot5!$: 6 ways to place the group of two, two ways to permute that group and $5!$ ways to permute the remaining five. Subtracting this from $7!$ yields the number of admissible arrangements: $5040-1440=3600$.

With three roughs, there are ten configurations in which those pesky people can sit:

o.o.o..  o.o..o.
o.o...o  o..o.o.
o..o..o  o...o.o
.o.o.o.  .o.o..o
.o..o.o  ..o.o.o


For each configuration there are $3!$ ways to permute the roughs and $4!$ ways to permute the rest, giving $10\cdot3!\cdot4!=1440$ admissible ways.