argumento combinatorio que $ [\binom{n}{0}+\binom{n}{1}+\dots+\binom{n}{n}]^{2} = \sum_{k=0}^{2n}\binom{2n}{k}$

Question

Dé un argumento combinatorio con doble conteo que demuestre que $$ \Bigg[\binom{n}{0}+\binom{n}{1}+\dots+\binom{n}{n}\Bigg]^{2} = \sum_{k=0}^{2n}\binom{2n}{k}$$

No estoy seguro de cómo enfocar este problema desde un argumento combinatorio perspectiva. He encontrado una prueba analítica utilizando el teorema del binomio, pero no puedo formular una explicación de la manera anterior.

Según tengo entendido, $\displaystyle \sum_{k=0}^{n} {n \choose k}$ representa el número de formas en que podemos elegir un conjunto de $k$ objetos de un grupo de $n$ objetos, para $k \le n$ . Así que esta cantidad al cuadrado debería ser equivalente al número de formas de elegir un conjunto de $k$ objetos de un grupo de $2n$ objetos.

¿Alguien podría darme alguna pista sobre cómo abordar este problema? combinatoriamente ?

Answer 1

Ambos lados describen el número de formas de seleccionar cualquier número de elementos de $2n$ (y ambos son iguales a $2^{2n}$ )

Vamos a escribir $A=\{1,\dots,n\}$ y $B=\{n+1,\dots,2n\}$ .

Ahora los subconjuntos de $A\cup B$ están en biyección con los pares de un subconjunto de $A$ y un subconjunto de $B$ .

$$\mathcal{P}(A\cup B) \to \mathcal{P}(A)\times \mathcal{P}(B)$$ $$S \mapsto (S\cap A, S \cap B)$$

También $$|\mathcal{P}(A\cup B)| = \sum_{k=0}^{2n} |\{S\subseteq A\cup B \mid |S|=k\}| = \sum_{k=0}^{2n} \binom{2n}{k}$$ $$|\mathcal{P}(A)| = \sum_{k=0}^{n} |\{S\subseteq A \mid |S|=k\}| = \sum_{k=0}^{n} \binom{n}{k}$$ $$|\mathcal{P}(B)| = \sum_{k=0}^{n} |\{S\subseteq B \mid |S|=k\}| = \sum_{k=0}^{n} \binom{n}{k}$$

Así que $$RHS = |\mathcal{P}(A\cup B)| = |\mathcal{P}(A)||\mathcal{P}(B)| = LHS$$

Answer 2

Digamos que tenemos $n$ pizzas y o tienen queso o no tienen queso. Cada pizza puede tener queso o no tenerlo, $2$ opciones para $n$ pizzas, así que $2^n$ maneras. Sin embargo, también puedes calcularlo de esta manera. En primer lugar, encuentre el número de maneras de tener $0$ sin queso y $n$ queso. Podemos elegir $0$ pizza que no sea de queso, así que $n \choose 0$ . Además, podemos tener $1$ sin queso y $n-1$ queso, así que elija $1$ pizza para comer $1$ sin queso fuera de $n$ pizzas, por lo que obtenemos $n \choose 1$ . ¿Ves a dónde vamos? Seguimos calculando y finalmente obtenemos la suma ${n \choose 0} + {n \choose 1} + \dots + {n \choose {n-1}} +{n \choose n}$ y sabemos que esto es igual a $2^n$ , por lo que esta suma al cuadrado debe ser $2^{2n}$

Ahora mira el lado derecho. Cada pizza puede tener queso o no tenerlo, $2$ opciones para $2n$ pizzas, así que $2^{2n}$ formas. Sin embargo, también puedes calcularlo de esta manera. En primer lugar, encuentre el número de maneras de tener $0$ sin queso y $2n$ queso. Podemos elegir $0$ pizza que no sea de queso, así que $2n \choose 0$ . Además, podemos tener $1$ sin queso y $2n-1$ queso, así que elija $1$ pizza para comer $1$ sin queso fuera de $2n$ pizzas, por lo que obtenemos $2n \choose 1$ . ¿Ves a dónde vamos? Seguimos calculando y finalmente obtenemos la suma ${2n \choose 0} + {2n \choose 1} + \dots + {2n \choose {n-1}} +{2n \choose n}$ y sabemos que esto es igual a $2^{2n}$ .

Así, hemos mostrado ambos lados iguales a $2^{2n}$ Así que hemos terminado.

Answer 3

Ambas partes cuentan el número de subconjuntos elegidos entre $n$ hombres y $n$ mujeres. La LHS lo hace contando el número de hombres y mujeres de forma independiente, condicionando el número $k$ de cada uno. El RHS hace el recuento condicionando el número $k$ de personas fuera de $2n$ .

Answer 4

Se puede combinar el razonamiento combinatorio y el analítico de la siguiente manera. Dado un conjunto $\,A = \{a_1,a_2,\dots,a_n\}\,$ con $\,n\,$ elementos, y un subconjunto $\,S\subseteq A,\,$ para cada $\,i\in\{1,2,\dots,n\}\,$ el binomio $\,x_i+y_i\,$ representa la condición de que $\,a_i\in S.\,$ Es decir, la elección $\,x_i\,$ indica que $\,a_i\in S\,$ y $\,y_i\,$ indica que $\,a_i\notin S.\,$ Utilizando el principio multiplicativo de opciones independientes, el producto $\,P_A:=(x_1+y_1)(x_2+y_2)\cdots(x_n+y_n)\,$ se expande en una suma de monomios que representa todos los subconjuntos de $\,A.\,$ Si $\,B=\{b_1,b_2,\dots,b_m\}\,$ es otro conjunto disjunto de $\,A,\,$ y la unión disjunta $\,C=A\cup B,\,$ entonces todos los subconjuntos de $\,C\,$ está representado por el producto $\,P_C = P_AP_B\,$ donde cada subconjunto $\,S\subseteq C\,$ se divide de forma única como $\,S=S_A\cup S_B.\,$ Aquí $\,x_{i+n}\,$ indica que $\,b_i\in S_B\,$ y $\,y_{i+n}\,$ indica que $\,b_i\notin S_B.\,$

Dado este resultado, consideremos el caso especial en el que $\,x_i=x,\, y_i=y\,$ para todos $\,i\,$ . Entonces $$ P_A = (x+y)^n = \sum_{j=0}^n x^jy^{n-j}{n\choose j},$$ $$ P_B = (x+y)^m = \sum_{k=0}^m x^ky^{m-k}{m\choose k},$$ $$ P_C = (x+y)^{n+m} = \sum_{i=0}^{n+m} x^iy^{n+m-i}{n+m\choose i}. $$ Cuando $\,n=m\,$ y $\,x=y=1\,$ su resultado es el siguiente.