8
$\begingroup$

I'm looking for a combinatorial interpretation for the identity $$ \sum_{k=0}^n\binom nk (2k-1)!!\,(2n - 2k - 1)!! = 2^n n! $$ where $(2n - 1)!! = (2n - 1)(2n - 3) \cdots 5 \cdot 3 \cdot 1$.

Perhaps the most natural interpretation of the right-hand side is the number of $2$-colorings of the letters of the permutations on $[n] = \{1,2,...,n\}$. However, I can't find a way to make the sum fit this interpretation.

Perhaps there is a way to use the fact that $(2n-1)!!$ is the number of ways to choose $n$ disjoint pairs of items from $2n$ items?


We can do some trickery to show that this is equivalent to showing that $$ \sum_{k=0}^n\binom{2n}{n}\binom{2n-2k}{n-k} = 4^n, $$ which is addressed by this question, but I'm interested in the earlier interpretation.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.