1
$\begingroup$

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?

$\endgroup$

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.