Suma de $k$ -combinación con repeticiones

Question

Puedo ver que hay $\binom{n+k-1}{k}$ casos de elección de k elementos de n tipos con repetición de http://en.wikipedia.org/wiki/Multiset_coefficient#Counting_multisets .

Me pregunto si existe alguna fórmula sobre su suma para variar $k$ . En particular, me interesa $\sum_{k=1}^{N} \binom{n+k-1}{k}$ .

¿Alguien tiene una idea, o un enlace sobre esto o algo similar a esto?

Actualización: He cambiado $nk$ a $N$ . En realidad $N = np$ para algún número entero positivo $p$ pero creo que no es necesario.

Answer 1

$\newcommand{\+}{^{\dagger}} \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{\down}{\downarrow} \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{\isdiv}{\,\left.\right\vert\,} \newcommand{\ket}[1]{\left\vert #1\right\rangle} \newcommand{\ol}[1]{\overline{#1}} \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} \newcommand{\wt}[1]{\widetilde{#1}}$ $\ds{\sum_{k = 1}^{N}{n + k - 1 \choose k}:\ {\large ?}}$

El binomio $\ds{{n + k - 1 \choose k}}$ es distinto de cero siempre que $\ds{0\ \leq\ k\ \leq\ n + k - 1\ \imp\ k \geq 0\,,\ n \geq 1}$ . A partir de ahora, supondremos que se cumplen esas condiciones.

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

Answer 2

El Identidad de Hockeystick establece que para los enteros positivos $n>r$ tenemos $\displaystyle\sum^n_{i=r}{i\choose r}={n+1\choose r+1}$ .

Consulte ese enlace para ver varias pruebas.

Así, $\displaystyle\sum_{k = 0}^{N}\dbinom{n+k-1}{k} = \displaystyle\sum_{k = 0}^{N}\dbinom{n+k-1}{n-1} \overset{i = n+k-1}{=}\displaystyle\sum_{i = n-1}^{n+N-1}\dbinom{i}{n-1} = \dbinom{n+N}{n}$ .

Resta $\dbinom{n+k-1}{0} = 1$ de ambos lados para obtener $\displaystyle\sum_{k = 1}^{N}\dbinom{n+k-1}{k} = \dbinom{n+N}{n}-1$ .

Answer 3

Esto se puede escribir como una suma telescópica (con $a = n-1$ )

$$\sum_{k=1}^{N} \binom{a+k}{k} = \sum_{k=1}^{N} \left(\binom{a+k+1}{k} - \binom{a+k}{k-1}\right)$$

lo que nos da la respuesta de ser

$$ \binom{a+N+1}{N} - \binom{a+N}{0} = \binom{n+N}{N} - 1$$