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
    @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

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

  • 0
    @Marc va$n$ 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 di$f$$f$erence between first *stone* and first *object*. :)2012-09-07
2

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

  • 0
    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).2012-09-07