Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
4  
If you want someone else to solve your homework for you, try using the search functionality. –  Joshua K Jun 26 '11 at 18:22
1  
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
1  
@user: Could you write what kind of approaches you've tried? –  user6701 Jun 26 '11 at 18:27
1  
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
2  
Why was this migrated? Except for the first sentence, this seems more like a dynamic programming question. –  user6701 Jun 26 '11 at 18:51
show 1 more comment

migrated from stackoverflow.com Jun 26 '11 at 18:33

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

4 Answers

up vote 3 down vote accepted

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.

share|improve this answer
    
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
add comment

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*}$

share|improve this answer
    
@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
add comment

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)!)

Read up more here http://en.wikipedia.org/wiki/Combination

share|improve this answer
    
Actually it does, in the second part of the question. –  André Laszlo Jun 26 '11 at 18:24
add comment

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}.$$

share|improve this answer
    
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.