# number of ways in which $4$ people can be chosen from $16$ people

Total number of ways in which $4$ people can be chosen from $16$ people sitting in a circle such that no two of them are neighbors.

Number of ways of choosing $4$ persons out of $16$ persons, is $\displaystyle \binom{16}{4}$.

Won't be able to go further, could someone help me with this, thanks.

Without any restrictions, there are $\dbinom{16}{4}$ ways

$16$ ways where all four people are neighbors

$16\dbinom{11}{1}$ ways where exactly three people are neighbors

Now for the case when two people are neighbors, no. of ways would be $$16\dbinom{12}{2}-\frac{16*11}{2}$$

$16\dbinom{12}{2}$ might look as the number of ways in which $2$ people are also sitting together. But we are counting twice the cases in which $2$ people are neighbors and the other $2$ are also sitting together.

So, first we have to count the number of cases in which $2$ pairs of people are sitting together.

There would be $16$ ways of selecting $2$ people sitting together.

Now for the other two we are left with $12$ people to choose from. There would be $11$ ways to select other $2$ neighboring people. Right now we have $16*11$ but we double counted each pair of neighbors. Ask me in the comments if you didn't get this part.

So, it would be $16*11/2$.

$$\dbinom{16}{4}-16-\left(16\dbinom{12}{2}-\frac{16*11}{2}\right)-16\dbinom{11}{1}=660$$

• I was very confused after writing my answer. Take a small example. Suppose A,B,C,D,E,F,G,H are 8 persons sitting in a circle. So, can u tell me any combination of 4 persons where all of them are neighbors? if we take ABCD, A is near to B, B is near to C, C is near to D. But A and D are not neighbors. So, in ABCD, only three adjacent pairs are there, right? – Kiran Jan 14 '17 at 19:30
• Don't go into the term "neighbor". It simply means people sitting besides each other here like your ABCD. – Gyanshu Jan 14 '17 at 19:33
• i wrote a small program. if total number of persons is 8, I got answer as 2 – Kiran Jan 14 '17 at 19:39
• Are you talking abt 8 out of 16? – Gyanshu Jan 14 '17 at 19:41
• selection of 4 persons from 8 persons named (a,b,c,d,e,f,g,h) and valid combinations are aceg and bdfh according to a program I wrote. Verifying the results now. Can u see more? – Kiran Jan 14 '17 at 19:45

The number of ways to choose $k$ non-consecutive persons on a circle of size $n$ is -

${n-k+1 \choose k} - {n-k-1 \choose k-2}$

First term is the number of ways to choose k non-consecutive positions on a size n and the second term subtracts off those arrangements where positions 1 and n were both chosen.

I am taking reference Aryabhata explanation in the answer here.

• please explain me how you get that formula, thanks – DXT Jan 14 '17 at 14:37
• this gives 660 as output – Kiran Jan 14 '17 at 20:46
• @Kiran Yes 660 is the right answer. – Kanwaljit Singh Jan 15 '17 at 2:10