Demostrando que ${x +y+n- 1 \choose n}= \sum_{k=0}^n{x+n-k-1 \choose n-k}{y+k-1 \choose k} $

Question

Cómo puedo probar que $${x +y+n- 1 \choose n}= \sum_{k=0}^n{x+n-k-1 \choose n-k}{y+k-1 \choose k} $$

He intentado lo siguiente:

Utilizamos la caída factorial de alimentación: $$y^{\underline k}=\underbrace{y(y-1)(y-2)\ldots(y-k+1)}_{k\text{ factors}},$$ de modo que $\binom{y}k=\frac{y^{\underline k}}{k!} .$

Entonces

$${x +y+n - 1 \elegir n} = \frac{(x +y+n - 1)!}{n! ((x +y+n - 1) - n)!} = \frac{1}{n!}. (x +y+n \color{#f00}{-1})^{\underline n} $$

Y

$$ {x+n-k-1 \choose n-k}{y+k-1 \choose k}$$ $$\frac{1}{(n-k)!}.(x+n-k-1)^{\underline{n-k}}.\frac{1}{k!}.(y+k-1)^{\underline{k}}$$ $$\frac{1}{k!.(n-k)!}.(x+n-k-1)^{\underline{n-k}}.(y+k-1)^{\underline{k}}$$ $$\sum_{k=0}^n{n \choose k}(x+n-k-1)^{\underline{n-k}}.(y+k-1)^{\underline{k}}$$

De acuerdo con el Binomio-coeficientes:

$$ ((x+n-k-1) + (y+k-1))^{\underline{n}}$$ $$ (x+y+n\color{#f00}{- 2})^{\underline{n}}$$

Lo que está mal ? y ¿Cómo puedo seguir? :/

Answer 1

El uso Negativo de los Coeficientes Binomiales y de Vandermonde de la Identidad, obtenemos $$ \begin{align} \sum_{k=0}^n\binom{x+n-k-1}{n-k}\binom{y+k-1}{k} &=\sum_{k=0}^n(-1)^{n-k}\binom{-x}{n-k}(-1)^k\binom{-y}{k}\tag{1}\\ &=(-1)^n\sum_{k=0}^n\binom{-x}{n-k}\binom{-y}{k}\tag{2}\\ &=(-1)^n\binom{-x-y}{n}\tag{3}\\ &=\binom{n+x+y-1}{n}\tag{4} \end{align} $$ Explicación:
$(1)$: Binomial negativa Coeficiente de conversión
$(2)$: álgebra
$(3)$: Vandermonde la Identidad de
$(4)$: Binomial negativa Coeficiente de conversión

Answer 2

Sugerencia: La fórmula binominal con el producto de Cauchy \begin{align*} (x+y)^n=\sum_{k=0}^n\binom{n}{k}x^ky^{n-k} \end{align*} no utilice la caída factoriales $x^{\underline{k}}$ resp. $y^{\underline{n-k}}$.

Aquí hay un paso a paso de respuesta similar a la de @MarkoRiedel. Es conveniente usar el coeficiente de operador $[z^k]$ para denotar el coeficiente de $z^k$ en una serie. De esta manera podemos escribir por ejemplo \begin{align*} \binom{n}{k}=[z^k](1+z)^n \end{align*}

Obtenemos

\begin{align*} \sum_{k=0}^{n}&\binom{x-1+n-k}{n-k}\binom{y-1+k}{k}\\ &=\sum_{k=0}^{\infty}\binom{x-1+n-k}{n-k}\binom{-y}{k}(-1)^k\tag{1}\\ &=\sum_{k=0}^\infty [t^{n-k}](1+t)^{x-1+n-k}[z^k](1+z)^{-y}(-1)^k\tag{2}\\ &=[t^n](1+t)^{x-1+n}\sum_{k=0}^\infty(-1)^kt^k(1+t)^{-k}[z^k](1+z)^{-y}\tag{3}\\ &=[t^n](1+t)^{x-1+n}\sum_{k=0}^\infty\left(-\frac{t}{1+t}\right)^k[z^k](1+z)^{-y}\\ &=[t^n](1+t)^{x-1+n}\left(1-\frac{t}{1+t}\right)^{-y}\tag{4}\\ &=[t^n](1+t)^{x+y-1+n}\tag{5}\\ &=\binom{x+y-1+n}{n} \end{align*} y el reclamo de la siguiente manera.

Comentario:

• En (1) utilizamos el binomio identidad $\binom{-p}{q}(-1)^q=\binom{p+q-1}{q}$ y se amplía el límite superior de la serie a $\infty$ sin cambiar nada, ya que estamos añadiendo ceros sólo.

• En (2) se aplica el coeficiente de operador dos veces.

• En (3) vamos a hacer algunos reordenamientos mediante el uso de la linealidad del coeficiente de operador y también utilizamos la regla \begin{align*} [z^{p-q}]A(z)=[z^p]z^{q}A(z) \end{align*}

• En (4) aplicamos la regla de sustitución \begin{align*} A(t)=\sum_{k=0}^\infty a_kt^k=\sum_{k=0}^\infty t^k[z^k]A(z)\\ \end{align*} con $z=-\frac{t}{1+t}$.

• En (5) vamos a hacer algunas simplificaciones.

• En (6) seleccionamos el coeficiente de $t^n$.

Answer 3

Tenemos $$\sum_{k=0}^n {y-1+k\choose k} {x-1+n-k\choose n-k} = \sum_{k=0}^n [z^{k}] \frac{1}{(1-z)^y} [z^{n-k}] \frac{1}{(1-z)^x} \\ = [z^n] \frac{1}{(1-z)^y} \frac{1}{(1-z)^x} = [z^n] \frac{1}{(1-z)^{x+y}} ={x+y-1+n\choose n}.$$

Answer 4

$\newcommand{\ángulos}[1]{\left\langle\,{#1}\,\right\rangle} \newcommand{\llaves}[1]{\left\lbrace\,{#1}\,\right\rbrace} \newcommand{\bracks}[1]{\left\lbrack\,{#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}{\Longleftrightarrow} \newcommand{\imp}{\Longrightarrow} \newcommand{\Li}[1]{\,\mathrm{Li}_{#1}} \newcommand{\ol}[1]{\overline{#1}} \newcommand{\pars}[1]{\left(\,{#1}\,\right)} \newcommand{\partiald}[3][]{\frac{\partial^{#1} #2}{\parcial #3^{#1}}} \newcommand{\ul}[1]{\underline{#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\,{#1}\,\right\vert}$

De ahora en adelante, voy a utilizar las identidades: $$ \left\lbrace\begin{array}{rcl} \ds{a \choose b} & \ds{=} & \ds{{-a + b - 1 \choose b}\pars{-1}^{b} \,,\quad b \in \mathbb{Z}} \\[5mm] \ds{a \choose b} & \ds{=} & \ds{\oint_{\verts{z} = 1^{-}}{\pars{1 + z}^{a} \over z^{b + 1}} \,{\dd z \over 2\pi\ic}\,,\quad b \in \mathbb{Z}} \\[5mm] \ds{\pars{1 + z}^{a}} & \ds{=} & \ds{\sum_{b = 0}^{\infty}{a \choose b}z^{b}\,, \quad\verts{z} < 1} \end{array}\right. $$

\begin{align} &\color{#f00}{\sum_{k = 0}^{n}{x + n - k - 1 \choose n - k} {y + k - 1 \choose k}} = \sum_{k = 0}^{\infty}\bracks{{-x \choose n - k}\pars{-1}^{n - k}} \bracks{{-y \choose k}\pars{-1}^{k}} \\[5mm] = & \pars{-1}^{n}\sum_{k = 0}^{n}{-y \choose k}\oint_{\verts{z} = 1^{-}} {\pars{1 + z}^{-x} \over z^{n - k + 1}}\,{\dd z \over 2\pi\ic} = \pars{-1}^{n}\oint_{\verts{z} = 1^{-}} {\pars{1 + z}^{-x} \over z^{n + 1}}\sum_{k = 0}^{\infty}{-y \choose k}z^{k}\,{\dd z \over 2\pi\ic} \\[5mm] = &\ \pars{-1}^{n}\oint_{\verts{z} = 1^{-}} {\pars{1 + z}^{-x - y} \over z^{n + 1}}\,{\dd z \over 2\pi\ic} = \pars{-1}^{n}{-x - y \choose n} = \pars{-1}^{n}{x + y + n - 1 \choose n}\pars{-1}^{n} \\[5mm] = &\ \color{#f00}{{x + y + n - 1 \choose n}} \end{align}

Answer 5

El conjunto múltiple de los números de $(\!\tbinom{m}{r}\!)=\binom{m+r-1}{r}$ recuento de la multisets de cardinalidad $r$ con elementos tomados de un conjunto de tamaño $m$. Utilizando el conjunto múltiple de los números, la identidad se convierte en:

$$\left(\!\tbinom{x+y}{n}\!\right)=\sum_{k=0}^n \left(\!\tbinom{x}{n-k}\!\right) \left(\!\tbinom{y}{k}\!\right)$$

Esto tiene más o menos la misma combinatoria interpretación como la Vandermonde de convolución de la identidad de los coeficientes binomiales. Cualquier $n$-conjunto múltiple construido a partir de la unión de dos conjuntos de tamaños de $x$ $y$ es únicamente una unión de un $(n-k)$-conjunto múltiple construido a partir del conjunto de tamaño $x$ $k$- conjunto múltiple construido a partir del conjunto de tamaño $y$ algunos $0\le k\le n$.