$20$ people are sitting around a (circular) table. How many ways can we choose $3$ people, no two of whom are neighbors?

Question

0 choices for the 1st person. 17 choices for the 2nd person (must exclude 1st and his/her two neighbours)

For 2 of these choices of 2nd person, there is one shared neighbour, so 15 remaining choices. (e.g. if they are numbered 1 to 20 in a circle, 1st person is #1, 2nd is #3, then people 20,1,2,3,4 are excluded). For the other 15 choices of 2nd person, there are no shared neighbors, so 14 remaining choices.

So if order matters, total is $20 \cdot (2 \cdot 15 + 15 \cdot 14) $ but since order does not matter, divide by $3! = 6$ to account for the permutations in order of the 3 people. So total = $20 \cdot \frac{2 \cdot 15 + 15 \cdot 14}{6}$

just redid it; does this make any sense?

Answer 1

There are $20$ ways to choose a block of $3$ consecutive people. There are also $20$ ways to choose a pair of adjacent people, and for each of those pairs there are $16$ ways to choose a third person who is not adjacent to either of them. Those are the only sets of $3$ people that we don’t want. There are altogether $\binom{20}3$ possible sets of $3$ people, so the number of acceptable sets is

$$\binom{20}3-20-20\cdot16=\frac{20\cdot19\cdot18}6-20\cdot17=20(57-17)=800\;.$$

Added: More generally, suppose that we have $n$ people at the table, and we want to choose $k$ of them, no two of whom are adjacent. First solve the problem when the $n$ people are in a line. Once the $k$ people are chosen, there will be $k+1$ gaps in which the others can be seated: one before the first chosen person, $k-1$ between adjacent chosen people, and one after the last chosen person. We have to fill these gaps with the $n-k$ people whom we didn’t choose. We must be sure to put at least one person in each of the $k-1$ gaps between adjacent chosen people, so we have only $n-k-(k-1)=n-2k+1$ people left to distribute freely amongst the $k+1$ gaps. This can be done in

$$\binom{(n-2k+1)+(k+1)-1}{(k+1)-1}=\binom{n-k+1}k$$

ways, by a standard stars and bars calculation.

However, this count includes the arrangements that in which the two people at the ends of the line are chosen, and when we wrap the line back around the table, those two people are adjacent. Thus, we don’t want to count those arrangements. There is one of them for each way of choosing $k-2$ people from a line of $n-2$ people with the requirement that no two be adjacent and that neither end person be chosen. This time we’re distributing $n-k$ unchosen people amongst $k-1$ slots with a requirement that each slot get at least one person, and another stars and bars calculation gives the number of such distributions as

$$\binom{n-k-1}{k-2}\;.$$

The final answer is therefore

$$\binom{n-k+1}k-\binom{n-k-1}{k-2}\;,$$

which in this specific problem is

$$\binom{18}3-\binom{16}1=816-16=800\;.$$

Answer 2

Assuming the seating assignments are fixed, the problem is tantamount to arranging $17$ blue chairs and $3$ green chairs in a circle so that no two of the green chairs are adjacent. We will solve the problem for a line, then adjust our answer to account for the fact that the chairs are arranged in a circle.

Line up $17$ blue chairs. This creates $18$ spaces, $16$ between successive blue chairs and two at the ends of the row. Choose three of the spaces in which to place a green chair. This can be done in $\binom{18}{3}$ ways.

However, we have counted selections in which both the first and last chairs are green. If both ends are selected, there are $16$ remaining spaces in which to place the third green chair. Hence, there are $16$ linear arrangements in which no two of the green chairs are adjacent in which there is a green chair at both ends of the row. Since we will be joining the ends of the row to form a circle, these arrangements must be excluded.

Therefore, the number of ways of circular arrangements of $17$ blue chairs and $3$ green chairs so that no two of the green chairs are adjacent is $$\binom{18}{3} - \binom{16}{1} = 800$$ as you found.

Answer 3

Why not again Stars and Bars theorem 1 with the extension of 2 gaps on the bounds. Theorem 1 because we don't want consecutive bars. Then $n=17, k_{max}=3$.

We don't take two on the bounds because we wrap around a circular table !

• |xxxxxx|xxxxxx|x : $\binom{17-1}{2}$ , two inside, one at the beginning
• x|xxxxx|xxxxxxx| : $\binom{17-1}{2}$ , two inside, one at the end
• x|xxxxx|xxxxxx|x : $\binom{17-1}{3}$ , three inside, none on the bounds

$$\binom{17-1}{2}+\binom{17-1}{2}+\binom{17-1}{3} = 800$$

Helped by @N. F. Taussig, I corrected my first answer which was false

Answer 4

Here is another way:
Form three blocks with a non-chosen $(N)$ clockwise of a chosen $(C),\;e.g. \boxed {CN}$

We now have $17$ entities, viz. $3$ blocks and $14$ others

We can place the blocks in $\binom{17}3$ ways, fulfilling the "non-neighbour" criterion,

but since in the process we are giving each entity only $17$ starting places instead of $20$,

ans = $\binom{17}3\cdot\frac{20}{17} = 800$