14
$\begingroup$

If $n$ distinct objects are arranged in a circle, I need to prove that the number of ways of selecting three of these $n$ things so that no two of them are next to each other is $\frac{1}{6}n(n-4)(n-5)$.

Initially I can select $1$ object in $n$ ways. Then its neighbours cannot be selected. So I will have $n-3$ objects to choose $2$ objects from. Again, I can select the second object in $n-3$ ways. The neighbours of this object cannot be selected. However from here onwards, I am unable to extend this argument as the selection of the third object is dependent on the position of the first and the second object. Is there any simpler method to prove the result?

|cite|improve this question
$\endgroup$
10
$\begingroup$

Choose one object first. Then think of the remaining $n-3$ objects in a line. There are then $n-4$ spaces in between the remaining $n-3$ objects in the line. Choose 2 of the $n-4$ spaces and choose the object to the left of the left space and right of the right space.

This last step is in 1-1 correspondence with the ways to have the final 2 objects; therefore we divide by 3 (corresponding to the initial first choice, which could have been any of the 3 objects to start) giving $1/3 \cdot n \cdot \binom{n-4}{2} = 1/6 \cdot n(n-4)(n-5)$.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ I'm not very clear on the reason for dividing by 3. $\endgroup$ – Karan Jun 6 '12 at 17:48
  • $\begingroup$ Think about a fixed set of objects of size 3. The argument given, without dividing by 3, will count this subset 3 times, since it will count that particular set of 3 once for each time that one of the 3 objects is considered the 'first' object. Perhaps looking at an example ($n=6$) will be helpful. $\endgroup$ – John Engbers Jun 6 '12 at 17:53
9
$\begingroup$

References: The number of ways to choose $d$ non-consecutive positions on a circle of size $n$ is $${n-d+1 \choose d} - {n-d-1 \choose d-2}.$$ Aryabhata explains the derivation in the answer here Consecutive birthdays probability. The first term is the number of ways to choose $d$ non-consecutive positions on a line of size $n$, and the second term subtracts off those arrangements where positions $1$ and $n$ were both chosen.

This expression can also be rewritten as $${n\over n-d}{n-d\choose d}.$$ This form, called $d_k$ in the following link, is used in the solution of the menage problem, (with $2n$ instead of $n$, and $k$ instead of $d$).

|cite|improve this answer
$\endgroup$
5
$\begingroup$

Hint Count the ways to select them so that at least two are neighbours (you can divide this into two cases). This is easier. Then substract from the total number of ways of selecting three objects. Then factorize your result, and you'll get the answer.

|cite|improve this answer
$\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.