Semplificazione dell'espressione combinatoria
Ho risolto un problema e ci sono rimasto bloccato per ore.
Non riesco a ricordare alcun approccio / formula combinatoria per la seguente espressione:
$$\sum_{i=a+1}^n {i-1 \choose a}{n-i \choose k-a}$$
Qualsiasi tipo di aiuto sarebbe apprezzato. So che è una norma condividere anche il mio approccio per dimostrare che ho fatto uno sforzo, ma onestamente non ho idea di questa particolare domanda.
Grazie!
Risposte
Quella che segue non è certo la prova più semplice. Pubblichiamo qui a titolo di arricchimento e per mostrare quattro tecniche, estrattori di coefficienti, la staffa di Iverson, i residui e la regola di Leibniz.
Cerchiamo di dimostrarlo
$$\sum_{q=a+1}^n {q-1\choose a} {n-q\choose k-a} = {n\choose k+1}$$
dove $k\ge a$ per definire il coefficiente binomiale e $n\ge a+1$ o in alternativa
$$\sum_{q=0}^{n-a-1} {q+a\choose a} {n-a-1-q\choose k-a} = {n\choose k+1}.$$
L'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}}.$$
Questo è
$$[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}}.$$
Ora il residuo all'infinito per $w$ è zero per controllo, la somma dei residui è zero e il residuo è uguale a $w=1$ rendimenti
$$[z^{k-a}] (1+z)^n (-1)^a \frac{1}{(-1)^{a+1} z^{a+1}} = - {n\choose k+1}.$$
Questa è l'affermazione se possiamo dimostrare che il contributo del polo a $w=1+z$è zero. Otteniamo (regola di 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}}.$$
Otteniamo così il contributo
$$[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$$
perché $a\ge q$ e $k+1\gt a.$ Questo conclude l'argomento.
Otteniamo \ 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 la dichiarazione segue.
Commento:
In (1) usiamo $\binom{p}{q}=\binom{p}{p-q}$ due volte.
In (2) applichiamo l'identità binomiale $\binom{-p}{q}=\binom{p+q-1}{q}(-1)^q$.
In (3) spostiamo l'indice per iniziare $i=0$.
In (4) applichiamo il https://en.wikipedia.org/wiki/Vandermonde%27s_identity#Chu%E2%80%93Vandermonde_identity. Qui usiamo che l'indice superiore è in effetti$n-k-1$, da $k\geq a$.
In (5) applichiamo l'identità come abbiamo fatto di nuovo in (2).
Considera parole binarie di lunghezza $n$ con $k+1$ quelli ... $ \binom{n}{k+1}$.
Lascia il $(a+1)^{th}$ uno si verifica presso il $i^{th}$posizione. Ci sono$a$ quelli nel $i-1$ posizioni prima di questa voce ... $\binom{i-1}{a}$. E ci sono$k-a$ quelli nel $n-i$ posizioni dopo ... $\binom{n-i}{k-a}$. Adesso$i$ può variare $a+1$ e $n$, quindi abbiamo \ begin {eqnarray *} \ sum_ {i = a + 1} ^ n \ binom {i-1} {a} \ binom {ni} {ka} = \ binom {n} {k + 1} . \ end {eqnarray *}
Sarei interessato a vedere una prova algebrica di ciò.
Modifica (alla luce della risposta di MS di seguito): usa due volte il trucco binomiale negativo \ begin {eqnarray *} \ binom {-p} {q} = (- 1) ^ q \ binom {p + q-1} {q} . \ end {eqnarray *} L'identità di Vandermonde può ora essere applicata, nuovamente binomiale negativo e il risultato segue.
Suggerimento: prova$\binom{n}{k+1}$questo è come Hockey Stick e Vandermonde insieme. Prova a combinare ciascuna delle loro descrizioni combinatorie. Ricorda che l'identità della mazza da hockey è simile$\sum _{k=0}^n\binom{k}{\ell}=\binom{n+1}{\ell +1}$ e quello che fa è aggiustare l'elemento più grande e scegliere il restante $k.$Qui stai scegliendo un elemento intermedio! (Chiamalo$i$e il picking a sinistra ea destra (come su Vandermonde)).
Indizio non serio: ho già chiamato questa identità: "Vandermonde che gioca a Hockey" da qualche parte.