Ayuda con una prueba con combinación: $ \binom {n}{k} \binom {k}{m} = \binom {n}{m} \binom {n-m}{k-m}$

Question

Tengo que probarlo:

$ \binom {n}{k} \binom {k}{m} = \binom {n}{m} \binom {n-m}{k-m}$

No estoy muy seguro de cómo abordar este problema. Conozco la definición de la fórmula de la combinación pero no estoy seguro de cómo aplicarla a esta cuestión

Answer 1

$$ \binom {n}{m} \binom {m}{k} = \frac {n!}{m!(n-m)!} \frac {m!}{k!(m-k)!}= \frac {n!}{(n-m)!} \frac {1}{k!(m-k)!}= \frac {n!}{k!} \frac {1}{(m-k)!(n-m)!}= \frac {n!}{k!(n-k)!} \frac {(n-k)!}{(m-k)!(n-m)!}= \binom {n}{k} \frac {(n-k)!}{(m-k)!((n-k)-(m-k))!}= \binom {n}{k} \binom {n-k}{m-k}$$

Answer 2

Hay $n$ Buñuelos (sanos), todos de diferentes sabores. Queremos elegir $m$ de ellos para comer hoy, y $k-m$ de ellos para comer mañana. Contamos el número de formas de hacer esto, de dos maneras diferentes.

Camino 1: Escoge el $k$ rosquillas que comeremos hoy y mañana. De estos, los de hoy pueden ser elegidos en $ \binom {k}{m}$ para un total de $ \binom {n}{k} \binom {k}{m}$ .

Camino 2: Escoge los que se van a comer hoy. Esto se puede hacer en $ \binom {n}{m}$ maneras. De las restantes $n-m$ elige el $k-m$ para mañana, el número total de formas $ \binom {n}{m} \binom {n-m}{k-m}$ .

Las dos respuestas deben ser iguales.

Answer 3

Aquí hay una prueba conceptual. En ambos lados estamos eligiendo un $k$ subconjunto de elementos de un $n$ y luego un conjunto de elementos $m$ subconjunto de elementos de la $k$ conjunto de elementos. Hay dos maneras de hacer esto. Primero elegir el $k$ y luego elegir el conjunto de elementos $m$ subconjunto de elementos, este es el lado izquierdo. La otra forma es primero elegir el $m$ y luego elegir el subconjunto de elementos adicionales $k-m$ elementos para formar el $k$ conjunto de elementos. Este es el lado derecho.

Answer 4

Dado $n$ gente, podemos formar un comité de tamaño $k$ en ${n \choose k}$ maneras. Una vez que se forme el comité podemos formar un subcomité de tamaño $m$ en ${k \choose m}$ maneras. Así podemos formar un comité de tamaño $k$ con un subcomité de tamaño $m$ en ${n \choose k}{k \choose m}$ maneras. Podemos contar lo mismo formando primero el subcomité y luego el comité que contiene el subcomité. Dado que $n$ personas podemos formar un subcomité de tamaño $m$ en ${n \choose m}$ maneras. Una vez que el subcomité se forme, debemos formar el comité de tamaño $k-m$ de los restantes $n-m$ la gente en ${n-m \choose k-m}$ maneras. Así podemos formar un subcomité de tamaño $m$ mientras formaba el comité de tamaño $k-m$ que contiene el subcomité en ${n \choose m}{n-m \choose k-m}$ maneras. Por lo tanto ${n \choose k}{k \choose m}={n \choose m}{n-m \choose k-m}$ .

Esta identidad combinatoria se conoce como la identidad del subconjunto de un subconjunto.

Answer 5

$ \dbinom {n}{k} \dbinom {k}{m}$ cuenta las formas de dividir $n$ los artículos en tres pilas de tamaño $n-k$ , $k-m$ y $m$ quitando primero $k$ de los artículos y luego dividiendo esos artículos.

$ \dbinom {n}{m} \dbinom {n-m}{k-m}$ cuenta las formas de dividir $n$ los artículos en tres pilas de tamaño $m$ , $n-m$ y $n-k$ seleccionando primero $m$ y luego dividir el resto.

---

$ \begin {align} \dbinom {n}{k} \dbinom {k}{m}&= \dfrac {n!}{k!\, n-k!} \dfrac {k!}{m!\, (k-m)!} \\ &= \dfrac {n!}{(n-k)!\,(k-m)!\,m!} \\ &= \dfrac {n!}{m!\,(n-m)!} \dfrac {(n-m)!}{(n-k)!\,(k-m)!} \\ &= \dbinom {n}{m} \dbinom {n-m}{k-m} \end {align}$