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

Question

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?

Answer 1

Unfortunately, I do not have a generating function approach as well.

Some simple cases:

If $k=0$ , then the solution is $1$.

If $k=1$, then the answer is $n$.

If $k>\frac{n}{2}$, there is no solution.

If $n > 3$ and $k \le \frac{n}{2}$: We consider $2$ cases.

• Item $1$ is chosen, hence item $n$ and item $2$ are not chosen. We still have to choose $k-1$ items from the remaining $n-3$ items where no adjacent items are chosen. We have $\binom{n-3-(k-1)+1}{k-1}=\binom{n-k-1}{k-1}$.

• Item $1$ is not chosen, hence we have to chooose $k$ items from the remaining $n-1$ items. We have $\binom{n-1-k+1}{k}=\binom{n-k}{k}$

Hence the expression should be \begin{align}\binom{n-k-1}{k-1}+\binom{n-k}{k}&=\binom{n-k-1}{k-1}+\frac{n-k}{k}\binom{n-k-1}{k-1}\\ &= \frac{n}{k}\binom{n-k-1}{k-1}\end{align}

Answer 2

As could gather, took stars & bars app., & twisted to clr.arrangement. For row, ways of selecting $k$ objects, no two consecutive, from $n$ objects is ${n-k+1\choose k}$, as at: https://math.stackexchange.com/a/3679784/424260. Now on, will use modified terms (i.e., $n',k'$) to avoid confusion.

In row based, stars & bars has categories/bars from which to choose as $n'=k+1$, as have $k+1$ spaces due to $k$ markers; while left stars $k'$ are the leftover elements after taking out $k, k-1$ elements, as for every set of $k$ objects being picked have to also choose $k-1$:
So, $n'- k - (k-1)= n' - 2k+1$ objects are left.

$\binom{\left(k+1\right)+\left(n'-2k+1\right)-1}{n'-2k+1}=\binom{n'-k+1}{k}$
with $n'- k+1-(n'-2k+1)= k$

But, clr. arrangement has still $n'=k+1$ markers, but has $k$ in-between spaces (mandatory seperators), instead of $k-1$. So, the left elements after picking up (or fixing) $k, k$ elements are:
$\binom{\left(k+1\right)+\left(n'-2k\right)-1}{n'-2k}=\binom{n'-k}{k}$
with $n'-k - k' = n'-k-(n'-2k)= k$

You have further assumed that object labelled $1$ is chosen, hence reducing the number of available objects by one.
If accept this then there will be one more object taken out as spacer, leading to a decrease of two.
Hence , need get for the row case expression

Have a doubt here, how to get difference as shown below:
As two elements have been removed, so $n'= k-2$, so further removal of an element for bar, and the accompanying spacer will get :
$n'= k-2, k'=(n')-(k-2)-(k-3)=n'-2k+5$,
that will yield :
$\binom{\left(k-2\right)+\left(n'-2k+5\right)-1}{n'-2k+5}=\binom{n'-k+2}{k-3}$
with $n'- k+2-(n'-2k+5)= k-3$