Interpretation of combinatorial identity involving binomial coefficients

72 Views Asked by At

I proved that for some positive integers $n$, $k\leq n-1$ and $l\leq k$ the following identity is satisfied.

$$\binom{k-1}{l-1}\binom{n-k-1}{l-1}\dfrac{n}{l} = \binom{k}{l}\binom{n-k-1}{l-1} +\binom{k-1}{l-1}\binom{n-k}{l}$$

Now I am looking for an interpretation of the right hand side. It arises from the problem of red and blue colored necklaces of length $n$ where exactly $k$ are colored blue and $n-k$ are colored red. $l$ is the number of connected components of each color, which has to be the same for both colors since the colors have to alternate. Hence, the problem is symmetric for $k$ and $n-k$ which explains the two summands. But I am a bit lost in how to interpret each summand in the context of necklaces.

Could you give me a hint or explain how it works?

1

There are 1 best solutions below

0
On BEST ANSWER

Hint: Most likely you know that $\binom{k-1}{l-1}$ is creating all the sequences of size $l$ of blue connected balls. (Usually called a composition)

Either the sequence start at blue or at red. If they start at blue do the following:

Place all blue balls in a line, and select $l$ of them in $\binom{k}{l}$ ways. Then create a sequence of the red balls in $\binom{n-k-1}{l-1}$ and place the first part after the first selected blue ball, the second part after the second selected blue ball, etc.. In this way you create every possible necklace starting with a blue ball. By the multiplication principle, you created $\binom{k}{l}\binom{n-k-1}{l-1}$ sequences. Do the same for the red ones.