Hay una simple combinatoric interpretación de esta identidad?

Question

Me llegó a través de un ejercicio en el que se pide demostrar la identidad:

$${2n\choose n}=\sum_{k=0}^n{n\choose k}^2$$

El ejercicio da la pista:

$$\left(1+x\right)^{2n}=\left[(1+x)^n\right]^2$$

No es demasiado difícil de utilizar la pista para probar la identidad (de las expresiones de la identidad son los coeficientes de $x^n$ en las respectivas expansiones de las expresiones en la pista, que por supuesto debe ser el mismo número), pero me preguntaba si existe una prolija equivalente de conteo de interpretación...

Es claro que ${2n \choose n}$ es el número de maneras en las que podemos elegir la mitad de los elementos de un conjunto (donde sea posible): ¿cómo podemos interpretar $\sum_{k=0}^n{n\choose k}^2$ equivalente?

Answer 1

Deje $A,B$ ser disjuntas $n$-elemento de conjuntos; el número de $n$-elemento de subconjuntos de a$A\cup B$ es $\binom{2n}n$. Por otro lado, podemos obtener cualquier $n$-elemento subconjunto de $A\cup B$ , de la siguiente manera: comienza con el conjunto $A$; elegir un número $k$ de $0$ a $n$; tire $k$ elementos de $A$ y reemplazarlos con $k$ elementos de $B$. En otras palabras, cualquier $n$-elemento subconjunto de $A\cup B$ tiene la forma $(A\setminus X)\cup Y$ donde $X\subseteq A$, $Y\subseteq B$, $|X|=|Y|=k$ para algunos $k\in\{0,\dots,n\}$. El número de grupos diferentes que podemos obtener de esta manera es $\sum_{k=0}^n\binom nk\binom nk$.

Answer 2

Este es también un bien saben interpretación.

Vamos a pensar en un camino más corto de $(0,0)$ a $(n,n)$ a través de la celosía de puntos y en paralelo a $x$-eje o $y$-eje.

El número de total de la forma en que se ${2n \choose n}$.

Y cada camino más corto debe pasar una y sólo una de las diagonales de los puntos de $(0,n), (1,n-1), \ldots, (n,0)$.

La suma de todas manera es $\sum_{k=0}^n{n\choose k}^2$.

Por lo tanto, tanto el valor de la misma.

Answer 3

Otra interpretación: Como Erick Wong indicado en los comentarios, $$\binom{n}{k}^2 = \binom{n}{k}\binom{n}{n - k}$$ Podemos interpretar $$\binom{2n}{n}$$ como el número de maneras de seleccionar los $n$ de las personas de un grupo que consiste de $n$ hombres y $n$ mujeres. La expresión $$\binom{n}{k}\binom{n}{n - k}$$ cuenta el número de maneras de seleccionar exactamente $k$ hombres y $n - k$ mujeres. Desde $k$ puede variar de $0$ a $n$, la CARTA también cuenta el número de maneras de seleccionar los $n$ personas de $n$ hombres y $n$ mujeres. Por lo tanto, $$\binom{2n}{n} = \sum_{k = 0}^{n} \binom{n}{k}\binom{n}{n - k} = \sum_{k = 0}^{n} \binom{n}{k}^2$$