¿Alguien puede dar una combinatoria prueba de la identidad de ${n \choose m} + 2{n-1 \choose m}+3{n-2 \choose m}+...+(n-m+1){m \choose m}={n+2 \choose m+2}$

Question

¿Alguien puede dar una combinatoria prueba de la identidad

$${n \choose m} + 2{n-1 \choose m}+3{n-2 \choose m}+\ldots+(n+1-m){m \choose m}={n+2 \choose m+2}$$

Me estoy encontrando difícil como $n$ es variable en lugar de $m$

Answer 1

SUGERENCIA: Usted desea contar los subconjuntos de a $\{0,1,\ldots,n+1\}$ que $m+2$ elementos. Claramente hay $\binom{n+2}{m+2}$ de ellos. Sin embargo, también podemos contar en lotes de acuerdo con el segundo número más pequeño en el conjunto.

Cuántas $(m+2)$-elemento de subconjuntos de a $\{0,1,\ldots,n+1\}$ ha $k$ como segundo elemento más pequeño?

Answer 2

Deje $S$ ser el conjunto de todas las cadenas binarias de longitud $n+2$ que tienen exactamente $m+2$ $1$'s.

Queremos contar el número de elementos en $S$ en dos formas diferentes. Por un lado, sabemos que $|S|=\binom{n+2}{m+2}$.

Ahora, fix $1\leq i\leq n+1-m$. Deje $S_{i}$ ser el subconjunto de $S$, cuyas cadenas tienen un $1$ $(i+1)$'st entrada y exactamente un $1$ entre el primer $i$ entradas. Claramente hay $i$ formas para realizar una $1$ entre el primer $i$ las entradas de la cadena. Puesto que el $(i+1)$'st entrada debe ser un $1$, el resto de $m$ $1$'s será uno de los últimos $(n+2)-(i+1)=n+1-i$ entradas. Hay $\binom{n+1-i}{m}$ formas para realizar estos restante $1$'s. Por lo tanto, no se $|S_{i}|=i\cdot\binom{n+1-i}{m}$.

Ahora, tenga en cuenta que $S=\underset{1\leq i\leq n+1-m}{\bigcup}S_{i}$. Además, el $S_{i}$'s son todos distintos. ${\bf\it Why?}$

Por lo tanto, $$ \binom{n+2}{m+2}=|S|=\underset{1\leq i\leq n+1-m}{\sum}|S_{i}|=\underset{1\leq i\leq n+1-m}{\sum}\cdot\binom{n+1-i}{m}. $$

Answer 3

Una forma es a través de la inducción. Si $n = m$, luego tenemos

$$ \binom{n}{m} = \binom{n+2}{m+2} $$

lo cual es cierto, ya que ambos lados de la igualdad de $1$. Siguiente, supongamos que

$$ \binom{m+k}{m} + 2\binom{m+k-1}{m} + 3\binom{m+k-2}{m} + \cdots + (k+1)\binom{m}{m} = \binom{m+k+2}{m+2} $$

para algunos $k \geq 0$. Entonces, para $k+1$, el lado izquierdo es igual a

\begin{align} L & = \binom{m+k+1}{m} + 2\binom{m+k}{m} + 3\binom{m+k-1}{m} + \cdots + (k+2)\binom{m}{m} \\ & = \binom{m+k+1}{m} + \binom{m+k}{m} + \binom{m+k-1}{m} + \cdots + \binom{m}{m} + \binom{m+k+2}{m+2} \\ & = \binom{m+k+2}{m+1} + \binom{m+k+2}{m+2} \qquad \leftarrow \text{hockey-stick identity} \\ & = \binom{m+k+3}{m+2} \end{align}

que establece la proposición.

Answer 4

$$\begin{align} \sum_{r=1}^{n-m+1}r\binom {n-r+1}m &=\sum_{k=m}^n(n-k+1)\binom km &&\text{putting }k=n-r+1\\ &=\sum_{k=m}^n\sum_{j=k}^n\binom km\\ &=\sum_{j=m}^n\sum_{k=m}^j\binom km\\ &=\sum_{j=m}^n\binom {j+1}{m+1}\\ &=\binom {n+2}{m+2}\qquad\blacksquare\end{align}$$