40 people are around a table,how many ways we can choose 5 person in case that between every 2 chosen person should be at least 3 people

Question

$40$ people are sitting around a table. In how many ways we can choose $5$ person of them so that between every $2$ persons that are chosen will be at least $3$ other people sited.

I think it is related to circular combination and permutation with repetition, but I do not know how?

I tried solving this question, but I could not. Please help me do that.

Answer 1

Fix a position at the table and assign it to be position $0$ and assign for example clockwise consecutively all postions from $0$ through $39$.

Any of your selections corresponds to a selection of increasing positions $p_1,\ldots , p_5$:

Now, consider the displacements between neighbouring positions:

$$d_k = p_{k}-p_{k-1} \text{ for } k=2,3,4,5 \text{ and set } d_1=p_1$$

Besides this the 5th position has a displacement of $d_6 = 39-p_5$ to the last position.

So, each selection corresponds to an integer solution of the equation

$$d_1 + d_2 + d_3 + d_4 + d_5 + d_6 = 39 \text{ where: }$$

• $ d_1,d_6 \geq 0 \text{ and } d_k \geq 4$ for $k=2,3,4,5$
• Since also between positions $p_1$ and $p_5$ should be at least $3$ people, a further restriction is $d_6 + d_1 \geq 4$.

So, introducing $d_k' = d_k - 4$ for $k=2,3,4,5$ we need the number of non-negative integer solutions of

$$d_1 + d_2' + d_3' + d_4' + d_5' + d_6 = 23 \text{ while } d_1+d_6 \geq 4$$

Since the number of non-negative integer solutions without any restrictions is $\binom{23+5}{5}$, we only need to subtract the solutions satisfying $0\leq d_1+d_6 = l$ for $l=0,1,2,3$:

$$d_2' + d_3' + d_4' + d_5' = 23-l$$

Noting that the number of non-negative integer solutions of $d_1+d_6 = l$ is $\binom{l+1}{1}=l+1$ we get

$$\binom{23+5}{5} - \sum_{l=0}^3(l+1)\binom{23-l+3}{3}$$

Answer 2

Assume for the moment the $5$-group consists of a leader and $4$ ordinary members. The leader can be chosen in $40$ ways. This choice creates a row of $39$ available candidates from which $4$ ordinary members have to be selected. The selection can be encoded in a binary word $w$ of length $39$, and containing exactly $4$ ones. This $w$ has the following form: $$w=0^{3+x_1}\ 1\ 0^{3+x_2}\ 1\ 0^{3+x_3}\ 1\ 0^{3+x_4}\ 1\ 0^{3+x_5}\ ,$$ where $0^{k}$ denotes a string of $k$ zeros. The $x_i\geq0$ have to satisfy $x_1+x_2+x_3+x_4+x_5=20$. By "stars and bars" there are ${24\choose4}$ different choices of the $x_i$.

In the above way each admissible $5$-group is chosen five times, but with different leaders. It follows that the number of different "unstructured" admissible $5$-groups is given by $$N=40\cdot{24\choose 4}\cdot{1\over5}=85\,008\ .$$

Answer 3

We will solve a more general problem: Find the number of ways of selecting $k$ objects from $n$ objects arranged in a circle, with every pair of selected objects separated by at least $q$ unselected objects.

Consider two blocks $A, B$ of tiles where $A$ has length $q+1$ tiles and $B$ has one tile.

Consider number of ways of placing $n - k(q+1)$ tiles of type $B$ and $k$ tiles of type $A$ in a row. This can be done in $\dbinom{n-k(q+1)+k}{k}$ ways. Having placed these, the arrangement can be placed around the circle in $n$ ways. When we choose the first cell of $A$ tiles, this counts each choice $n-kq$ times (corresponding to the circular rotation of these $n-k(q+1) + k = n-kq$ objects). $$\dfrac{n}{n-kq}\dbinom{n -kq}{k}$$

In the present problem, we have $n=40, k=5, q=3$. Hence the number of ways is $\frac{40}{25}\binom{25}{5}$