Choose K items from N in a circle

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

-

migrated from stackoverflow.comJun 26 '11 at 18:33

This question came from our site for professional and enthusiast programmers.

If you want someone else to solve your homework for you, try using the search functionality. – Joshua K Jun 26 '11 at 18:22
This isn't really my homework sir. Already tried searching. Was trying to solve this problem spoj.pl/problems/CHAIR Spent quite some time but couldn't get the formulae right. So thought of seeking help, because this is basic maths that I'm messing up with. – user488652 Jun 26 '11 at 18:25
@user: Could you write what kind of approaches you've tried? – user6701 Jun 26 '11 at 18:27
I thought first I'll figure out all the ways to choose k from n in a circle, then subtract the possible cases when k are always together. if n items are in a circle and i want to choose 1 then there are n ways. But not able to form a formulae for circular thing. – user488652 Jun 26 '11 at 18:33
Why was this migrated? Except for the first sentence, this seems more like a dynamic programming question. – user6701 Jun 26 '11 at 18:51

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.

-
Another way to see that $L(n,k) = {{n-k+1}\choose{k}}$ is to realize that in effect we're just counting the number of ways to put $n-k$ marbles into $k+1$ boxes if we're required to put at least one marble into each box except the first and last. Then of course we just subtract the ${{n-k-1}\choose{k-2}}$ ways of doing so that put no marbles in the first and last boxes. – Brian M. Scott Jun 27 '11 at 2:44
@Brian M. Scott: Yes. In my post I was describing how I got to the result. Maybe should have mentioned that of course I tried to tackle the problem directly (while driving). Saw that trying to push to a "smaller" problem inevitably cuts the circle, so there seemed no good alternative to solving the line problem. – André Nicolas Jun 27 '11 at 4:00
Your approach was still nicer than mine: I calculated $C(n,k)$ for small values of $n$ and $k$, spotted the recurrence, recognized the numbers as differences of binomial coefficients, and then proved everything! I didn't see the easy marbles-and-boxes argument until I read your answer. – Brian M. Scott Jun 27 '11 at 4:10

Assuming that $1 \le k \le n/2$, the desired number is ${{n-k+1}\choose{k}} - {{n-k-1}\choose{k-2}}$, where it's understood that ${{n}\choose{-1}} = 0$.

Let $f(k,n)$ be the number of ways to choose $k$ non-adjacent elements from a circle of $n$ elements, where we assume that $1 \le k \le n/2$. Clearly $f(1,n) = n$, and it's not hard to see that $f(k,2k) = 2$ for all $k$: either you take all of the items in the odd-numbered positions, or you take those in the even-numbered positions. Let $\mathcal A(k,n)$ be the set of $k$-element subsets of $\{0,1,\dots,n-1\}$ having no two adjacent members, where $0$ and $n-1$ are considered adjacent; $f(k,n) = |\mathcal A(k,n)|$.

Suppose that $A \in \mathcal A(k+1,n+1)$. If $n \notin A$ and $\{0,n-1\} \nsubseteq A$, then $A \in \mathcal A(k+1,n)$; conversely, $\mathcal A(k+1,n) \subseteq \mathcal A(k+1,n+1)$. Otherwise, either $n \in A$, or $n \notin A$ and $\{0,n-1\} \subseteq A$.

If $n \in A$, $\{0,n-1\} \cap A = \emptyset$, and $A \setminus \{n\} \in \mathcal A(k,n-1)$; conversely, if $0 \notin A \in \mathcal A(k,n-1)$, then $A \cup \{n\} \in \mathcal A(k+1,n+1)$. If $n \notin A$ and $\{0,n-1\} \subseteq A$, then $A \setminus \{n-1\} \in \mathcal A(k,n-1)$; conversely, if $0 \in A \in \mathcal A(k,n-1)$, then $n-2 \notin A$, so $A \cup \{n-1\} \in \mathcal A(k+1,n+1)$.

It follows from the last two paragraphs that the function $f$ satisfies the recurrence $$f(k+1,n+1) = f(k+1,n) + f(k,n-1),$$

and I claim that $f(k,n) = {{n-k+1}\choose{k}} - {{n-k-1}\choose{k-2}}$, where it's understood that ${{n}\choose{-1}} = 0$. Certainly ${{k+1}\choose{k}}-{{k-1}\choose{k-2}} = 2 = f(k,2k)$ and ${{n}\choose{1}}-{{n-2}\choose{-1}} = n$, so the initial conditions are satisfied, and the following calculation verifies the recurrence: \begin{align*}f(k+1,n)+f(k,n-1)&= {{n-(k+1)+1}\choose{k+1}} - {{n-(k+1)-1}\choose{(k+1)-2}}\\ &\qquad {}+ {{(n-1)-k+1}\choose{k}} - {{(n-1)-k-1}\choose{k-2}}\\ &={{n-k}\choose{k+1}} - {{n-k-2}\choose{(k-1}} + {{n-k}\choose{k}} - {{(n-k-2}\choose{k-2}}\\ &={{n-k}\choose{k+1}} + {{n-k}\choose{k}} - {{n-k-2}\choose{(k-1}} - {{(n-k-2}\choose{k-2}}\\ &={{n-k+1}\choose{k+1}} - {{n-k-1}\choose{k-1}}\\ &={{(n+1)-(k+1)+1}\choose{k+1}} - {{(n+1)-(k+1)-1}\choose{(k+1)-2}}\\ &=f(k+1,n)+f(k,n-1) \end{align*}

-
@Ben: Thanks for the formatting. – Brian M. Scott Jun 27 '11 at 2:54
No problem, hopefully now it's a little easier to understand! – Ben Alpert Jun 27 '11 at 3:56

Circle or a straight line doesn't make a difference. The number of way to choose k items from n is always nCk or "n choose k" or n!/(k!(k+n)!)

First, we arrange $k$ distinct elements in a circle in order. Next, put rest elements of $n$-element set in the positions between them (each place at least one).$$x_1 + x_2 + \cdots + x_k = n-k,$$ where $x_i \ge 1$ for all $i.$ So,the number of different arrangements is equal to the number of integer solutions of equation above. It is, obviously, $$\binom{n-k-1}{k-1}=\frac{k}{n-k} \binom{n-k}{k}.$$
The correct answer is $\frac{n}{n-k} \binom{n-k}{k}$, not $\frac{k}{n-k} \binom{n-k}{k}.$ – Byron Schmuland Apr 16 '13 at 19:14