# 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

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.

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.
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 1, "mathjax_display_tex": 1, "mathjax_asciimath": 1, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 0, "wp-katex-eq": 0, "align": 0, "equation": 0, "x-ck12": 0, "texerror": 0, "math_score": 0.6809919476509094, "perplexity": 543.1065334740475}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "plain"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "warc_path": "s3://commoncrawl/crawl-data/CC-MAIN-2021-43/segments/1634323585177.11/warc/CC-MAIN-20211017113503-20211017143503-00628.warc.gz"}