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.

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.
