Find the number of ways to choose $k$ objects from a set of $n$ objects arranged in a circular order such that no two consecutive elements are chosen.

I could think of a combinatorial solution-

Arrange the objects such that they are in a row and not in a circular order. To begin with, the objects are arranged as $\{1,2,3,\cdots,n\}$ (in that order). From the stars and bar method it can be seen that there are a total of ${n-k-1}\choose{k-1}$ ways to choose $k$ objects from the row such that no two are adjacent assuming that object $1$ is chosen. This can be repeated and we can start from all $n$ objects instead of object $1$. But then there's going to be $k$ repeats. And thus the answer gets boiled down to ${\frac{n}{k}} \times {{n-k-1}\choose{k-1}} = \left(\frac{n}{k}\right) {{n-k-1}\choose{k-1}}$.

I have this solution but then I feel that there are some nice ways using generating functions to solve this. Can anyone help me out?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.