El reto: demostrar esta identidad entre bi y trinomio coeficientes?

Question

Esta pregunta es la continuación de su predecesor.

Mediante el convenio que trinomio coeficientes de $$ \binom{n}{k_1,k_2,k_3}=\frac{n!}{k_1! k_2! k_3!} $$ son cero si $k_i<0$ o $\sum_i k_i\neq n$, tenemos la siguiente relación entre el binomio y trinomio coeficientes, $$ \binom{2n}{\ell} = \sum_{k=0}^{\lfloor \frac{\ell}2 \rfloor} 2^{\ell-2k} \binom{n}{\ell-2k,k,n-\ell+k} = \sum_{k=\max(\ell-n,0)}^{\lfloor \frac{\ell}2 \rfloor} \frac{2^{\ell-2k} n!}{(\ell-2k)!\,k!\,(n-\ell+k)!}, \quad (*) $$ y, en particular, $$(2n)!=\sum_{k=0}^{\lfloor \frac{n}2 \rfloor} \frac{2^{n-2k} (n!)^3}{(n-2k)!\,(k!)^2}.$$

Me encontré con esta identidad como un producto de una calidad diferentes, y mi pregunta es, ¿cómo uno puede demostrar esta identidad directamente - por ejemplo, a través de la generación de funciones u otras herramientas de número de formulario de la teoría (que no es mi experiencia por un tiro largo) - y pensó que este podría ser un reto interesante.

Originalmente he publicado sólo el último de identidad, donde Semiclásica resolver esto por un doble conteo de argumento (después de la primera recuperación de la forma del coeficiente binomial).

Desde el trinomio coeficiente puede trivialmente se divide en dos coeficientes binomiales, también podría ser posible la adaptación de la doble contabilización argumento para esto, pero no es inmediatamente obvio para mí. Utilizando el mismo método que en Semiclásica de la respuesta, contando las maneras de poner $\ell$ (wlog $\le n$) 1s en un $2\times n$-matriz de tomar $k$ columnas de ceros (0), $m$ columnas de 1s y $n-k-m$ columnas con 0 y 1 no parece funcionar, porque $m$ tendría que ser simultáneamente $k$ (por la potencia de 2), $\ell-2k$ (para el coeficiente binomial) y $\ell+k-n$ para la condición de que no se $\ell$ 1s.

Algunas observaciones:

• Traté de búsqueda de esta identidad, sin éxito, y estaría interesado en una referencia, si alguien ha visto cosas similares aparecer en cualquier otra parte.
• He probado con éxito el (primer) identidad numéricamente, lo cual me da bastante seguro de que no he cometido un error en la prueba (la indirecta versión se mencionó anteriormente).
• Visualmente, la relación también podría ser interesante interpretación: Como los coeficientes binomiales corresponden a triángulo de Pascal, por lo que el trinomio coeficientes corresponden a la de Pascal, del tetraedro (o Pascal de la pirámide). Por lo tanto, $(*)$ significa que ciertas sumas ponderadas dentro de la $n^{\mathrm{th}}$ nivel de Pascal del tetraedro dar la $(2n)^{\mathrm{th}}$ fila del triángulo de Pascal, como se ilustra a continuación para $n=5$.

Answer 1

Podemos probar esto en una mancha de la forma a través de la Serpiente método del Aceite de Wilf (ver el enlace en los comentarios de la OP). Para hacer la notación mucho más sencilla, observamos que el rango de $k$ $l$ es aplicada por los coeficientes binomiales--se desvanecen para enteros no válido para contar, y entonces las sumas de $k,l$ son asumidas $\mathbb{Z}$.

Ese convenio en mente, se multiplica la RHS por $x^l$ y la suma de todos los enteros $l$:

\begin{align} \sum_{\ell,k} \binom{n}{\ell-2k,k,n-\ell+k}2^{\ell-2k} x^\ell &= \sum_{\ell, k} \binom{n}{\ell,k,n-\ell-k}2^{\ell} x^{\ell+2k}\\ &= \sum_{\ell, k} \binom{n}{\ell,k,n-\ell-k}(2y)^{\ell} (x^2)^k\\ &= (x^2+2x+1)^n \end{align}

En la primera igualdad, se han desplazado $\ell \mapsto \ell+2k$; reorganizar un poco, reconocemos la forma de que el trinomio teorema y por lo tanto la suma de la serie. Pero podemos factor de esta expresión a$(1+x)^{2n}$, por lo que aplicar el binomio teorema para obtener el $l$-ésimo coeficiente como $\binom{2n}{l}$. Comparando esto con nuestra primera expresión da el deseo de identidad.

Answer 2

Supongamos que buscamos evaluar (hacer algunas re-escribir como se observa en el OP) $$\sum_{k=0}^n {n\choose k} 2^{l-2k} {n-k\choose n-l+k}.$$

Inicio de $${n-k\elegir n-l+k} = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{n-l+k+1}} (1+z)^{n-k} \; dz.$$

Esto le da la siguiente integral por la suma $$\frac{1}{2\pi i} \int_{|z|=\epsilon} \sum_{k=0}^n {n\elegir k} 2^{l-2k} \frac{1}{z^{n-l+k+1}} (1+z)^{n-k} \;dz \\ = \frac{2^l}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^n}{z^{n-l+1}} \sum_{k=0}^n {n\elegir k} 2^{-2k} \frac{1}{z^k(1+z)^k} \;dz \\ = \frac{2^l}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^n}{z^{n-l+1}} \left(1 + \frac{1}{4z(z+1)}\right)^n \; dz \\ = \frac{2^l}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^n}{z^{n-l+1}} \left(\frac{1+4z+4z^2}{4z(z+1)}\right)^n \; dz \\ = \frac{2^l}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^n}{z^{n-l+1}} \frac{(1+2z)^{2n}}{2^{2n} (z(1+z))^n} \; dz \\ = \frac{2^{l-2n}}{2\pi i} \int_{|z|=\epsilon} \frac{(1+2z)^{2n}}{z^{2n-l+1}} \; dz.$$

Esta última integral se puede evaluar por la inspección y los rendimientos $$2^{l-2n} [z^{2n-l}] (1+2z)^{2n} = 2^{l-2n} \times {2n\elegir 2n-l} 2^{2n-l} = {2n\elegir l}.$$

Un seguimiento de cuándo este método apareció en el MSE, y por el que se inicia en este MSE enlace.