# 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.

• Where do you find these strange sentences @Carl Mummert? What as you thinking, when you wrote them down? And where did you find these words? – coffeee Mar 12 at 9:18

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.$$