Prueba combinatoria de la suma de $\sum\limits_{k = 0}^n {n \choose k}^2= {2n \choose n}$

Question

Esperaba encontrar una prueba más "matemática", en lugar de probar lógicamente $\displaystyle \sum_{k = 0}^n {n \choose k}^2= {2n \choose n}$ .

Ya conozco la prueba lógica:

$${n \choose k}^2 = {n \choose k}{ n \choose n-k}$$

Por tanto, la suma puede expresarse como

$$\binom{n}{0}\binom{n}{n} + \binom{n}{1}\binom{n}{n-1} + \cdots + \binom{n}{n}\binom{n}{0}$$

Se puede pensar en ello como la elección de $n$ personas de un grupo de $2n$ (imagina dividir un grupo de $2n$ en $2$ grupos de $n$ personas cada uno. Puedo conseguir $k$ personas del grupo $1$ y otro $n-k$ personas del grupo $2$ . Lo hacemos desde $k = 0$ a $n$ .

Answer 1

La explicación combinatoria es sencilla. También hay una aproximación indirecta a través de las llamadas "funciones generadoras". El teorema del binomio nos dice que

$$(1+x)^n(x+1)^n=\left(\sum_{a=0}^n\binom{n}{a}x^a\right)\left(\sum_{b=0}^n\binom{n}{b}x^{n-b}\right)=\sum_{c=0}^{2n}\left(\sum_{a+n-b=c}\binom{n}{a}\binom{n}{b}\right)x^c$$

El $x^n$ coeficiente de lo anterior ocurre con $c=n$ donde el coeficiente es

$$\sum_{a+n-b=n}\binom{n}{a}\binom{n}{b}=\sum_{a=0}^n\binom{n}{a}^2.$$

Sin embargo, el $x^n$ coeficiente de $(1+x)^n(x+1)^n=(1+x)^{2n}$ , de nuevo por el teorema del binomio, es

$$\binom{2n}{n}. $$

Al igualar los dos se obtiene el resultado.

Answer 2

Desde $\dbinom n k= \dbinom n {n-k}$ la identidad $$ \sum_{k=0}^n \binom n k ^2 = \binom {2n} n $$ es lo mismo que $$ \sum_{k=0}^n \binom n k \binom n {n-k} = \binom {2n} n. $$ Digamos que un comité está formado por $n$ Demócratas y $n$ Republicanos, y uno elegirá un subcomité de $n$ miembros. Se puede elegir $k$ Demócratas y $n-k$ Los republicanos en $\dbinom n k \cdot \dbinom n {n-k}$ maneras. El número de demócratas está en el conjunto $\{0,1,2,\ldots,n\}$ Por lo tanto, van desde todos los republicanos hasta todos los demócratas. La suma da entonces el número total de formas de elegir $n$ de $2n$ .

Answer 3

$\newcommand{\angles}[1]{\left\langle\, #1 \,\right\rangle} \newcommand{\braces}[1]{\left\lbrace\, #1 \,\right\rbrace} \newcommand{\bracks}[1]{\left\lbrack\, #1 \,\right\rbrack} \newcommand{\ceil}[1]{\,\left\lceil\, #1 \,\right\rceil\,} \newcommand{\dd}{{\rm d}} \newcommand{\ds}[1]{\displaystyle{#1}} \newcommand{\expo}[1]{\,{\rm e}^{#1}\,} \newcommand{\fermi}{\,{\rm f}} \newcommand{\floor}[1]{\,\left\lfloor #1 \right\rfloor\,} \newcommand{\half}{{1 \over 2}} \newcommand{\ic}{{\rm i}} \newcommand{\iff}{\Longleftrightarrow} \newcommand{\imp}{\Longrightarrow} \newcommand{\pars}[1]{\left(\, #1 \,\right)} \newcommand{\partiald}[3][]{\frac{\partial^{#1} #2}{\partial #3^{#1}}} \newcommand{\pp}{{\cal P}} \newcommand{\root}[2][]{\,\sqrt[#1]{\vphantom{\large A}\,#2\,}\,} \newcommand{\sech}{\,{\rm sech}} \newcommand{\sgn}{\,{\rm sgn}} \newcommand{\totald}[3][]{\frac{{\rm d}^{#1} #2}{{\rm d} #3^{#1}}} \newcommand{\ul}[1]{\underline{#1}} \newcommand{\verts}[1]{\left\vert\, #1 \,\right\vert}$ \begin{align} \color{#66f}{\large\sum_{k\ =\ 0}^{n}{n \choose k}^{2}}&= \sum_{k\ =\ 0}^{n}{n \choose k} \oint_{\verts{z}\ =\ 1}{\pars{1 + z}^{n} \over z^{k + 1}}\,{\dd z \over 2\pi\ic} \\[5mm] & = \oint_{\verts{z}\ =\ 1}{\pars{1 + z}^{n} \over z} \sum_{k\ =\ 0}^{n}{n \choose k}\pars{1 \over z}^{k}\,{\dd z \over 2\pi\ic} \\[5mm]&=\oint_{\verts{z}\ =\ 1}{\pars{1 + z}^{n} \over z} \pars{1 + {1 \over z}}^{n}\,{\dd z \over 2\pi\ic} \\[5mm] & = \oint_{\verts{z}\ =\ 1}{\pars{1 + z}^{2n} \over z^{n + 1}}\,{\dd z \over 2\pi\ic} \\[5mm] & =\color{#66f}{\large{2n \choose n}} \end{align}

Answer 4

Consideremos el gráfico subyacente al triángulo de Pascal:

En este gráfico, el número en cada nodo es un coeficiente binomial y también puede considerarse como el número de caminos descendentes desde el vértice hasta ese nodo.

El lado izquierdo de la identidad es el número de caminos que comienzan en el vértice, bajan hasta el $n$ y volver al vértice (llamémosles viajes de ida y vuelta a $n$ ). Al reflejar la trayectoria de retorno sobre el $n$ se obtiene una correspondencia biyectiva entre los viajes de ida y vuelta a $n$ y caminos desde el vértice hasta el nodo central del $2n$ La tercera fila. Esto no es más que el coeficiente binomial central $\binom{2n}n$ .

Answer 5

---

Okey este es fácil(si has visto este una vez) Tenemos que mostrar: $${n \choose 0}^2+{n \choose 1}^2+\cdots+{n \choose n}^2={2n \choose n} $$ Definir un conjunto A, $$A=\{a_1,\ldots,a_n,a_{n+1},\ldots,a_{2n}\}$$ que consiste en $2n$ - Elementos. Ahora declaramos $V$ es un conjunto de $n$ -conjuntos de $A$ . Obviamente, la cardinalidad de $V,$ $$|V|={2n \choose n}.$$ Ya que se puede elegir $n$ Elementos de $2n$ Elementos en $${2n \choose n}$$ formas.

Okey ahora tenemos el lado derecho. Para el lado izquierdo tienes que dar una partición disyuntiva del $V$ conjunto. Esto debe hacerse de la siguiente manera: $V_i$ tiene exactamente $i$ -Elementos de ${a_1,\ldots,a_n}$ entonces la cardinalidad $|V_i|={n \choose i}{n \choose n-i}={n \choose i}{n \choose i}={n \choose i}^2$ . Entonces con la regla de la suma tenemos el lado izquierdo. Y ya está. La parte difícil es crear la partición para usar la regla de la suma.