Simplificación de la expresión combinatoria
He estado resolviendo un problema y me he quedado atascado durante horas.
No recuerdo ningún enfoque / fórmula combinatoria para la siguiente expresión:
$$\sum_{i=a+1}^n {i-1 \choose a}{n-i \choose k-a}$$
Se agradecería cualquier tipo de ayuda. Sé que es una norma compartir mi enfoque también para demostrar que me he esforzado, pero honestamente no tengo ni idea de esta pregunta en particular.
¡Gracias!
Respuestas
Lo que sigue, ciertamente, no es la prueba más simple. Publicamos aquí a modo de enriquecimiento y para mostrar cuatro técnicas, extractores de coeficientes, el corchete de Iverson, los residuos y la regla de Leibniz.
Buscamos mostrar que
$$\sum_{q=a+1}^n {q-1\choose a} {n-q\choose k-a} = {n\choose k+1}$$
dónde $k\ge a$ para que se defina el coeficiente binomial, y $n\ge a+1$ o alternativamente
$$\sum_{q=0}^{n-a-1} {q+a\choose a} {n-a-1-q\choose k-a} = {n\choose k+1}.$$
El LHS es
$$[z^{k-a}] (1+z)^{n-a-1} \sum_{q\ge 0} {q+a\choose a} (1+z)^{-q} [[q\le n-a-1]] \\ = [z^{k-a}] (1+z)^{n-a-1} \sum_{q\ge 0} {q+a\choose a} (1+z)^{-q} [w^{n-a-1}] \frac{w^q}{1-w} \\ = [z^{k-a}] (1+z)^{n-a-1} [w^{n-a-1}] \frac{1}{1-w} \sum_{q\ge 0} {q+a\choose a} (1+z)^{-q} w^q \\ = [z^{k-a}] (1+z)^{n-a-1} [w^{n-a-1}] \frac{1}{1-w} \frac{1}{(1-w/(1+z))^{a+1}} \\ = [z^{k-a}] (1+z)^{n} [w^{n-a-1}] \frac{1}{1-w} \frac{1}{(1+z-w)^{a+1}}.$$
Esto es
$$[z^{k-a}] (1+z)^n (-1)^a \mathrm{Res}_{w=0} \frac{1}{w^{n-a}} \frac{1}{w-1} \frac{1}{(w-(1+z))^{a+1}}.$$
Ahora el residuo en el infinito para $w$ es cero por inspección, los residuos suman cero y el residuo en $w=1$ rendimientos
$$[z^{k-a}] (1+z)^n (-1)^a \frac{1}{(-1)^{a+1} z^{a+1}} = - {n\choose k+1}.$$
Esta es la afirmación si podemos demostrar que la contribución del polo en $w=1+z$es cero. Obtenemos (regla de Leibniz)
$$\frac{1}{a!} \left(\frac{1}{w^{n-a}} \frac{1}{w-1}\right)^{(a)} = \frac{1}{a!} \sum_{q=0}^a {a\choose q} \frac{(-1)^q (n-1-a+q)!}{(n-1-a)! \times w^{n-a+q}} \frac{(-1)^{a-q} (a-q)!}{(w-1)^{a+1-q}} \\ = (-1)^a \sum_{q=0}^a {n-1-a+q\choose q} \frac{1}{w^{n-a+q}} \frac{1}{(w-1)^{a+1-q}}.$$
Así obtenemos por la contribución
$$[z^{k-a}] (1+z)^n \sum_{q=0}^a {n-1-a+q\choose q} \frac{1}{(1+z)^{n-a+q}} \frac{1}{z^{a+1-q}} \\ = \sum_{q=0}^a {n-1-a+q\choose q} [z^{k+1-q}] (1+z)^{a-q} = 0$$
porque $a\ge q$ y $k+1\gt a.$ Con esto concluye el argumento.
Obtenemos \ begin {align *} \ color {blue} {\ sum_ {i = a + 1} ^ n} & \ color {blue} {\ binom {i-1} {a} \ binom {ni} {ka }} \\ & = \ sum_ {i = a + 1} ^ n \ binom {i-1} {ia-1} \ binom {ni} {ni-k + a} \ tag {1} \\ & = \ sum_ {i = a + 1} ^ n \ binom {-a-1} {ia-1} (- 1) ^ {ia-1} \ binom {-k + a-1} {ni-k + a } (- 1) ^ {ni-k + a} \ etiqueta {2} \\ & = (- 1) ^ {nk-1} \ sum_ {i = 0} ^ {na-1} \ binom {-a -1} {i} \ binom {-k + a-1} {nk-1-i} \ etiqueta {3} \\ & = (- 1) ^ {nk-1} \ binom {-k-2} {nk-1} \ etiqueta {4} \\ & = \ binom {n} {nk-1} \ etiqueta {5} \\ & \, \, \ color {azul} {= \ binom {n} {k +1}} \ end {align *} y el reclamo sigue.
Comentario:
En (1) usamos $\binom{p}{q}=\binom{p}{p-q}$ dos veces.
En (2) aplicamos la identidad binomial $\binom{-p}{q}=\binom{p+q-1}{q}(-1)^q$.
En (3) cambiamos el índice para comenzar con $i=0$.
En (4) aplicamos el https://en.wikipedia.org/wiki/Vandermonde%27s_identity#Chu%E2%80%93Vandermonde_identity. Aquí usamos que el índice superior es de hecho$n-k-1$, ya que $k\geq a$.
En (5) aplicamos la identidad como lo hicimos en (2) nuevamente.
Considere palabras binarias de longitud $n$ con $k+1$ unos ... $ \binom{n}{k+1}$.
Deja el $(a+1)^{th}$ uno ocurre en el $i^{th}$posición. Existen$a$ unos en el $i-1$ posiciones antes de esta entrada ... $\binom{i-1}{a}$. Y aquí están$k-a$ unos en el $n-i$ posiciones después de ... $\binom{n-i}{k-a}$. Ahora$i$ puede variar sobre $a+1$ y $n$, entonces tenemos \ begin {eqnarray *} \ sum_ {i = a + 1} ^ n \ binom {i-1} {a} \ binom {ni} {ka} = \ binom {n} {k + 1} . \ end {eqnarray *}
Me interesaría ver una prueba algebríaca de esto.
Editar (a la luz de la respuesta de MS a continuación): Use el truco binomial negativo dos veces \ begin {eqnarray *} \ binom {-p} {q} = (- 1) ^ q \ binom {p + q-1} {q} . \ end {eqnarray *} Ahora se puede aplicar la identidad de Vandermonde, binomial negativo nuevamente y el resultado sigue.
Pista: prueba$\binom{n}{k+1}$esto es como Hockey Stick y Vandermonde juntos. Intente combinar cada una de sus descripciones combinatorias. Recuerda que la identidad del palo de hockey es como$\sum _{k=0}^n\binom{k}{\ell}=\binom{n+1}{\ell +1}$ y lo que hace es arreglar el elemento más grande y elegir el restante $k.$¡Aquí está eligiendo un elemento intermedio! (Llámalo$i$y recogiendo a la izquierda y a la derecha (como en Vandermonde)).
Pista no seria: he llamado a esta identidad: "Vandermonde jugando al hockey" en algún lugar antes.