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.

Possible Duplicate:
Number of triangles inside given n-gon?

Let $f(n,k)$ denote the number of arrangements of $k$ stones and $n-k$ sticks in a circle in such a way that no two stones are adjacent to each other. If one arrangement can be obtained from another after a circular shift, it is considered different. I am to prove that $f(n, k) = \dfrac{n}{k}{n-k-1 \choose k-1}$, where $0 < k \leq n$.

What I've been thinking of is to begin with a chain of consecutive $k$ stones/sticks \[ \cdots \circ | \circ | \circ | \circ \cdots \]

(they're supposed to be arranged in a circle). This serves as a "base" for any valid arrangement of $k$ stones, $n-k$ sticks (because there must be at least one stick between two consecutive stones). Then we insert the remaining $n-2k$ sticks in the $k$ "separating" places (no matter whether we add a new stick immediately before or after an existing stick, as they're indistinguishable). There're ${n - k - 1 \choose k-1}$ such distributions.

I'm stuck at this point though, since this is mereley the number of different patterns of arranging sticks and stones. What I'm still missing is, how to count the number of ways to "apply" those patterns to the circle (i.e. how to fit the stones and sticks in the $n$ distinct places around it).

I believe this isn't a very difficult problem, but somehow I can't find a way to reach the desired result and need some help.

share|improve this question

marked as duplicate by Henning Makholm, William, Quixotic, rschwieb, J. M. Sep 20 '12 at 17:04

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

    
You have mores stones than sticks - how do you avod two stones being adjacent? –  Hagen von Eitzen Sep 7 '12 at 13:58
    
It was a typo, $k$ is the number of stones of course. –  Quintofron Sep 7 '12 at 14:01
    
When $n=k$, the formula makes no sense. What is $\binom{-1}{k-1}$? –  Cameron Buie Sep 7 '12 at 14:14
    
I think you meant the last binomial coefficient you wrote (choosing with repetition $2n-k$ out of $k$) to be $\binom{n-k-1}{k-1}$ (as well). –  Marc van Leeuwen Sep 7 '12 at 14:40
    
@Marc van Leeuwen: Yes, it should be ${n - k - 1 \choose k-1}$. Thanks for pointing this out, as only now have I found a very silly mistake in some algebraic transformation I did. –  Quintofron Sep 7 '12 at 16:46

2 Answers 2

Once you have found that there are $g(n,k)$ linear arrangements, you can select one of these arrangements and one of the $n$ positions of the circle and arrange the sequence in such a manner that the first stone is in the selected position (yeah, anybody else would put the first object there). This gives us $n\cdot g(n,k)$ as count of all circular arrangements together with one stone (the one placed in the selected position, i.e. originally the first stone of the linear arrangement) marked as special.

We could also start by selecting one of the $f(n,k)$ circular arrangements and pick one of the $k$ stones as special. Hence $k\cdot f(n,k) = n\cdot g(n,k)$.

share|improve this answer
    
It is not clear to me which linear arrangements you are counting (or OP for that matter). It seems to me that you are counting only those that start with a stone; if not the $n\cdot g(n,k)$ is overcounting. –  Marc van Leeuwen Sep 7 '12 at 14:38
    
To me it also seems there are configurations we would count multiple times (when multiplying the result above by $n$). I took into consideration this case, but the problem with overcounting was apparent. –  Quintofron Sep 7 '12 at 14:48
    
@Marc van Leeuwen: Yes, indeed, I partially overlooked that. The linear arrangements counted must be those starting with a stone and ending with a stick to make my argument work. Moreover, there is no longer a difference between first stone and first object. :) –  Hagen von Eitzen Sep 7 '12 at 15:07

In this equivalent question the answer was given as $$ \binom{n-k}k+\binom{n-k-1}{k-1} = \binom{n-k+1}{k+1} - \binom{n-k-1}{k-2} $$ Now use the first of those, together with $\binom{n-k}k=\frac{n-k}k\binom{n-k-1}{k-1}$ and $\frac{n-k}k+1=\frac nk$.

share|improve this answer
    
I myself obtained the LHS by applying the absorption and induction identities to $\dfrac{n}{k}{n-k-1 \choose k-1}$ (that's what I started with when trying to figure out how to reach the expected result). The problem was to get there from the other side (thanks for showing me the link to the other thread). –  Quintofron Sep 7 '12 at 15:29

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