Skip to main content
2 of 2
deleted 1 character in body
sdd
  • 109
  • 1
  • 11

Curious identity involving the number of perfect matchings of the complete graph

Can you prove (preferably combinatorially) the following identity for the total number of perfect matchings of the complete graph $K_{2n}$, where the edges in the matching are ordered, i.e., $\binom{2n}{2,2,\ldots ,2} = \frac{(2n)!}{2^{n}} = n!(2n-1)(2n-3)\cdots 1$:

$$ \binom{2n}{2,2,\ldots ,2} = \prod_{k=1}^{n} \left[\binom{n+1}{2}-\binom{k}{2}\right] = n\prod_{j=1}^{n-1} [n+(n-1)+ \ldots + (n-j)]. $$

It is also immediate to show that the total number of matchings is $\prod_{i=2}^{n} [i(i+(i-1))]$.

Thus it suffices to show that for every $n\geq 1$, \begin{equation} n[n+(n-1)]\cdots [n+(n-1)+\cdots + 1] = [n(n+(n-1))][(n-1)((n-1)+(n-2))]\cdots [2(2+1)]. \end{equation}

Algebraic proof would be also of some help. I tried by induction unsuccessfully.

sdd
  • 109
  • 1
  • 11