n people sit on a round table.$2\leq k\leq {n+1\over 2}$ are chosen from the n.

n people sit on a round table.$2\leq k\leq {n+1\over 2}$ are chosen from the n. Find the probability that no two people from the group of k chosen sat at the table beside each other. This maybe can be done using Caplanski theorem..

I tried $A_i$-person $i$, in the group of $k$ chosen has at least one neighboor in the group of k. $A=\bigcup_{i=1}^{n} A_i$; $B$-the desired outcome; $B=1-A...$

• could you please explain more clear what do you mean by "no two chosen people sat at the sat beside each other"? – xecafe Mar 26 '15 at 12:31

1 Answer

Suppose we represent a chosen person by "$*$" and a non-chosen person by "$o$". Then any selection of $k$ non-adjacent people corresponds to a linear arrangement of $k$ lots of "$*o$" and $n-2k\;$ lots of "$o$", where the leftmost position in the line is person $1$ and the rightmost position is person $n$. To illustrate, if $n=8,k=3$ then the selection of persons $2,5,7$ corresponds to the arrangement

$$o*o\;o*o*o$$

The number of such arrangements is $\binom{n-k}{k}$ since we must simply choose $k$ positions for the "$*0$"s from $n-k$ available positions.

However, these arrangements only account for selections where person $n$ is not chosen because the last position must always be "$o$". So to account for these others where person $n$ is chosen, we now assume the last position in the arrangement is "$*$" and the first is "$o$" and the remaining positions are any arrangement of $k-1$ lots of "$*o$" and $n-2k$ lots of "$o$". By similar reasoning as above, the number of such arrangements is $\binom{n-k-1}{k-1}$.

Now the total number of ways to choose $k$ people from $n$ is $\binom{n}{k}$. Therefore the required probability is:

$$\dfrac{\binom{n-k}{k} + \binom{n-k-1}{k-1}}{\binom{n}{k}}.$$