In how many ways can we choose k items from n distinct items put in a circle.
Then further extension of the question, if I want to find out the number of ways to choose k items from n distinct items in a circle such that no 2 are together.
Thanks
Combinatorics – Choose K Items from N in a Circle
combinatorics
Related Solutions
Here is a copy of an answer I gave to a similar post (I'll edit it to fit your question a bit better):
The formula for permutations is $\frac{n!}{(n-k)!}$
The formula for combinations is $\frac{n!}{k!(n-k)!}$
(Here I assume you understand the permutation formula a bit). To derive the second from the first let's make an example... say we are finding the combinations of $3$ numbers from a set of $4$, say $1,2,3,$ and $4$. If we use the permutation formula we get our answer as $24$, but we can see we over-counted... for example, $1,2,3$ and $1,3,2$ were counted separately. Since we are taking sets of size $3$ and there are $3!$ ways to arrange a set of size $3$, we have over-counted by a factor of $3!$. Generalizing this, if we use the permutation formula to get combinations we will always over-count by $k!$, where $k$ is the size of the set we take from the whole, and hence the formula for combinations above (we say order does not matter with combinations because of that division... every set we take is unique no matter how we arrange it. This is not true for permutations).
EDIT: Since you are new to this, we get the permutations formula by first choosing one from a set of $n$, then $(n-1)$, then $(n-2)$, and we do this until we get $(n-k+1)$, yielding $P(n,k)=n(n-1)(n-2)(n-3)\ldots(n-k+1)$ (The last case avoids $0$ when $n=k$). We then multiply by (n-k)! to get $$P(n,k)=\frac{n(n-1)(n-2)(n-3)\ldots(n-k+1)(n-r)!}{(n-r)!}$$ $$= \frac{[n(n-1)(n-2)\ldots(n-k+1)]\cdot[(n-k)(n-k-1)\ldots(3)(2)(1)]}{((n-r)!}$$ $$= \frac{n!}{(n-r)!}$$ (The last step requires an observation about the descending nature of the numerator... I leave it as a math puzzle to you!)
a) Correct
b) No. You have 12 choices on the first item. 12 on the second. 12 on the third, fourth and fifth. So it should be $12^5$.
c) Correct
d) This is a bit tricky, I shall explain this below.
We have $C$ for combination, $P$ for permutation, and the first time I was taught this one (order does not matter + repetition allowed), my teacher called it $H$ although I am not sure if it is standard notation.
Anyway, the formula in general is $H_r^{n}=C_r^{n+r-1}$.
The reasoning behind this is as follows (for simplicity we shall take $H_5^{12}$ as in this case as an example):
Let the $12$ possible choices be $a,b,c,\dots,l$.
We don't care about the order here, we only care about how many of each item you choose, and with each choice, we can assign with it a unique "binary code".
For example, if you choose $aabbc$, then we write $0010010111111111$ where the first two $0$'s represent the two $a$'s, after the $1$ we have two $0$'s for the two $b$'s, and so on.
As another example, $abjkl$ is represented by $0101111111101010$.
In this way, each possible choice can be represented by a string of five $0$'s and eleven $1$'s for a total of $16$ numbers. So to count all possible choices, we simply have to choose the five places to insert the $0$'s.
This is given by $C_5^{16}$, hence $H_5^{12}=C_5^{16}$
Best Answer
The problem is simpler to think about if we first imagine that the objects are in a line, not in a circle. Perhaps if I were a harmonic analyst I would find it easier to think in circles.
We analyze the line problem, and then make a simple adjustment to solve the circle problem.
Let $L(n,k)$ be the number of ways of choosing $k$ objects from a line of $n$ objects, no two of them adjacent.
There are two possibilities (i) the first (leftmost) object in the line is among the chosen ones and (ii) the first object is not among the chosen ones.
In case (i), the second object cannot be chosen, which leaves $L(n-2,k-1)$ possibilities for the remaining $k-1$. In case (ii), we need to choose $k$ objects from $n-1$, giving $L(n-1,k)$ possibilities. We have obtained the recurrence $$L(n,k)=L(n-2,k-1)+ L(n-1,k).$$ With the obvious initial conditions, the solution of this recurrence is given by $$L(n,k)=\binom{n-k+1}{k}.$$ It is not hard to check that the above is a solution of the recurrence. There should be a bijective argument that makes it obvious, you choose the people and pad the choice with a blank seat to the right, most of the time, but I can't quite make it work. Annoying! Boring old induction does work, however.
Now let's adapt this to the circle, by bending the line and connecting the ends. Let $C(n,k)$ be the number of allowed choices.
Some of the choices that were counted in $L(n,k)$ now become "bad." They are the arrangements in a line in which we chose both endpoints. Everything else is fine.
Now count the bad line choices. We chose both endpoints, so could not choose the next to end points, so needed to choose $k-2$ points from $n-4$. There are $L(n-4,k-2)$ ways to do that. Putting things together, we get $$C(n,k)=\binom{n-k+1}{k}-\binom{n-k-1}{k-2}$$ (if $k$ satisfies the obvious constraint).
It was obvious!: For the line, think of the following operation. Imagine $n-k+1$ chairs laid out in a row, and choose any $k$ of them. Now for every chosen chair except the rightmost one, add a chair immediately to the right of the chosen chair. Then we get an acceptable arrangement.
Conversely, given any acceptable arrangement, remove the chair immediately to the right of every chosen chair except the rightmost one. In this way we obtain a choice of $k$ chairs from $n-k+1$ chairs. It follows that obviously $$L(n,k)=\binom{n-k+1}{k}$$ and the fussing with a recurrence for $L(n,k)$ was unnecessary. But I am leaving the original solution intact, to show that clean solutions do not come instantly, at least not to me.