# Combinatorial proof that $\sum_{i=0}^n 2^i\binom{n}{i}i!(2n-i)! = 4^n(n!)^2$

I'm looking for a combinatorial proof that $$\sum_{i=0}^n 2^i\binom{n}{i}i!(2n-i)! = 4^n(n!)^2.$$

My thoughts so far: the RHS counts the number of pairs of permutations on $$n$$ elements along with an $$n$$-tuple whose entries come from 4 choices. The LHS might count the same thing but partitioned into cases somehow.

• You can improve the question by explaining the source of the identity - without a proof, why do you know it is true in the first place? Where did the identity arise? These things make the question more compelling as well as helping others write answers that fit into the situation where the identity applies. – Carl Mummert Oct 24 '18 at 14:05

## 2 Answers

Not a combinatorial proof, but still a proof. We may notice that $$k!(2n-k)! = \Gamma(k+1)\Gamma(2n-k+1) = (2n+1)!\cdot B(k+1,2n-k+1)$$ equals $$(2n+1)! \int_{0}^{1} x^{2n-k}(1-x)^k\,dx=(2n+1)! \int_{0}^{1} x^{k}(1-x)^{2n-k}\,dx$$, hence $$\sum_{k=0}^{n}2^k\binom{n}{k}k!(2n-k)! = (2n+1)!\int_{0}^{1}\sum_{k=0}^{n}\binom{n}{k}(2x)^k (1-x)^{2n-k}\,dx$$ and by the binomial theorem the integrand function in the RHS equals $$(1-x^2)^n$$, so $$\begin{eqnarray*} \sum_{k=0}^{n}2^k\binom{n}{k}k!(2n-k)! &=& (2n+1)!\int_{0}^{1}(1-x^2)^n\,dx\\&=&\tfrac{1}{2}(2n+1)!\int_{0}^{1} x^{-1/2}(1-x)^{n}\,dx\\&=&\tfrac{1}{2}(2n+1)!\cdot B\left(\tfrac{1}{2},n+1\right)=\color{red}{4^n n!^2}.\end{eqnarray*}$$

Not a combinatorial proof either, however from

$$\sum_{q=0}^n {n\choose q} 2^q q! (2n-q)! = 4^n (n!)^2$$

we obtain on dividing by $$(n!)^2$$

$$\sum_{q=0}^n {2n-q\choose n-q} 2^q = \sum_{q=0}^n [z^{n-q}] (1+z)^{2n-q}2^q = [z^{n}] (1+z)^{2n} \sum_{q=0}^n z^q (1+z)^{-q} 2^q .$$

Now when $$q\gt n$$ there is no contribution to the coefficient extractor in front and we may write:

$$[z^{n}] (1+z)^{2n} \sum_{q\ge 0} z^q (1+z)^{-q} 2^q \\ = [z^{n}] (1+z)^{2n} \frac{1}{1-2z/(1+z)} = [z^{n}] (1+z)^{2n+1} \frac{1}{1-z}.$$

This is

$$\sum_{q=0}^n [z^q] (1+z)^{2n+1} [z^{n-q}] \frac{1}{1-z} = \sum_{q=0}^n {2n+1\choose q} = \frac{1}{2} 2^{2n+1} = 4^n.$$