In how many ways can $4$ of $100$ people sitting at a circular table be selected so that no two of them are adjacent?

Question

At a circular table for $100$ persons, $4$ people will shake hands with each other. How many ways are there to choose $4$ people in that group so that there are no person who shakes hands sits beside another person who shakes hands too?

I have tried something like this problem but simpler. I solve it by enumerating it manually. If I change the total number of people to $8$ and choose $3$ people that shake hands with each other, I found that the answer is $16$.

ABCDEFGH
x-x-x---
x-x--x--
x-x---x-
x--x-x--
x--x--x-
x---x-x-
-x-x-x--
-x-x--x-
-x--x-x-
--x-x-x-
-x-x---x
-x--x--x
-x---x-x
--x-x--x
--x--x-x
---x-x-x

x is the shaking hand group

Can somebody help me solving this problem. Thank you :)

Answer 1

A circle can be formed by joining the ends of a row together. We solve the problem for a row, then remove those solutions in which two of the selected people are at the ends of the row.

We will arrange $96$ blue balls and $4$ green balls in a row so that the green balls are separated. Line up $96$ blue balls in a row, leaving spaces in between them and at the ends of the row in which to insert a green ball. There are $95$ spaces between successive blue balls and two at the ends of the row for a total of $97$ spaces. To separate the green balls, we choose four of these spaces in which to insert a green ball, which we can do in $$\binom{97}{4}$$ ways. Now number the balls from left to right, the numbers on the green balls represent the positions of the selected people.

However, those selections in which there are green balls at both ends of the row are inadmissible since that means the people in those positions will be in adjacent seats when the ends of the row are joined. If two green balls are placed at the ends of the row, the other two green balls must be placed in two of the $95$ spaces between successive blue balls. Hence, there are $$\binom{95}{2}$$ placements of green balls in which both ends of the row are filled by green balls. As these placements are inadmissible, the number of ways four of the $100$ people at the circular table may be selected so that no two are adjacent is $$\binom{97}{4} - \binom{95}{2}$$

Answer 2

Let the $n$ people around the table be labeled $1, 2, \ldots n $ and let $k$ be the # of those people to be selected.
We will count using two cases. Case A: $1$ is selected. Case B: $1$ is not selected.

Case A: $ \binom{n-k-1}{k-1}$
Case B: $ \binom{n-k}{k}$
Their sum is $\frac{n}{k}\binom{n-k-1}{k-1}$

You can check that the formula works for your example (for which the answer is 16).

I will prove Case A, leaving Case B for you.

EDIT: This proof has been revised using the methods of the clean proof by @ChristianBlatter

Assume $1$ is selected. Consider a sequence of $n-k\; 0$s. There are $n-k-1$ spaces between the $0$s. Select $k-1$ of these spaces. This can be done $ \binom{n-k-1}{k-1}$ ways. Place a $1$ into each of the selected places. This gives a unique sequence of length $n-1$ consisting $n-k \; 0\text{s and } k-1\; 1$s starting and ending with $0$ and with a $0$ between each of the $1$s.

Now label the elements of the string $2, 3, 4, \ldots , n$. The selected hand shakers are $1$ and the $k-1$ people in the string that had been selected.

Answer 3

Assume there are $N$ admissible quadruples. These involve $4N$ choices of an individual, and by symmetry each person is chosen the same number of times, hence ${N\over25}$ times. We now count the number of admissible quadruples having person $100=0$ as a member. The admissible choices of the remaining three persons can be encoded as a binary word of length $99$ obtained in the following way: Write $96$ zeros, and insert a one into $3$ of the $95$ gaps between the zeros.

It follows that the total number of admissible quadruples is given by $$N=25\cdot{95\choose3}=3\,460\,375\ .$$