Evaluar $\sum_{k=0}^{n} {n \choose k}{m \choose k}$ para un determinado $n$$m$.

Question

¿Cómo puedo evaluar $\sum_{k=0}^{n} {n \choose k}{m \choose k}$ para un determinado $n$$m$.

He intentado utilizar el binomio de expansión y combinar factoriales, pero he conseguido nada. Realmente no sé cómo empezar este problema.

La respuesta es ${n+m \choose n}$. Cualquier ayuda es muy apreciada.

EDIT: estoy buscando una prueba de esta identidad.

Answer 1

Utilice el hecho de que (en lo que sigue de la definición) $$\binom{m}{k}=\binom{m}{m-k}.$$ Una vez que usted tiene esta del lado izquierdo puede escribirse como $$LHS=\sum_{k=0}^n\binom{n}{k}\binom{m}{k}=\sum_{k=0}^n\binom{n}{k}\binom{m}{m-k}.$$

Ahora podemos hacer una combinatoria argumento para encontrar esta suma. Considere un grupo de $n$ hombres y $m$ mujeres. Queremos hacer un comité compuesto de $m$ de la gente. Esto se puede hacer en cualquiera de las siguientes maneras:

1). $0$ hombres y $m$ mujeres\begin{align} 0 & = \int_C \left(x - \frac12\right)^3\;dm_\phi = \int_C x^3 - \frac32 x^2 + \frac34x - \frac18 \;dm_\phi \\ & = \int_C x^3\;dm_\phi -\frac32\cdot\frac38 + \frac34\cdot\frac12 - \frac18 = \int_C x^3\;dm_\phi -\frac{5}{16}. \endesta selección puede hacerse en $\binom{n}{0}\binom{m}{m}$ maneras.

2). $1$ hombre y $m-1$ mujeres-----esta selección puede hacerse en $\binom{n}{1}\binom{m}{m-1}$ maneras.

y así sucesivamente.....

m+1). $m$ hombres y $0$ mujeres-----esta selección puede hacerse en $\binom{n}{m}\binom{m}{0}$ maneras.

La suma total de esta le da al lado izquierdo. Pero este problema también puede resolverse considerando la elección de $m$ de personas de un grupo de $m+n$ de la gente, que se puede hacer en $\binom{n+m}{m}$ maneras. Por eso, las dos maneras de contar debe ser igual.

$$\sum_{k=0}^n\binom{n}{k}\binom{m}{m-k}=\binom{n+m}{n}=\binom{n+m}{m}$$

Answer 2

El uso de la Vandermonde de Identidad, esto es $$ \sum_{k=0}^n\binom{n}{n-k}\binom{m}{k}=\binom{n+m}{n} $$

---

La prueba de la Identidad de Vandermonde

