Combinatorics: Selecting objects arranged in a circle

Question

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?

Answer 1

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

Answer 2

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

Answer 3

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.