Otra identidad del palo de hockey

Question

Sé que esta pregunta ya se ha formulado antes y ha sido respondida aquí y aquí .

Tengo una formulación ligeramente diferente de la Identidad del Palo de Hockey y me gustaría que me ayudaran con un argumento combinatorio para demostrarla. En primer lugar tengo que demostrar esta afirmación: $$\sum_{i=0}^r\binom{n+i-1}{i}=\binom{n+r}{r}.$$ Aquí ya tengo una solución algebraica utilizando la Identidad de Pascal: $$\begin{align*} \binom{n+r}{r}&=\binom{n+r-1}{r}+\binom{n+r-1}{r-1}\\ &=\binom{n+r-1}{r}+\left[\binom{n+(r-1)-1}{(r-1)}+\binom{n+(r-1)-1}{r-2}\right]\\ &=\binom{n+r-1}{r}+\binom{n+(r-1)-1}{(r-1)}+\left[\binom{n+(r-2)-1}{r-2}+\binom{n+(r-2)-1}{(r-2)-1}\right]\\ &\,\,\,\vdots\\ &=\binom{n+r-1}{r}+\binom{n+(r-1)-1}{(r-1)}+\binom{n+(r-2)-1}{(r-2)-1}+\binom{n+(r-3)-1}{r-3}+\cdots+\left[\binom{n+1-1}{1}+\binom{n+1-1}{0}\right]\\ &=\binom{n+r-1}{r}+\binom{n+(r-1)-1}{(r-1)}+\binom{n+(r-2)-1}{(r-2)-1}+\binom{n+(r-3)-1}{r-3}+\cdots+\binom{n+1-1}{1}+\binom{n-1}{0}\\ &=\sum_{i=0}^r\binom{n+i-1}{i}. \end{align*}$$

He leído ambas pruebas combinatorias en las respuestas referenciadas más arriba, pero no consigo averiguar cómo alterar los argumentos combinatorios para que se adapten a mi formulación de la Identidad del Palo de Hockey. Básicamente, esta formulación da el "otro" palo de hockey. ¿Alguna idea?

Answer 1

Tenga en cuenta que $\binom{n+r}{r}=\binom{n+r}{n}$ es el número de subconjuntos de $\{1,2,\ldots,n+r\}$ de tamaño $n$ . Por otra parte, para $i=0,1,2,\ldots,r$ , $\binom{n+i-1}{i}=\binom{n+i-1}{n-1}$ es el número de subconjuntos de $\{1,2,\ldots,n+r\}$ de tamaño $n$ cuyo mayor elemento es $n+i$ .

Answer 2

Supongamos que la desigualdad diofantina $x_1 + x_2 + ... + x_n \le r$ tiene $A(n, r)$ soluciones enteras no negativas. (O uno tiene que molestar a lo sumo $r$ objetos en $n$ y esta tarea es posible en $A(n, r)$ maneras. Obsérvese que se distinguen los contenedores pero no se desea distinguir los objetos)

Calcularemos $A(n, r)$ de dos maneras.

$$x_1 + x_2 + ... + x_n \le r \\ \Rightarrow \exists x_{n+1} \in \mathbb{Z^+}\cup\{0\}: x_1 + x_2 + ... + x_n + x_{n+1} = r$$

Según problema de estrellas y barras ,

$$A(n, r) = \left(\!\!{n + 1 \choose r}\!\!\right) = {n + r \choose r} \qquad \mathcal{\color{navy}{(I)}}$$

De ahí que busquemos soluciones enteras (y $r$ también es un entero), por la regla de la suma, $A(n, r)$ sería la suma de soluciones enteras no negativas de estas ecuaciones:

$$x_1 + x_2 + \cdots + x_n = 0\\or\\ x_1 + x_2 + \cdots + x_n = 1\\or\\ x_1 + x_2 + \cdots + x_n = 2\\or\\ \vdots\\or\\ x_1 + x_2 + \cdots + x_n = r$$

Para todos $0 \le i \le r$ la ecuación $x_1 + x_2 + ... + x_n = i$ habría $\left(\!\!{n \choose i}\!\!\right) = {n + r - 1 \choose r}$ soluciones enteras no negativas. Por lo tanto,

$$A(n, r) = \sum_{i=0}^r\left(\!\!{n \choose i}\!\!\right) = \sum_{i=0}^r{n+i-1 \choose i} \qquad \mathcal{\color{navy}{(II)}} \\ {\color{navy}{(I)}}, {\color{navy}{(II)}} \Rightarrow {n + r \choose r} = \sum_{i=0}^r\left(\!\!{n \choose i}\!\!\right) = \sum_{i=0}^r{n+i-1 \choose i}$$