I've conjectured the following identity, which I can reason combinatorically. Assuming $M$ is even, then

$$ \sum_{\text{even }m}^{M}\binom{M}{m}^2m!\ [(M-m-1)!!]^2\overset{?}{=}(2M-1)!!\,,$$

where the double factorial of odd argument $(2n-1)!!=\frac{(2n)!}{2^nn!}$ is the number of distinct pairings of the elements of a set of size $2n$.

Given two sets of (even) $M$ members each, the left hand side of the equation is the number of unique ways to pair $m$ elements from one set with elements from the other, while the rest are paired internally within their respective sets, summed over $m$. For odd values of $m$ no total pairing is possible. The right hand side is then just the number of ways to pair up a single group with $2M$ elements in total.

Numerically, this identity holds (I checked for even $M$ up to 10), and feeding the lhs to Mathematica, it is simplified to the right hand side. I hoped that this can be shown by applying some binomial theorem, but after expanding all the factorials on the lhs, couldn't see how this would be done. I'm interested in the actual proof, because I would want to generalize this result in two ways: 1. Weighing the sum over $m$ by some $x^m$, and 2. Applying this to two sets of differing sizes $M_{1,2}$ (whose sum is even), so something analogous to

$$ \sum_{m}\binom{M_1}{m}\binom{M_2}{m}m!\ (M_1-m-1)!!\ (M_2-m-1)!!\ x^m \ =\ ?$$


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.