2
$\begingroup$

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?

$\endgroup$
3
  • $\begingroup$ 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? $\endgroup$ Dec 4 '17 at 4:47
  • $\begingroup$ 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!$. $\endgroup$ Dec 4 '17 at 4:47
  • $\begingroup$ @ParclyTaxel no, in the question NONE of the 3 can be adjacent to each other $\endgroup$
    – NeonCop
    Dec 4 '17 at 4:52
3
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.