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

Solution 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\;.$$

Solution 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.