1
$\begingroup$

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

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

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}}.$$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.