demostrando la identidad combinatoria -$\sum_{k=0}^m{n-k \choose m-k}={n+1 \choose m}$

Question

Demuestre que por cada$n \ge m \ge 1 , \sum_{k=0}^m{n-k \choose m-k}={n+1 \choose m}$

Intenté decir que el RHS representa el número de series binarias con m "1" yn + 1-m "0" 's, pero no pude averiguar qué k representa en el LHS. Gracias

Answer 1

Puede pensar en LHS como$$\sum_{k=0}^{m} \dbinom{n-k}{n-m}$$ hence, you count the number of binary series starting with exactly k "1"s. For example when $ k = 0$, the first term must be "0", which has $ \ dbinom {n} {nm}$ combinations, and when $ k = 1$ the number of binary series starting with exactly one "1" has $ \ dbinom {n- 1} {nm} $ combinaciones (ya que necesita que el segundo término en la secuencia sea "0"), y así sucesivamente.

Estos suman exactamente la cantidad de series binarias posibles con m "0" syn-m +1 "1" s como usted describió. Espero que esto ayude.

Answer 2

En una $(n+1-m)\times m$ cuadrícula, hay $n+1 \choose m$ rutas (Creo que de las opciones de cuando ir entre los $n+1$ binario opciones de Arriba y a la Derecha para llegar de a a B).

Deje $R_k$ indican las rutas hasta ese nodo, pero con una decisión de la Derecha girar a la siguiente. Cada ruta a $B$ incluye sólo uno de estos $R_0, R_1, \dots, $ o $R_m$ (ir a la derecha, el resto es) opciones.

Equivalentemente, denotan la Derecha por $0$, y $1$, por lo que se le suma las opciones con la cola $0, 01, 011, 0111, \dots,$ $01\dots 1$ agotar el $m$.

Answer 3

$$ \begin{align} \sum_{k=0}^m\binom{n-k}{m-k} &=\sum_{k=0}^m\binom{n-k}{n-m}\tag{1}\\ &=\binom{n+1}{n-m+1}\tag{2}\\[3pt] &=\binom{n+1}{m}\tag{3} \end {align} $$ Explicación:
$(1)$:$\binom{n}{k}=\binom{n}{n-k}$
$(2)$: Ecuación$(9)$ de esta respuesta
$(3)$:$\binom{n}{k}=\binom{n}{n-k}$

Answer 4

$\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{\dd}{\mathrm{d}} \newcommand{\ds}[1]{\displaystyle{#1}} \newcommand{\expo}[1]{\,\mathrm{e}^{#1}\,} \newcommand{\mitad}{{1 \over 2}} \newcommand{\ic}{\mathrm{i}} \newcommand{\iff}{\Leftrightarrow} \newcommand{\imp}{\Longrightarrow} \newcommand{\ol}[1]{\overline{#1}} \newcommand{\pars}[1]{\left (\, nº 1 \,\right)} \newcommand{\partiald}[3][]{\frac{\partial^{#1} #2}{\parcial #3^{#1}}} \newcommand{\raíz}[2][]{\,\sqrt[#1]{\, #2 \,}\,} \newcommand{\totald}[3][]{\frac{\mathrm{d}^{#1} #2}{\mathrm{d} #3^{#1}}} \newcommand{\verts}[1]{\left\vert\, nº 1 \,\right\vert}$

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