There are $n$ persons sitting around a table...

Question

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?

Answer 1

Other people have explained how to get the correct answer, so I will just focus on why your answer is wrong: there is no one-to-one correspondence between the ways to choose three gaps between $n-3$ people and the ways to choose three non-neighbor people out of $n$. Let's call the people in your gaps problem $A_1, \dots, A_{n-3}$, and the people in the original problem $B_1, \dots, B_n$. If you put three additional persons between $A$s, how would you choose which $B$s correspond to them? For example, you can always identify $A_1$ with $B_1$, but then you will only get the ways to choose three $B$s other than $B_1$. So you see that the answer to the gaps problem is smaller than the answer to the original problem.

By the way, since every person (for example, $B_1$) is selected in exactly $\frac 3n$ of all the ways to choose three non-neighboring $B$s, what you should get your way is $1-\frac 3n$ of the correct answer. And this is exactly what you get: $\frac 16(n-3)(n-4)(n-5) = (1-\frac 3n)\cdot \frac 16n(n-4)(n-5)$.

Answer 2

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.

Answer 3

You have $n$ ways to choose person 1. For example if $n=13$, pick one person: 0000001000000. Then there are two choices sitting one away from him, as in either 0000201000000 or 0000001020000. After picking one of those, there are five spaces you cannot pick so finally you are left with $n-5$ choices for the third person: 3330201033333. But if you choose the second person sitting two seats away from the first person, you have $n-5$ choices for the second person 2222001002222 and then you have $n-6$ choices for the third person: 3302001033333. That covers both the cases. In equations: $$ \begin{align} n\times[2\times(n-5)+(n-5)\times(n-6)]&=n\times(n-5)\times(n-6+2)\\ &=n\times(n-4)\times(n-5) \end{align} $$ Then divide by six for the duplicates.

Answer 4

In your answer you pick $n-3$ seats and count the number of ways to pick three people from these $n-3$ seats. This is completely different from the question! Example: $n = 7$, seats numbered clockwise. You pick seats $1,2,4,6$ and leave $3,5,7$ as gaps. Then you count the configuration $1,2,4$ even though it has neighbours and you don't count $1,3,6$ which has no neighbours.

To find the correct solution, I refer to the other answers here.

Answer 5

First pick one out which can be done on $n$ ways.

Then picking out two others comes to the same as writing $n-3$ as a sum of $3$ positive integers. Equivalent is writing $n-6$ as a sum of $3$ nonnegative integers and there are $\binom{n-4}{2}=\frac{1}{2}\left(n-5\right)\left(n-4\right)$ ways to do that.

So we seem to end up with $\frac{1}{2}n\left(n-5\right)\left(n-4\right)$ ways. However, each way is counted $3$ times. This because each way offers $3$ possible seats for the person that is picked out first.

Dividing by $3$ repairs that: $$\frac{1}{6}n\left(n-5\right)\left(n-4\right)$$