Simplificação da Expressão Combinatória
Tenho resolvido um problema e estou preso nele há horas.
Não consigo me lembrar de nenhuma abordagem / fórmula combinatória para a expressão abaixo:
$$\sum_{i=a+1}^n {i-1 \choose a}{n-i \choose k-a}$$
Qualquer tipo de ajuda seria apreciada. Eu sei que é uma norma compartilhar minha abordagem também para mostrar que fiz um esforço, mas, honestamente, não tenho nenhuma pista sobre essa questão em particular.
Obrigado!
Respostas
O que se segue não é reconhecidamente a prova mais simples. Postamos aqui a título de enriquecimento e para mostrar quatro técnicas, extratores de coeficientes, o braquete de Iverson, resíduos e a regra de Leibniz.
Procuramos mostrar que
$$\sum_{q=a+1}^n {q-1\choose a} {n-q\choose k-a} = {n\choose k+1}$$
Onde $k\ge a$ para o coeficiente binomial a ser definido, e $n\ge a+1$ ou alternativamente
$$\sum_{q=0}^{n-a-1} {q+a\choose a} {n-a-1-q\choose k-a} = {n\choose k+1}.$$
O LHS é
$$[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}}.$$
Isto é
$$[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}}.$$
Agora, o resíduo no infinito para $w$ é zero por inspeção, os resíduos somam zero e o resíduo em $w=1$ rendimentos
$$[z^{k-a}] (1+z)^n (-1)^a \frac{1}{(-1)^{a+1} z^{a+1}} = - {n\choose k+1}.$$
Esta é a afirmação se pudermos mostrar que a contribuição do pólo em $w=1+z$é zero. Nós entendemos (regra 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}}.$$
Obtemos assim pela contribuição
$$[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$ e $k+1\gt a.$ Isso conclui o argumento.
Obtemos \ 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} \ tag {2} \\ & = (- 1) ^ {nk-1} \ sum_ {i = 0} ^ {na-1} \ binom {-a -1} {i} \ binom {-k + a-1} {nk-1-i} \ tag {3} \\ & = (- 1) ^ {nk-1} \ binom {-k-2} {nk-1} \ tag {4} \\ & = \ binom {n} {nk-1} \ tag {5} \\ & \, \, \ color {blue} {= \ binom {n} {k +1}} \ end {align *} e a reivindicação segue.
Comente:
Em (1) usamos $\binom{p}{q}=\binom{p}{p-q}$ duas vezes.
Em (2), aplicamos a identidade binomial $\binom{-p}{q}=\binom{p+q-1}{q}(-1)^q$.
Em (3), mudamos o índice para começar com $i=0$.
Em (4), aplicamos o https://en.wikipedia.org/wiki/Vandermonde%27s_identity#Chu%E2%80%93Vandermonde_identity. Aqui usamos que o índice superior é de fato$n-k-1$, Desde a $k\geq a$.
Em (5), aplicamos a identidade como fizemos em (2) novamente.
Considere palavras binárias de comprimento $n$ com $k+1$ uns ... $ \binom{n}{k+1}$.
Deixe o $(a+1)^{th}$ um ocorre no $i^{th}$posição. tem$a$ uns no $i-1$ posições antes desta entrada ... $\binom{i-1}{a}$. E há$k-a$ uns no $n-i$ posições depois ... $\binom{n-i}{k-a}$. Agora$i$ pode variar $a+1$ e $n$, portanto, temos \ begin {eqnarray *} \ sum_ {i = a + 1} ^ n \ binom {i-1} {a} \ binom {ni} {ka} = \ binom {n} {k + 1} . \ end {eqnarray *}
Eu estaria interessado em ver uma prova algebríaca disso.
Editar (à luz da resposta de MS abaixo): Use o truque binomial negativo duas vezes \ begin {eqnarray *} \ binom {-p} {q} = (- 1) ^ q \ binom {p + q-1} {q} . \ end {eqnarray *} A identidade Vandermonde agora pode ser aplicada, binomial negativo novamente e o resultado segue.
Dica: Experimente$\binom{n}{k+1}$isso é como Hockey Stick e Vandermonde juntos. Tente combinar cada uma de suas descrições combinatórias. Lembre-se de que a identidade do Hockey Stick é como$\sum _{k=0}^n\binom{k}{\ell}=\binom{n+1}{\ell +1}$ e o que ele faz é corrigir o maior elemento e escolher o restante $k.$Aqui você está escolhendo um elemento do meio! (Chame-o$i$e escolhendo à esquerda e à direita (como em Vandermonde)).
Dica não séria: já chamei essa identidade de "Vandermonde jogando hóquei" em algum lugar antes.