Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question

3 Answers 3

up vote 5 down vote accepted

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

share|improve this answer
    
I'm not very clear on the reason for dividing by 3. –  Karan Jun 6 '12 at 17:48
    
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. –  John Engbers Jun 6 '12 at 17:53

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

share|improve this answer

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.