Let $n$ objects be placed on a circle. We are supposed to select $k$ objects such that no $2$ of the $k$ objects are placed adjacent to each other Let us say $n$ objects are placed in a circular manner. We are supposed to select $k$ objects such that no $2$ of the $k$ objects are placed adjacent to each other in the circle.
This was what I was thinking to actually solve this problem
An alien script has $n$ letters $b_1, \cdots , b_n$.
For some $k < n/2$ assume that all words formed
by any of the k letters (written left to right) are meaningful. These words are called
$k-$words. A $k-$word is considered sacred if:
i) no letter appears twice and,
ii) if a letter $b_i$ appears in the word then the letters $b_{i-1}$ and $b_{i+1}$ do not appear. (Here
$b_{n+1} = b_1$ and $b_0 = b_n$.)
For example, if $n = 7$ and $k = 3$ then $b_1b_3b_6$, $b_3b_1b_6$, $b_2b_4b_6$ are sacred $3-$words. On the
other hand $b_1b_7b_4$, $b_2b_2b_6$ are not sacred.
What is the total number of sacred $k-$words?
But I still have no clue, how to move ahead with my thought. Can someone give me a hint.
 A: We count the number of admissible selections of one special and $k-1$ ordinary objects. The special object can be chosen in $n$ ways. When this choice is made we have a linear array of $n-1$ objects left. The selection of the  ordinary objects is a binary word of length $n-1$ having exactly $k-1$ ones. Write these ones with ample space between them and at the ends:
$$-1-1-\ldots-1-1-\ .$$
Then write one zero in each of the $k$ spaces:
$$-01-01-\ldots-01-01\>0-\ .$$
There are still $k$ spaces left, in which we have to write $n-2k$ zeros in an arbitrary way. According to stars and bars this can be done in
$${(n-2k)+(k-1)\choose k-1}={n-k-1\choose k-1}$$
ways. The total number $N$ of admissible selections of all objects then comes to
$$N={n\over k}{n-k-1\choose k-1}\ .$$
We have to divide by $k$ since in reality none of the $k$ chosen objects is specialized. E.g., when $n=5$, $\>k=2$ we obtain $N=5$, as expected.
A: It is just a stars and bars problem in disguise.
Consider $n$ objects to be placed around the circle. Consider $k$ bars to divide the the circle into $k$ parts.
Let $a_1,a_2, \ldots, a_k$ denote the number of objects between these bars.
Select the starting position of the first bar in $n$ ways.
So we have $a_1+a_2+\ldots+a_k=n-k$, and $a_i \geq 1, \forall 1 \leq i \leq k$ due to the given condition of no two choosen objects being adjacent.
Also as this is a circular permutation, each solution gets repeated by a factor of $k$. For example the tuple solution of $(a_1,a_2,\ldots a_k)$ is identical to any of the $k$ cyclic permutations of $(a_1,a_2,\ldots,a_k)$.
Hence the final answer is $\frac{n}{k}{n-k-1 \choose k-1}$.
A: Actually, once you have chosen the first element to keep, you break the circular thing.
Let's say you have $n$ objects. You have $n$ options for choosing the first object. Once this is done, you need to choose $k-1$ objects from the remaining $n-3$ (eliminating the two neighbors). But in this new case, there are no more circular behavior, just a chain.
For the next object, we have two options : either we choose one end of the chain, or an object in the middle.
There are $2$ choice for an end of the chain (except if there is only one remaining object), and then we recursively go to the same problem with $k-2$ to choose from $n-5$ objects.
If you choose an object in the middle (there are $n-5$ of them), you actually create two sub-instances of the problem : you have to choose $k-2$ between two chains of elements, whose lengths sum up to $n-6$. I would guess that this point is the most tricky one, with several combinatorics involve.
I think that decomposing the problems in sub-routines like this could help to find a recursive formula, given $n$ and $k$, but I have no further clue except for testing for small values and try to find a pattern emerging.
Hope that'll help.
