Was ist der direkte Beweis für die von Bizley gegebene Wiederholungsrelation zur Aufzählung von Gitterpfaden?

Question

Lassen $k$ sei eine nichtnegative ganze Zahl und lass $m,n$Coprime-positive ganze Zahlen sein. Lassen$\phi_k$ sei die Anzahl der Gitterpfade von $(0,0)$ zu $(km,kn)$ mit Schritten $(0,1)$ und $(1,0)$ das steigt nie über die Linie $my=nx$. Ein Pfad mit dieser Eigenschaft wird als a bezeichnet$\phi$-Pfad. Dann,$\phi_k$ erfüllt die Wiederholungsrelation $$ k(m+n)\phi_k = \sum_{j=1}^{k}\binom{j(m+n)}{jm}\phi_{k-j} $$ für alle $k \in \mathbb{Z}^+$, wie von Bizley (1954) gezeigt .

Bizley hat erklärt, dass „diese Beziehungen direkt durch allgemeine Überlegungen aus den geometrischen Eigenschaften der Pfade abgeleitet werden können“. Es gelang mir jedoch nicht, einen kombinatorischen Beweis für diesen Satz zu erhalten.

Frage: Was ist der direkte Beweis für die oben erwähnte Wiederholungsbeziehung?

Mein erster Gedanke an diese Beziehung war, dass die linke Seite der Gleichung die Anzahl der zyklischen Permutationen aller zählt $\phi$-Pfade von $(0,0)$ zu $(km,kn)$. In seiner Arbeit definiert Bizley den höchsten Punkt eines Gitterpfades als „Gitterpunkt“$X$ auf dem Weg so, dass die Linie des Gradienten $\frac{n}{m}$ durch $X$ schneidet die y-Achse auf einen Wert von $y$nicht weniger als der, der einem anderen Gitterpunkt des Pfades entspricht “. (Es ist wichtig zu beachten, dass der erste Punkt$(0,0)$ wird als nicht zum Pfad gehörend angesehen.) Somit ist die Anzahl der zyklischen Permutationen aller $\phi$-Pfade können als die Summe von ausgedrückt werden $t$ mal die Anzahl aller Gitterpfade mit genau $t$ höchste Punkte für alle $t=1,2,\ldots,k$. Anscheinend hat die rechte Seite der Gleichung jedoch nichts mit der Anzahl der Gitterpfade mit einer bestimmten Anzahl von höchsten Punkten zu tun.

Ich fürchte, mir fehlt etwas Offensichtliches an den geometrischen Eigenschaften des $\phi$-paths und ich wären so froh, wenn jemand einen kombinatorischen Beweis oder Trick liefern könnte, den ich nicht sehen konnte. Vielen Dank für Ihre Aufmerksamkeit im Voraus.

Answer 1

Der Trick ist hinzuzufügen $\phi_k$zu beiden Seiten der Gleichung, und interpretieren Sie die linke Seite als Zählpfade mit einem vorangestellten horizontalen Schritt, und einer seiner Schritte ist markiert. Machen Sie dann den markierten Schritt zum ersten Schritt eines Pfades von$(-1, 0)$ zu $(km, kn)$. Lassen$j$ minimal sein, so dass dieser Pfad trifft $(jm, jn)$ und bleibt unten $my = nx$danach. Dann bilden die Schritte vor dem Treffpunkt mit Ausnahme des letzten horizontalen Schritts einen beliebigen Pfad, der durch den Binomialkoeffizienten im Summanden mit Index gezählt wird$j$und die verbleibenden Schritte bilden einen Pfad, der von gezählt wird $\phi_{k-j}$.