1
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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

Thus the answer is

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

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Kiran Jan 14 '17 at 19:30
  • $\begingroup$ Don't go into the term "neighbor". It simply means people sitting besides each other here like your ABCD. $\endgroup$ – Gyanshu Jan 14 '17 at 19:33
  • $\begingroup$ i wrote a small program. if total number of persons is 8, I got answer as 2 $\endgroup$ – Kiran Jan 14 '17 at 19:39
  • $\begingroup$ Are you talking abt 8 out of 16? $\endgroup$ – Gyanshu Jan 14 '17 at 19:41
  • $\begingroup$ 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? $\endgroup$ – Kiran Jan 14 '17 at 19:45
2
$\begingroup$

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.

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

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.