Una suma combinatoria difícil

Question

Estoy buscando una expresión limpia de la siguiente suma combinatoria:

%#% $ De #% recuerdo que lo hace tienen una expresión cuidada.

Sin embargo, no estoy familiarizado con la combinatoria o nada relacionado con evaluar sumas finitas no triviales como esto, por lo que básicamente falta métodos tacke esto.

¡Cualquier idea sería genial!

Answer 1

Podemos simplificar un poco la reorganización de la factoriales: $$ \frac{\binom nk^2}{\binom{2n}{2k}} = \frac{\frac{n!\,n!}{k!\,k!\,(n-k)!\,(n-k)!}}{\frac{(2n)!}{(2k)!\,(2n-2k)!}} = \frac{n!\,n!}{(2n)!} \cdot \frac{(2k)!}{k!\,k!} \cdot \frac{(2n-2k)!}{(n-k)!\,(n-k)!} = \frac{\binom{2k}{k} \binom{2(n-k)}{n-k}}{\binom{2n}{n}}. $$ Así que esto nos permite factor de un plazo que no depende de la $n$: $$ \sum_{k=0}^n \frac{\binom nk^2}{\binom{2n}{2k}} = \frac{1}{\binom{2n}{n}} \sum_{k=0}^n \binom{2k}{k}\binom{2(n-k)}{n-k}. $$ La suma de lo que queda simplifica muy bien el uso de funciones de generación, a pesar de que yo no soy consciente de que una buena manera de hacerlo que evita ellos. Si partimos de la identidad $$ \frac1{\sqrt{1-4x}} = \sum_{i \ge 0} \binom{2i}{i} x^i $$ entonces podemos concluir que el coeficiente de $x^n$ en el cuadrado de $\frac{1}{\sqrt{1-4x}}$ es, precisamente, la suma que queremos: la suma como $k$ $0$ $n$representa el coeficiente de $x^k$ tomado de uno de los factores veces el coeficiente de $x^{n-k}$ tomado de la otra. Pero el coeficiente de $x^n$ $\frac{1}{1-4x}$ es sólo $4^n$: es una serie geométrica. Así llegamos a la conclusión de que $$ \sum_{k=0}^n \frac{\binom nk^2}{\binom{2n}{2k}} = \frac{1}{\binom{2n}{n}} \sum_{k=0}^n \binom{2k}{k}\binom{2(n-k)}{n-k} = \frac{4^n}{\binom{2n}{n}}. $$

Answer 2

Para la primera parte, usando la misma forma de reordenar como @MishaLavrov han hecho: $$\frac{\binom nk^2}{\binom{2n}{2k}} = \frac{\frac{n!\,n!}{k!\,k!\,(n-k)!\,(n-k)!}}{\frac{(2n)!}{(2k)!\,(2n-2k)!}} = \frac{n!\,n!}{(2n)!} \cdot \frac{(2k)!}{k!\,k!} \cdot \frac{(2n-2k)!}{(n-k)!\,(n-k)!} = \frac{\binom{2k}{k} \binom{2(n-k)}{n-k}}{\binom{2n}{n}}.$$

La motivación detrás de hacer esta era conseguir un buen momento de forma, significa hacer el denominador constante para una constante $n$, por lo que el trato con la suma puede ser mucho más fácil. Ahora, para evitar que la forma de usar funciones de generación para obtener la suma, la voy a utilizar combinatoria argumento. Vamos a concentrarnos en la suma $$\sum_{k=0}^n \binom{2k}{k}\binom{2(n-k)}{n-k}$$ Argumento:

Para el grupo específico, compuesto de $2n$ de la gente, van a elegir a $k$ niños y $(n-k)$ niñas. Para elegir este tipo de personas, grupo será dividido a $2k$ grupo de personas y $2(n-k)$ grupo de personas, cada una para niño y niña. Encontrar el número de casos de satisfacer la condición(grupo compuesto de la misma gente se considerará el mismo grupo, no importa el orden). A continuación, podemos hacer que el problema de la instrucción como la siguiente: en primer lugar, elija $k$ niños y $(n-k)$ niñas. en segundo lugar, elegir $k$ chicos de la deserción y la $n-k$ de las niñas de la deserción. Cada uno de no interferir otro caso, por lo que la fórmula viene a ser $(\sum_{k=0}^{n})\binom{n}{k})^2$,$4^n$.

Por lo tanto, la suma de: $$\frac{1}{\binom{2n}{n}} \sum_{k=0}^n \binom{2k}{k}\binom{2(n-k)}{n-k}=\frac{4^n}{\binom{2n}{n}}.$$