Vereinfachung der kombinatorischen Expression
Ich habe ein Problem gelöst und bin jetzt seit Stunden daran festgehalten.
Ich kann mich an keinen kombinatorischen Ansatz / keine kombinatorische Formel für den folgenden Ausdruck erinnern:
$$\sum_{i=a+1}^n {i-1 \choose a}{n-i \choose k-a}$$
Jede Art von Hilfe wäre dankbar. Ich weiß, dass es eine Norm ist, auch meinen Ansatz zu teilen, um zu zeigen, dass ich mich bemüht habe, aber ehrlich gesagt habe ich keine Ahnung von dieser speziellen Frage.
Vielen Dank!
Antworten
Was folgt, ist zugegebenermaßen nicht der einfachste Beweis. Wir veröffentlichen hier zur Anreicherung und zur Präsentation von vier Techniken, Koeffizientenextraktoren, der Iverson-Klammer, Rückständen und der Leibniz-Regel.
Das wollen wir zeigen
$$\sum_{q=a+1}^n {q-1\choose a} {n-q\choose k-a} = {n\choose k+1}$$
wo $k\ge a$ für den zu definierenden Binomialkoeffizienten und $n\ge a+1$ oder alternativ
$$\sum_{q=0}^{n-a-1} {q+a\choose a} {n-a-1-q\choose k-a} = {n\choose k+1}.$$
Die LHS ist
$$[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}}.$$
Das ist
$$[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}}.$$
Nun der Rückstand im Unendlichen für $w$ ist Null durch Inspektion, Rückstände summieren sich zu Null und der Rückstand bei $w=1$ ergibt
$$[z^{k-a}] (1+z)^n (-1)^a \frac{1}{(-1)^{a+1} z^{a+1}} = - {n\choose k+1}.$$
Dies ist die Behauptung, wenn wir zeigen können, dass der Beitrag von der Stange bei $w=1+z$ist Null. Wir bekommen (Leibniz-Regel)
$$\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}}.$$
Wir erhalten also für den Beitrag
$$[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$$
da $a\ge q$ und $k+1\gt a.$ Damit ist das Argument abgeschlossen.
Wir erhalten \ 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 *} und die Behauptung folgt.
Kommentar:
In (1) verwenden wir $\binom{p}{q}=\binom{p}{p-q}$ zweimal.
In (2) wenden wir die Binomialidentität an $\binom{-p}{q}=\binom{p+q-1}{q}(-1)^q$.
In (3) verschieben wir zunächst den Index $i=0$.
In (4) wenden wir die https://en.wikipedia.org/wiki/Vandermonde%27s_identity#Chu%E2%80%93Vandermonde_identity. Hier verwenden wir, dass der obere Index tatsächlich ist$n-k-1$, schon seit $k\geq a$.
In (5) wenden wir die Identität wie in (2) erneut an.
Betrachten Sie binäre Wörter der Länge $n$ mit $k+1$ Einsen ... $ \binom{n}{k+1}$.
Lasst den $(a+1)^{th}$ man tritt am auf $i^{th}$Position. Es gibt$a$ diejenigen in der $i-1$ Positionen vor diesem Eintrag ... $\binom{i-1}{a}$. Und da sind$k-a$ diejenigen in der $n-i$ Positionen nach ... $\binom{n-i}{k-a}$. Jetzt$i$ kann variieren über $a+1$ und $n$, also haben wir \ begin {eqnarray *} \ sum_ {i = a + 1} ^ n \ binom {i-1} {a} \ binom {ni} {ka} = \ binom {n} {k + 1} . \ end {eqnarray *}
Es würde mich interessieren, einen algebrischen Beweis dafür zu sehen.
Bearbeiten (In Anbetracht der Antwort von MS unten): Verwenden Sie den negativen Binomialtrick zweimal \ begin {eqnarray *} \ binom {-p} {q} = (- 1) ^ q \ binom {p + q-1} {q} . \ end {eqnarray *} Die Vandermonde-Identität kann jetzt angewendet werden, wieder ein negatives Binomial und das Ergebnis folgt.
Hinweis: Versuchen Sie es$\binom{n}{k+1}$Das ist wie Hockey Stick und Vandermonde zusammen. Versuchen Sie, jede ihrer kombinatorischen Beschreibungen zu kombinieren. Denken Sie daran, dass die Identität des Hockeyschlägers so ist$\sum _{k=0}^n\binom{k}{\ell}=\binom{n+1}{\ell +1}$ und was es tut, ist das größte Element zu reparieren und das verbleibende auszuwählen $k.$Hier wählen Sie ein mittleres Element aus! (Nennen$i$und links und rechts auswählen (wie bei Vandermonde).
Kein ernsthafter Hinweis: Ich habe diese Identität schon einmal "Vandermonde spielt Hockey" genannt.