¿Cuál es esta suma binomial?

Question

Estoy tratando de averiguar en qué consiste esta suma:$$\sum^n_{k=0}k \binom{m-k}{m-n}$ $

Creí que había n giros y en cada turno elegías 1 objeto de k objetos ($\binom{k}{1}=k$) y también elegías$m-n$ objetos de$m-k$ objetos. Así que pensé que seleccionamos un total de$m-n+1$ de objetos de$m-k+k=m$ de objetos, dando$$\sum^n_{k=0}k \binom{m-k}{m-n}=\binom{m}{m-n+1}$ $ Pero conecté algunos números de prueba y esto no pareció funcionar. ¿Qué estoy pensando mal?

Answer 1

Veamos un poco diferente. Supongamos que usted quiere elegir un conjunto de $m-n+2$ a los números del conjunto $A=\{0,1,\ldots,m\}$. Si $S$ es un juego, vamos a $k_S$ ser el segundo miembro más pequeño de $S$. A continuación, $S$ $1$ miembro más pequeño de $k_S$ $m-n$ de los miembros más grandes de $k_S$. Para un determinado $k$ hay $k$ maneras de escoger uno más pequeño miembro de el conjunto $A$ $\binom{m-k}{m-n}$ formas para recoger $m-n$ miembros más grandes de $A$, por lo que hay

$$k\binom{m-k}{m-n}$$

formas de elegir los $S$$k_S=k$. Recapitulación sobre los posibles valores de $k$ da el número total de subconjuntos, que es, por supuesto,

$$\binom{|A|}{m-n+2}=\binom{m+1}{m-n+2}\;.$$

El problema con su enfoque es que cuando se elige uno de los primeros a $k$ $m-n$ de la última $n-k$ elementos de $[m]$, no sólo de hacer una selección de $m-n+1$ elementos de $[m]$: está también la especificación de un punto de ruptura entre el primer y el último $m-n$.

Answer 2

He probado las siguientes cálculos : $$ \eqalign{ \sum_{k=0}^n k \binom{m-k}{m n} &= \sum_{k=0}^n (m+1-(m+1-k)) \binom{m-k}{m n} \cr &= \sum_{k=0}^n (m+1)\binom{m-k}{m n} - \sum_{k=0}^n (m+1-k) \binom{m-k}{m n} \cr &= \sum_{k=0}^n (m+1)\binom{m-k}{m n} - \sum_{k=0}^n (m-n+1) \binom{m-k+1}{m-n+1} \cr &= (m+1)\sum_{k=0}^n \binom{m-k}{m n} - (m-n+1) \sum_{k=0}^n \binom{m-k+1}{m-n+1} \cr } $$ Vamos $$ A=\sum_{k=0}^n \binom{m-k}{m n}\ \ \ y\ \ \ B=\sum_{k=0}^n \binom{m-k+1}{m-n+1} $$ Evaluamos primero $A$, $$ \eqalign{ A &= \sum_{0 \le k \le n} \binom{m-k}{m n} \cr &= \sum_{0 \le m-k \le n} \binom{m-(m-k)}{m n} \cr &= \sum_{-m \le-k \le -(m-n)} \binom{k}{m n} \cr &= \sum_{0 \le k \le m} \binom{k}{m n} \cr &= \binom{m+1}{m-n+1} \cr } $$ Cálculos similares para $B$ dar $$ \eqalign { B &= \binom{m+2}{m-n+2} \cr } $$ Para concluir, finalmente, que $$ \sum_{k=0}^n k \binom{m-k}{m n} = (m+1)\binom{m+1}{m-n+1} - (m-n+1)\binom{m+2}{m-n+2} $$

Answer 3

$$ \begin{align} \sum_{k=0}^n k\binom {m-k}{m-n} &=\sum_{k=0}^n \binom k1\binom {m-k}{m-n}\\ &=\sum_{k=0}^n\binom k{k-1}\binom {m-k}{n-k}\\ &=\sum_{k=0}^n(-1)^{k-1}\binom{-2}{k-1}(-1)^{n-k}\binom {-m+n-1}{n-k} && \text{(Upper negation)}\\ &=(-1)^{n-1}\sum_{k=0}^n\binom{-2}{k-1}\binom {-m+n-1}{n-k}\\ &=(-1)^{n-1}\binom {-m+n-3}{n-1}&& \text{(Vandermonde)}\\ &=(-1)^{n-1}(-1)^{n-1}\binom {m+1}{n-1} &&\text{(Upper negation)}\\ &=\binom {m+1}{n-1} =\binom {m+1}{m-n+2}\qquad\blacksquare \end {align} $$