Combinatoria prueba de coeficiente binomial suma.

Question

Deje $n$ $k$ ser enteros con $1 \leq k \leq n$. Demostrar que:

$$\sum_{k=1}^n {n \choose k}{n \choose k-1} = \frac12{2n+2 \choose n+1} - {2n \choose n}$$

Me dijeron que esto se supone que el uso de una combinatoria de prueba y mientras yo no estoy cómodo con eso, muchas de las pruebas semejantes uso de una prueba matemática que muestra la igualdad. Cualquier orientación sería muy apreciada.

Answer 1

Utilizando el estándar binomio identidades, esto puede ser demostrado de la siguiente manera: $$ \begin{align} \sum_{k=1}^n \binom{n}{k}\binom{n}{k-1}&=\sum_{k=1}^n \binom{n}{n-k}\binom{n}{k-1}\\ &=\binom{2n}{n-1}\\ &=\binom{2n+1}{n}-\binom{2n}{n}\\ &=\frac{n+1}{2n+2}\binom{2n+2}{n+1}-\binom{2n}{n}\\ &=\frac{1}{2}\binom{2n+2}{n+1}-\binom{2n}{n} \end{align} $$ Cada identidad se puede dar una simple combinatoria justificación.

1. $$ \binom{n}{k}=\binom{n}{n-k} $$ El número de formas de elegir los $k$ elementos de $n$ es el número de formas de elegir el complemento de un conjunto de $k$ elementos de $n$.

2. $$ \sum_{k=1}^n \binom{n}{n-k}\binom{n}{k-1}=\binom{2n}{n-1} $$ Dado un conjunto de mármoles verdes, numeradas $1...n$ y canicas rojas numeradas $1...n$, el recuento de las elecciones de $n-1$ mármoles de el total $2n$ contando las opciones de $n-k$ mármoles verdes y $k-1$ canicas rojas.

3. $$ \binom{2n}{n-1}+\binom{2n}{n}=\binom{2n+1}{n} $$ Dado un conjunto de mármol verde numerado $1...2n$ $1$ mármol rojo, una selección de $n$ mármoles de el total $2n+1$ tiene el mármol rojo, y por lo tanto $n-1$ de la $2n$ mármoles verdes, o no tiene el mármol rojo, y por lo tanto $n$ de la $2n$ mármoles verdes.

4. $$ (2n+2)\binom{2n+1}{n}=(n+1)\binom{2n+2}{n+1} $$ Poner a $n+1$ canicas de una bolsa de $2n+2$ a un cuadro y, a continuación, eligiendo $1$ de la caja es la misma como la elección de $1$ de la bolsa de $2n+2$ mármoles y, a continuación, poner $n$ restante de los $2n+1$ canicas en el cuadro.

Answer 2

Sugerencia: Utilice $\displaystyle {n \choose k} = {n \choose n-k}$ e intentar contar algo que es igual a $\displaystyle {n \choose n-k}{n \choose k-1}$

Answer 3

Esta identidad puede ser interpretado como el conteo de rutas en $\Bbb Z^2$, cada paso sea un hasta $(+1,+1)$ o un desplegable $(+1,-1)$.

La primera observación es que el $\binom{2n+2}{n+1}$ cuenta el número total de rutas de$(0,0)$$(2n+2,0)$. De hecho, en un camino de $n+1$ hastas y $n+1$ abajos, y sólo hay que especificar que los pasos entre las $2n+2$ hastas. Del mismo modo $\binom{2n}{n}$ es el número de caminos de $(2,0)$ $(2n+2,0)$y ahora es fácil ver que $\frac12{2n+2 \choose n+1} - {2n \choose n}$ es en realidad el número de caminos de $(0,0)$ $(2n+2,0)$que empezar con dos hasta los pasos.

Desde el primero de dos pasos, que son fijos, sólo necesitamos considerar la última $2n$ entre $(2,2)$$(2n+2,0)$. El número de rutas con $k$ abajos en la primera $n$ $k'$ hastas en los últimos$n$$\binom{n}{k}\binom{n}{k'}$. Por otra parte, los números de $k$ $k'$ están limitados por la condición para llegar a $(2n+2,0)$, $2 + (n-k) - k -(n-k') + k' = 0$ o, equivalentemente,$k'=k-1$. Sumando sobre todos los posibles valores de $k$ obtenemos la fórmula deseada $$ \frac12{2n+2 \elegir n+1} - {2n \elegir n} = \sum_{k=1}^n \binom{n}{k}\binom{n}{k-1}. $$

Answer 4

$\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}}$ \begin{align}&\color{#66f}{\large\sum_{k = 1}^{n}{n \choose k}{n \choose k - 1}} =\sum_{k = 1}^{n}{n \choose k}\ \overbrace{\oint_{\verts{z}\ =\ 1}{\pars{1 + z}^{n} \over z^{k}} \,{\dd z \over 2\pi\ic}}^{\ds{n \choose k - 1}} \\[3mm]&=\oint_{\verts{z}\ =\ 1}\pars{1 + z}^{n} \sum_{k = 1}^{n}{n \choose k}\pars{1 \over z}^{k}\,{\dd z \over 2\pi\ic} =\oint_{\verts{z}\ =\ 1}\pars{1 + z}^{n} \bracks{\pars{1 + {1 \over z}}^{n} - 1}\,{\dd z \over 2\pi\ic} \\[3mm]&=\oint_{\verts{z}\ =\ 1}\pars{1 + z}^{n}\, \bracks{{\pars{1 + z}^{n} \over z^{n}} - 1}\,{\dd z \over 2\pi\ic} \\[3mm]&=\underbrace{\oint_{\verts{z}\ =\ 1}% {\pars{1 + z}^{2n} \over z^{n}}\,{\dd z \over 2\pi\ic}}_{\ds{2n \choose n - 1}}\ -\ \underbrace{\oint_{\verts{z}\ =\ 1}\pars{1 + z}^{n}\,{\dd z \over 2\pi\ic}} _{\ds{=\ 0}} ={2n \choose n - 1} \\[5mm]&=\color{#66f}{\large\half\,{2n + 2 \choose n + 1} - {2n \choose n}} \end{align}

Tenga en cuenta que \begin{align}\color{#c00000}{\half\,{2n + 2 \choose n + 1} - {2n \choose n}}&= \half\,{\pars{2n + 2}! \over \pars{n + 1}!\pars{n + 1}!} -{\pars{2n}! \over n!\,n!} ={\pars{2n + 2}! - 2\pars{n + 1}^{2}\pars{2n}!\over 2\bracks{\pars{n + 1}!}^{2}} \\[3mm]&={2\pars{n + 1}\pars{2n + 1}\pars{2n}! - 2\pars{n + 1}^{2}\pars{2n}!\over 2\pars{n + 1}n\pars{n - 1}!\pars{n + 1}!} \\[3mm]&={\pars{n + 1}\pars{2n + 1} - \pars{n + 1}^{2} \over \pars{n + 1}n}\, {\pars{2n}! \over \pars{n - 1}!\pars{n + 1}!} \\[3mm]&={\pars{n + 1}\bracks{\pars{2n + 1} - \pars{n + 1}} \over \pars{n + 1}n}\, {2n \choose n - 1} = \color{#c00000}{{2n \choose n - 1}} \end{align}