Prueba combinatoria de que $\sum_{i=0}^n 2^i\binom{n}{i}i!(2n-i)! = 4^n(n!)^2$

Question

Estoy buscando una prueba combinatoria de que $$\sum_{i=0}^n 2^i\binom{n}{i}i!(2n-i)! = 4^n(n!)^2.$$

Mis pensamientos hasta ahora: el RHS cuenta el número de pares de permutaciones en $n$ junto con un elemento $n$ -tupla cuyas entradas proceden de 4 opciones. El LHS podría contar lo mismo pero particionado en casos de alguna manera.

Answer 1

No es una prueba combinatoria, pero es una prueba. Podemos observar que $$ k!(2n-k)! = \Gamma(k+1)\Gamma(2n-k+1) = (2n+1)!\cdot B(k+1,2n-k+1) $$ es igual a $(2n+1)! \int_{0}^{1} x^{2n-k}(1-x)^k\,dx=(2n+1)! \int_{0}^{1} x^{k}(1-x)^{2n-k}\,dx$ Por lo tanto $$ \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 $$ y por el teorema del binomio la función integrando en el lado derecho es igual a $(1-x^2)^n$ Así que $$\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

Tampoco es una prueba combinatoria, sin embargo de

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

obtenemos al dividir por $(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 .$$

Ahora, cuando $q\gt n$ no hay contribución al coeficiente extractor delante y podemos escribir

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

Esto es

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

Como alternativa, un enfoque de sabor más combinatorio:

Multiplica ambos lados por $\binom{2n}{n}$ para que tengas $$\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},$$ entonces, usando eso $\binom{a}{b}\binom{b}{c}=\binom{a}{c}\binom{a-c}{b-c},$ obtenemos $$\sum_{i=0}^n 2^i\binom{2n}{i}\binom{2n-i}{n-i}i!(2n-i)! = 2^{2n}(2n)!,$$ cancelando los factoriales, obtenemos $$\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}.$$ Esta última expresión puede demostrarse de la siguiente manera: Consideremos una cadena binaria $x\in \{0,1\}^{2n},$ está claro que $\underbrace{|x|_0= |x|_1}_{*_1}$ ou $|x|_0\neq |x|_1,$ donde $|x|_a$ es el número de símbolos igual a $a$ en la cadena.
Si es el primer caso(es decir, $*_1$ ), entonces hay $\binom{2n}{n}=2^0\binom{2n-0}{n}$ formas de hacerlo. Si no, entonces está claro que en algún punto(yendo de izquierda a derecha) de la cadena, hay un símbolo(tenemos $2$ formas de elija el símbolo ) que se producirá $n+1$ veces, llame a este punto $2n-i+1$ con $1\leq i\leq n.$ Tienes que elegir dónde están los $n$ símbolos a la izquierda en $\binom{2n-i}{n}$ y no importa lo que le pase a la derecha para que haya $2^{2n-(2n-i+1)}=2^{i-1}$ formas de hacerlo. Por doble cuenta, el LHS es igual al RHS.

Yendo hacia atrás, y considerando la interpretación combinatoria de cada paso, se puede construir una prueba de historia en torno a esto, siendo el tema las permutaciones firmadas de $[2n].$ Por ejemplo, al dividir por el $\binom{2n}{n}$ estás diciendo que en lugar de considerar cualquier permutación, vas a considerar sólo permutaciones que el primer $n$ están en la primera $n$ y respectivamente el último $n.$ Así que, esencialmente, tienes en el RHS permutaciones coloreadas de tuplas de $n!,$ en el LHS lo mismo, pero teniendo en cuenta dónde se ve el $n+1-$ ª aparición del símbolo más frecuente en la coloración.