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?
Best Answer
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)$.