1
$\begingroup$

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.

  • 0
    You have mores stones than sticks - how do you avod two stones being adjacent?2012-09-07
  • 0
    It was a typo, $k$ is the number of stones of course.2012-09-07
  • 0
    When $n=k$, the formula makes no sense. What is $\binom{-1}{k-1}$?2012-09-07
  • 0
    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).2012-09-07
  • 0
    @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.2012-09-07
  • 0
    @Henning Makholm: Thank you for providing me with that link. I didn't notice the similarity of the two questions when browsing the forum for some useful hint. Apparently splitting the problem into two cases does the job. If I were able to, I would "accept" the answer you gave in the other thread. :) This one can be actually removed now.2012-09-07

2 Answers 2