Combinatoria - ¿Contar de dos maneras?

Question

¿Cuál es la idea de demostrar una identidad binomial mediante contar de dos maneras ?

¿Podría ilustrarlo con este ejemplo? Muchas gracias.

$$\binom{2n}{n}= \sum_{k=0}^n {\binom nk}^2$$

(captura de pantalla original)

Answer 1

La idea que subyace a esta técnica es realizar la misma tarea mediante procedimientos distintos. A partir de cada procedimiento distinto, obtenemos una expresión combinatoria para el número de formas en que se puede realizar la tarea. Como la tarea es la misma, las expresiones combinatorias son las mismas.

El ejemplo más sencillo es probablemente el procedimiento que da lugar a la selección de $k$ de una colección de $n$ objetos distintos. Podríamos realizar esta tarea colocando primero el $n$ objetos en una mesa, marcando $k$ de ellos como los objetos a seleccionar, y luego mover el $k$ objetos marcados a una pila separada. Hay $\binom{n}{k}$ formas de hacerlo. Alternativamente, podríamos mirar nuestra pila, y marcar $n-k$ objetos para no seleccionar, y luego mover el resto $k$ objetos no marcados a una pila separada. Hay $\binom{n}{n-k}$ formas de marcar el $n-k$ objetos para dejar fuera de la colección. Como cada procedimiento da como resultado lo mismo, una colección de $k$ objetos-- el número de formas de realizar cada procedimiento debe ser el mismo. Por lo tanto, $$\binom{n}{k}=\binom{n}{n-k}$$

En su ejemplo dado puede pensar como sigue. El lado izquierdo $$\binom{2n}{n}$$ cuenta el número de formas de seleccionar $n$ de una colección de $2n$ objetos. Podríamos realizar esta tarea como en el caso anterior: colocar todos los objetos en una mesa y marcar $n$ de ellos para mantener lo que da la expresión anterior. Como alternativa, podríamos dividir primero el montón de $2n$ objetos en dos pilas separadas de $n$ objetos. Para obtener la colección deseada de $n$ objetos, podríamos seleccionar $k$ de la primera pila ( $\binom{n}{k}$ formas), y el resto $n-k$ de la segunda ( $\binom{n}{n-k}$ formas). Por lo tanto, el número de maneras de hacerlo es: $$\sum_{k=0}^n\binom{n}{k}\binom{n}{n-k}$$ Por lo tanto, $$\binom{2n}{n}=\sum_{k=0}^n\binom{n}{k}\binom{n}{n-k}$$ Para obtener el resultado deseado, basta con utilizar la identidad establecida anteriormente para encontrarlo: \begin {align*} \binom {2n}{n}&= \sum_ {k=0}^n \binom {n}{k} \binom {n}{n-k} \\ &= \sum_ {k=0}^n \binom {n}{k} \binom {n}{k} \\ &= \sum_ {k=0}^n \binom {n}{k}^2 \end {align*}

Answer 2

[EDITAR]

La idea que subyace a los argumentos de doble recuento es proporcionar pruebas verbales de las identidades combinatorias que permitan comprender intuitivamente por qué deben ser así. Al mostrar simplemente que dos expresiones miden diferentes formas de contar la misma cosa, queda claro, incluso para un matemático novato, que deben ser equivalentes.

---

En el lado izquierdo: $\binom{2n}{n}$ es el número de formas de dividir un conjunto de objetos distintos en dos subconjuntos de igual tamaño.

En el lado derecho: $\sum\limits_{k=0}^{n} \binom{n}{k}^2$ es el recuento de formas de redistribuir los objetos entre dos conjuntos de igual tamaño de la siguiente manera:

$\binom{n}{k}$ cuenta las formas de seleccionar $k$ forman un conjunto de $n$ objetos distintos. Así, $\binom{n}{k}^2$ cuenta las formas de hacerlo para dos conjuntos; lo que hace que sea el recuento de formas de transferir $k$ objeto de un conjunto a otro a cambio de $k$ objetos originalmente en el segundo conjunto. La suma es, por tanto, el recuento de formas de intercambiar igual número de objetos distintos entre dos conjuntos de igual tamaño, para todos los tamaños posibles de los intercambios.

Debe quedar claro que se obtiene el mismo resultado simplemente combinando los dos conjuntos y contando todas las formas de dividirlos en conjuntos de igual tamaño.

De ahí se deduce que: $\dbinom{2n}{n}=\sum\limits_{k=0}^{n} \dbinom{n}{k}^2$

Answer 3

Una prueba alternativa es la siguiente.

¿Cuál es el coeficiente de $x^n$ en $(1+x)^{2n}$ ?

Escriba esto como $(1+x)^n(1+x)^n$ . ¿Qué pasa ahora?

Nota $$\sum_{k=0}^n\binom nk^2=\sum_{k=0}^n \binom nk\binom n{k -n}=\sum_{i+j=n}\binom ni\binom nj$$

Answer 4

Dejemos que $a$ = número de formas de elegir $n$ animales de $n$ gatos y $n$ perros es $\binom{2n}{n}$ .

Dejemos que $c(k)$ = número de formas de elegir $k$ gatos de $n$ gatos = $\binom{n}{k}$

Dejemos que $d(k)$ = número de formas de elegir $n-k$ perros de $n$ perros = $\binom{n}{n-k}$ = $\binom{n}{k}$

Así, $e(k)$ = número de maneras de elegir $k$ gatos y $n-k$ perros = $c(k)*d(k) = {\binom nk}^2$

Obviamente $a$ = Número de formas de elegir $k$ gatos y $n-k$ perros para todos $k \in [0, n]$

Por lo tanto, $a = \sum_{k=0}^n e(k) = {\binom nk}^2$ . QED.