[Math] There are $n$ persons sitting around a table…

combinatoricspermutations

There are $n$ persons sitting around a circular table. Then, in how many different ways 3 persons can be selected if none of them are neighbours.


My approach:-

Let us pretend that we have already picked 3 out of n persons. Now we have to place them with remaining n-3 persons in such a way that none of them are sitting together.

This can be easily done by gap method. There are 4 gaps between 3 persons in a line, xoxoxox , but there are 3 gaps between 3 persons in a circle.

So there are $(n-3)$ gaps for $(n-3)$ persons in a circle. We have to place those chosen $3$ persons in these $(n-3)$ spots. This can be done in $n-3 \choose 3$ ways which is $\frac{1}{6}(n-3)(n-4)(n-5)$. Which should be the answer because we can again pick those three and they fulfil our conditions.

But, The actual answer is $\frac{1}{6}n(n-4)(n-5)$.

The question is How?

Best Answer

There are $\binom{n}{3}$ ways of choosing $3$ people. But there are $n$ ways of choosing the three people sitting next to each other, and $n(n-4)$ ways of choosing them with 2 sitting together and one alone. Hence, there are in total $$\binom{n}{3}-n-n(n-4)=\frac{1}{6}n(n-4)(n-5)$$ ways of choosing three people such that no two of them are neighbours.