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.


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.