Demostración de identidades mediante la interpretación combinatoria de coeficientes binomiales

Question

Sea $n \in \mathbb{N}$ . Demostrar las identidades $$\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}$$ y $$\sum^{n}_{k=0}\binom{n}{k}^2 = \binom{2n}{n}$$ utilizando sólo la interpretación combinatoria del coeficiente binomial.

No entiendo exactamente lo que quiere decir con " interpretación combinatoria del coeficiente binomial ". Puedo resolver la primera identidad simplemente usando el coeficiente binomial así:

$$\binom{n-1}{k-1} + \binom{n-1}{k} = \frac{(n-1)!}{(n-k)!(k-1)!} + \frac{(n-1)!}{(n-k-1)!k!} = \frac{(n-1)!k}{(n-k)!k!} + \frac{(n-1)!(n-k)}{(n-k)!k!} = \frac{(n-1)![k+(n-k)]}{(n-k)!k!} = \frac{(n-1)!n}{(n-k)!k!} = \frac{n!}{(n-k)!k!} = \binom{n}{k}$$

Y para la segunda identidad, puedo aplicar simetría, luego Vandermonde para obtener:

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

Aunque, no entiendo exactamente si el problema pide este tipo de solución, si no, me gustaría ver una prueba a las identidades utilizando interpretación combinatoria del coeficiente binomial .

Answer 1

"Utilizar una interpretación combinatoria" significa utilizar lo que el símbolo $\dbinom{n}{k}$ medios; es decir, el número de maneras de elegir $k$ cosas de $n$ cosas. En cada caso, quieres contar las cosas de dos maneras diferentes.

Pistas:

1. $\dbinom{n}{k}$ es el número de maneras de elegir $k$ cosas de $n$ . Divida el $n$ cosas en un grupo de $n-1$ y un grupo de $1$ . Si elige $k$ cosas de la $n$ ¿cuántos podría haber elegido del primer grupo? ¿Del segundo?
2. Del mismo modo, considere $2n$ cosas, y dividirlas en dos grupos de $n$ cosas. Si eliges $n$ cosas de aquellos $2n$ ¿cuántos habrá elegido del primer grupo? ¿Del segundo?

Answer 2

Creo que lo que quieren decir es un argumento como el siguiente (para la primera identidad). Sea $X$ ser un $n$ -conjunto de elementos. Entonces $\binom{n}{k}$ es el número de $k$ -subconjuntos de elementos de $X$ . Si $x\in X$ es un elemento fijo de $X$ entonces puedo dividir el $k$ -subconjuntos de elementos de $X$ en dos clases: las que contienen $x$ y los que no. El sitio $k$ -subconjuntos de elementos que no contienen $x$ son precisamente los $k$ -subconjuntos de elementos de $X-\{x\}$ y hay $\binom{n-1}{k}$ tales conjuntos. Entonces $k$ -subconjuntos de elementos de $X$ que sí contienen $x$ son todos de la forma $\{x\}\cup Y$ donde $Y$ es un $k-1$ -subconjunto de elementos de $X-\{x\}$ hay $\binom{n-1}{k-1}$ tales conjuntos. Así, en total, hay $\binom{n-1}{k} + \binom{n-1}{k-1}$ total $k$ -subconjuntos de elementos de $X$ demostrando que $$\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}.$$

Fíjese, esto se hizo puramente usando la interpretación de los coeficientes binomiales como el número de subconjuntos de un tamaño dado de un conjunto mayor; no usamos la fórmula de los coeficientes binomiales en absoluto. Creo que esto es lo que piden.