Prueba ${n \choose k}^2 = \sum_{i=0}^{k}{n \choose i}{n-i \choose k-i}{n-k \choose k-i}$ usando una discusión combinatoria

Question

He estado estudiando para un examen final. Yo he conseguido pegado en esta una pregunta que nos pide demostrar mediante una prueba de doble contabilización que $${n \choose k}^2 = \sum_{i=0}^{k}{n \choose i}{n-i \choose k-i}{n-k \choose k-i}$ $

Me gustaría me podrian dar una respuesta tentativa, pero realmente no sé dónde empezar con esto. ¿Podría alguien por favor ayudarme?

Gracias

Answer 1

Vamos a pensar acerca de lo que sabemos de que el lado izquierdo se cuenta desde que es una forma más natural de expresión. $\binom{n}{k}$ cuenta el número de maneras de seleccionar los $k$ objetos de $n$ total, por lo $\binom{n}{k}^2$ cuenta el número de maneras de seleccionar los $k$ objetos de uno de los lotes de $n$ objetos y seleccionar otro $k$ objetos de diferentes lotes de $n$ objetos.

Deje que nuestro hipotético escenario de ser que tenemos dos urnas de $n$ etiquetado bolas cada uno, de una urna que contiene bolas de color rojo y una urna que contiene bolas de color azul. Cada bola va a ser etiquetado como un entero $1$ a través de $n$ tal de que exactamente uno de cada número que aparece en cada urna.

El LHS cuenta entonces, ¿cuántas maneras podemos tomar $k$ bolas rojas y $k$ bolas de color azul.

---

Tratemos de contar con esta forma diferente para que coincida con el lado derecho.

Deje $i$ denotar el número de números que coinciden entre las bolas seleccionados de la roja de la urna y el azul de la urna.

Si hay $i$ números que coinciden, nos deja escoger la $i$ números de aquellos que fueron. Esto se puede lograr en $\binom{n}{i}$ maneras.

Una vez seleccionado, nos vamos a recoger el resto de $k-i$ bolas de color azul. Esto se puede lograr en $\binom{n-i}{k-i}$ maneras.

Ahora que tenemos a nuestra selección de bolas de color azul, nos vamos a recoger el resto de $k-i$ bolas desde el rojo urna de tal manera que ninguna de ellas coincide con alguno de los números elegidos para el azul. Esto se puede lograr en $\binom{n-k}{k-i}$ maneras.

Van más de todos los posibles valores de $i$ se obtiene el número total de maneras para recoger $k$ bolas de cada urna como $\sum\limits_{i=0}^k\binom{n}{i}\binom{n-i}{k-i}\binom{n-k}{k-i}$

Puesto que ambos métodos de conteo de encontrar un recuento de el mismo escenario, las expresiones deben ser iguales. El LHS hizo sin que se refiere a la cantidad de números en las bolas elegido se superponen, mientras que el lado derecho se agrupan los términos de acuerdo a la cantidad de números en las bolas elegido superpuesta.