Argumento combinatorio para una identidad

Question

Considera la siguiente ecuación:

$x_1 + x_2 + \cdots + x_r = n,$ donde $0\leq x_{i}\leq n, \forall i$

El número de soluciones integrales de la ecuación anterior = ${n+r-1 \choose r-1}$ .

Considere el siguiente resultado:

$\Sigma_{n=0}^{N} {n+r-1\choose r-1} = {N+r \choose r}$

El resultado anterior se puede demostrar utilizando la inducción. ¿Existe una forma algebraica de demostrar el resultado anterior? Más importante aún, ¿existe un "argumento combinatorio" intuitivo que justifique el resultado anterior?

Answer 1

En cuanto a su segunda pregunta, $\binom{N+r}{r}$ es el número de resultados de la selección de $r$ enteros de $\{1,2,\ldots,N+r\}$ . Supongamos que queremos organizar estos resultados por el número entero máximo seleccionado. Para contar el número de resultados cuyo número entero máximo es $n+r$ entonces tenemos que seleccionar $r-1$ otros enteros de $\{1,\ldots, n+r-1\}$ , por lo que hay $\binom{n+r-1}{r-1}$ tales resultados. Sumando sobre todos los máximos posibles $r,r+1,\ldots,N+r$ tenemos $\sum_{n=0}^N \binom{n+r-1}{r-1}$ .

---

Para ver la conexión con tu primera pregunta, consulta la pista de Johannes. Para contar todas las formas posibles de satisfacer $x_1+\cdots+x_r=n$ Puede organizarlos de las siguientes maneras $x_1+\cdots+x_{r-1} \le n$ .

Answer 2

Tenemos $N+r$ diferentes rosquillas alineadas en una fila. ¿De cuántas maneras podemos elegir $r$ de ellos para el desayuno? Lo contamos de dos maneras diferentes.

La forma simple da $\binom{N+r}{r}$ . Ahora contamos de forma más complicada.

Supongamos que el $r$ -El quinto donut es el que se elige más a la derecha. Entonces hay $\binom{0+r-1}{r-1}$ formas de elegir el resto $r-1$ rosquillas.

Supongamos que el $(1+r)$ -El quinto donut es el que se elige más a la derecha. Entonces hay $\binom{1+r-1}{r-1}$ formas de elegir el resto $r-1$ rosquillas.

Supongamos que el $(2+r)$ -El quinto donut es el que se elige más a la derecha. Entonces hay $\binom{2+r-1}{r-1}$ formas de elegir el resto $r-1$ rosquillas.

Y así sucesivamente. Finalmente, si el $(N+r)$ -el donut más elegido es el de la derecha, hay $\binom{N+r-1}{r-1}$ para elegir el resto de $r-1$ rosquillas.

Sume.

Answer 3

Has preguntado por una prueba algebraica. Considere la identidad $$(1+x)^{-1} \cdot (1+x)^{-r} = (1+x)^{-r-1}$$ Expandir todo por el Teorema del Binomio para exponentes negativos: $$\sum_{i=0}^{\infty} x^i \cdot \sum_{n=0}^{\infty} \binom{r+n-1}{r-1} x^n= \sum_{N=0}^{\infty} \binom{r+N}{r} x^N$$ El coeficiente de $x^N$ en el lado izquierdo es $\sum_{n=0}^N \binom{r+n-1}{r-1}$ el coeficiente del lado derecho es $\binom{r+N}{r}$ .