$$ \begin{align} \sum_{k=0}^{m+n}\color{#C00000}{\binom{m+n}{k}}x^k &=(1+x)^{m+n}\tag{1}\\ &=(1+x)^m(1+x)^n\tag{2}\\ &=\sum_{j=0}^m\binom{m}{j}x^j\sum_{k=0}^n\binom{n}{k}x^k\tag{3}\\ &=\sum_{j=0}^m\sum_{k=j}^{n+j}\binom{m}{j}\binom{n}{k-j}x^k\tag{4}\\ &=\sum_{k=0}^{m+n}\color{#C00000}{\sum_{j=0}^k\binom{m}{j}\binom{n}{k-j}}x^k\tag{5} \end{align} $$ Explicación:
$(1)$: teorema del binomio
$(2)$: propiedad de los exponentes
$(3)$: teorema del binomio
$(4)$: sustituto $k\mapsto k-j$
$(5)$: cambiar el orden de la suma de

Comparar los coeficientes de $x^k$.

Answer 3

$\newcommand{\+}{^{\daga}} \newcommand{\ángulos}[1]{\left\langle\, nº 1 \,\right\rangle} \newcommand{\llaves}[1]{\left\lbrace\, nº 1 \,\right\rbrace} \newcommand{\bracks}[1]{\left\lbrack\, nº 1 \,\right\rbrack} \newcommand{\ceil}[1]{\,\left\lceil\, nº 1 \,\right\rceil\,} \newcommand{\dd}{{\rm d}} \newcommand{\down}{\downarrow} \newcommand{\ds}[1]{\displaystyle{#1}} \newcommand{\expo}[1]{\,{\rm e}^{#1}\,} \newcommand{\fermi}{\,{\rm f}} \newcommand{\piso}[1]{\,\left\lfloor #1 \right\rfloor\,} \newcommand{\mitad}{{1 \over 2}} \newcommand{\ic}{{\rm i}} \newcommand{\iff}{\Longleftrightarrow} \newcommand{\imp}{\Longrightarrow} \newcommand{\isdiv}{\,\left.\a la derecha\vert\,} \newcommand{\cy}[1]{\left\vert #1\right\rangle} \newcommand{\ol}[1]{\overline{#1}} \newcommand{\pars}[1]{\left (\, nº 1 \,\right)} \newcommand{\partiald}[3][]{\frac{\partial^{#1} #2}{\parcial #3^{#1}}} \newcommand{\pp}{{\cal P}} \newcommand{\raíz}[2][]{\,\sqrt[#1]{\vphantom{\large Un}\,#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\, nº 1 \,\right\vert} \newcommand{\wt}[1]{\widetilde{#1}}$ $\ds{\sum_{k=0}^{n}{n \choose k}{m \choose k}:\ {\large ?}}$

${\large\tt\mbox{Hereafter, I'll illustrate a general method:}}$

\begin{align}&\color{#66f}{\large\sum_{k=0}^{n}{n \choose k}{m \choose k}} =\sum_{k=0}^{n}{n \choose k}\oint_{\verts{z}\ =\ 1} {\pars{1 + z}^{m} \over z^{k + 1}}\,{\dd z \over 2\pi\ic} =\oint_{\verts{z}\ =\ 1}{\pars{1 + z}^{m} \over z}\, \sum_{k=0}^{n}{n \choose k}\pars{1 \over z}^{k}\,{\dd z \over 2\pi\ic} \\[3mm]&=\oint_{\verts{z}\ =\ 1}{\pars{1 + z}^{m} \over z}\, \pars{1 + {1 \over z}}^{n}\,{\dd z \over 2\pi\ic} =\oint_{\verts{z}\ =\ 1}{\pars{1 + z}^{m + n} \over z^{n + 1}}\, \,{\dd z \over 2\pi\ic} = \color{#66f}{\large{m + n \choose n}} \end{align}

Answer 4

Edificio en robjohn la respuesta, para demostrar la Vandermonde identidad fijamos en el coeficiente de $x^n$ a ambos lados de la igualdad $$ (x+1)^n(x+1)^m = (x+1)^{m+n}. $$

Answer 5

Supongamos que queremos recoger $n$ de los niños de un grupo de $n$ niños y $m$ niñas. A continuación, podemos elegir el $n$ niños y $0$ de las niñas, o $n - 1$ niños y $1 $ chica, o $n - 2$ niños y $2$ niñas, ... Hay

$$\sum_{r = 0}^n\binom{n}{n - r}\binom{m}{r} = \sum_{r = 0}^n\binom{n}{r}\binom{m}{r}$$

maneras de hacer esto.

Pero también podemos ver como la elección de $n$ objetos a partir de un conjunto de $n + m$ objetos. Luego hay

$$\binom{n + m}{n}$$

maneras de hacer esto.

Ya que ambos cuentan con el mismo número de cosas, que debe ser igual, es decir,

$$\sum_{r = 0}^n\binom{n}{r}\binom{m}{r} = \binom{n + m}{n}$$