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

Question

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.

Answer 1

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*} $$

Answer 2

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

Answer 3

Alternatively, a more combinatorial flavor approach:

Multiply both sides by $\binom{2n}{n}$ so you get $$\sum_{i=0}^n 2^i\binom{2n}{\color{red}{n}}\binom{\color{red}{n}}{i}i!(2n-i)! = 4^n(n!)^2\frac{(2n)!}{n!^2},$$ then, using that $\binom{a}{b}\binom{b}{c}=\binom{a}{c}\binom{a-c}{b-c},$ we get $$\sum_{i=0}^n 2^i\binom{2n}{i}\binom{2n-i}{n-i}i!(2n-i)! = 2^{2n}(2n)!,$$ cancelling the factorials, we get $$\sum_{i=0}^n 2^i\binom{2n-i}{n} = \underbrace{2^0\binom{2n-0}{n}}_{*_1}+2\sum_{i=1}^n 2^{i-1}\binom{2n-i}{n}=2^{2n}.$$ This last expression can be proved as follows: Consider a binary string $x\in \{0,1\}^{2n},$ is clear that either $\underbrace{|x|_0= |x|_1}_{*_1}$ or $|x|_0\neq |x|_1,$ where $|x|_a$ is the number of symbols equal to $a$ in the string.
If it is the first case(i.e., $*_1$), then there are $\binom{2n}{n}=2^0\binom{2n-0}{n}$ ways to do this. If not, then is clear that at some point(going from left to right) in the string, there is a symbol(we have $2$ ways to choose which symbol) that will occur $n+1$ times, call this point $2n-i+1$ with $1\leq i\leq n.$ You need to pick where are the remaining $n$ symbols to the left in $\binom{2n-i}{n}$ and it does not matter what happens to the right so there are $2^{2n-(2n-i+1)}=2^{i-1}$ ways to do this. By double counting, the LHS is equal to the RHS.

Going backwards, and considering the combinatorial interpretation of each step, one can construct a story proof around this with the subject being signed permutations of $[2n].$ For example, when you divide by the $\binom{2n}{n}$ you are saying that instead of considering any permutation, you are going to consider just permutations that the first $n$ are in the first $n$ and respectively the last $n.$ So, essentially, you have in the RHS colored permutations of tuples of $n!,$ in the LHS the same, but taking into account where do you see the $n+1-$th occurrence of the most frequent symbol in the coloring.