Ayuda con prueba combinatoria de identidad binomial: $\sum\limits_{k=1}^nk^2{n\choose k}^2 = n^2{2n-2\choose n-1}$

Question

Considere la siguiente identidad:

\begin{equation} \sum\limits_{k=1}^nk^2{n\choose k}^2 = n^2{2n-2\choose n-1} \end{equation}

Consideremos el conjunto a $S$ del tamaño de la $2n-2$. Dividimos $S$ en dos conjuntos de $A$$B$, cada uno de tamaño $n-1$. Ahora, además de la partición de $S$ a $n$ partes: $C_0, C_1, \ldots C_{n-1}$

Mediante la adición principio de que tenemos ${2n-2\choose n-1} = \sum\limits_{k=0}^{n-1}C_k$

Además, cada una de las $C_k$ está dado por ${n-1\choose k}{n-1\choose n-1-k}={n-1\choose k}^2$ desde $k$ de los elementos será en $A$ $n-1-k$ elementos $B$. Así tenemos: \begin{align} \sum\limits_{k=0}^{n-1}{n-1\choose k}^2 =&{2n-2\choose n-1} \end{align} Indización: \begin{equation} \sum\limits_{k=1}^{n}{n-1\choose k-1}^2 = {2n-2\choose n-1} \end{equation} Aquí es donde yo estoy perdido. No puedo pensar en una combinatoria argumento de la $n^2$ y lo que queda a la izquierda. Si usted tiene mejores ideas omitir este! Mi primer pensamiento es el siguiente:

\begin{equation} \sum\limits_{k=1}^{n}n{n-1\choose k-1}^2 = n{2n-2\choose n-1} \end{equation} Este es el recuento de la misma cosa, pero, ¿qué es $n$? La razón por la que hago esto es porque ahora todo lo que necesito es un $k$ en la suma en el lado izquierdo:

\begin{equation} \sum\limits_{k=1}^{n}kn{n-1\choose k-1}^2 = \sum\limits_{k=1}^{n}k^2\dfrac{n}{k}{n-1\choose k-1}^2 = \sum\limits_{k=1}^{n}k^2{n\choose k}^2 \end{equation}

Y de alguna manera esto es equivalente a la RHS $n^2{2n-2\choose n-1}$, sin embargo, ¿cuál es la combinatoria argumento?

Gracias por toda la ayuda!

Answer 1

$$\sum_{k=1}^nk^2\binom{n}k^2=n^2\binom{2n-2}{n-1}\;.\tag{1}$$

Ha $n$ hombres y $n$ mujeres. Usted quiere elegir a un equipo de $n+1$ de la gente, y en este equipo va a designar a un hombre y a una mujer como co-capitanes. Usted puede elegir el co-capitanes en $n^2$ formas, y entonces usted puede elegir el resto del equipo en $\binom{2n-2}{n-1}$ maneras, por lo que la parte derecha de $(1)$ cuenta los posibles equipos.

Ahora vamos a contar los equipos con exactamente $k$ mujeres, para $k=1,\dots,n$. Hay $\binom{n}k$ formas de elegir a las mujeres, y $k$ formas de designar a uno la mujer co-capitán. Hay, a continuación, $n$ maneras de escoger el macho co-capitán y $\binom{n-1}{n-k}$ formas de seleccionar el resto de los hombres. Y

$$kn\binom{n}k\binom{n-1}{n-k}=kn\binom{n}k\binom{n-1}{k-1}=k^2\binom{n}k^2\;,$$

de modo que el lado izquierdo cuenta la misma cosa según el número de mujeres en el equipo.

Answer 2

Esta es sólo una manera de reformular la respuesta de Brian Scott, de modo que se evita cualquier manipulación algebraica de coeficientes binomiales.

Considerar la coloración de los cuadrados de a $2\times n$ rectángulo con los colores rojo, blanco, azul, sujeto a las siguientes restricciones

• Exactamente uno de los cuadrados de cada uno de los dos hileras debe ser de color blanco,
• No debe ser $n-1$ cada uno de rojo y de azul los cuadrados.

Cada solución tiene el mismo número de cuadrados azules en la primera fila como el rojo plazas en la segunda fila; dejar que este número se $n-k$ ( $1\leq k\leq n$ ). Ahora para cualquier solución con este valor de $k$ debemos elegir en la primera fila $k-1$ rojo plazas, $1$ cuadrado blanco y $n-k$ cuadros azules, y en la segunda fila del mismo modo con el rojo y el azul intercambiados. Para cada fila de este número está dado por el trinomio coeficiente de $\binom n{k-1,1,n-k}$, dando $$ \sum_{k=1}^n\binom n{k-1,1,n-k}^2 $$ soluciones en todos. Por otro lado, uno puede simplemente elegir el blanco de plazas en dos filas (dando el factor de $n^2$) y, a continuación, el $n-1$ rojo plazas entre el resto de los $2(n-1)$, para $$ n^2\binom{2(n-1)}{n-1} $$ posibilidades. Finalmente, el trinomio coeficiente de arriba puede ser visto para ser $k\binom nk$: $\binom nk$ formas de elegir el subconjunto de la primera de dos colores juntos, y $k$ opciones para el único cuadrado blanco entre ellos.

Answer 3

Considere un grupo de 2n personas .Ahora consideran que existen dos grupos($A,B$) de n personas.

A partir de los grupos(de 2n personas) tiene que seleccionar un grupo más pequeño de $n+1$ personas la selección de un representante de cada grupo $A,B$

Explicación de los RHS.

En primer lugar seleccione el representante de cada grupo.Esto se puede hacer en $n^2$ formas anthe resto del equipo puede ser seleccionado en $\binom{2n-2}{n-1}$ maneras.

Ahora del lado izquierdo,

A partir de las n personas del primer grupo podemos seleccionar el $k$ personas $\binom{n}{k} $ formas , de entre las personas k se puede seleccionar un representante en $k$ maneras .Por lo que el total no. de formas de seleccionar el grupo y el representante de la $k$ personas $k\binom{n}{k}$ .De manera similar, en caso de que el grupo 2 hay $k\binom{n}{k}$.Por lo que el total de uso no. de las formas en que el $$\sum _{k=1}^{n}k^2\binom{n}{k}^2$$

Como en los dos casos, estamos haciendo lo mismo pero de una manera diferente,por lo que debemos tener,

$$\sum _{k=1}^{n}k^2\binom{n}{k}^2=n^2\binom{2n-2}{n-1}$$