Skip to main content
Bumped by Community user
Bumped by Community user
Bumped by Community user
Bumped by Community user
deleted 1 character in body
Source Link
sdd
  • 109
  • 1
  • 11

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.

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.

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.

Source Link
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.