Quelle est la preuve directe de la relation de récurrence sur l'énumération des chemins de treillis donnée par Bizley?

Question

Laisser $k$ être un entier non négatif et soit $m,n$être des entiers positifs premiers. Laisser$\phi_k$ être le nombre de chemins de treillis à partir de $(0,0)$ à $(km,kn)$ avec des marches $(0,1)$ et $(1,0)$ qui ne montent jamais au-dessus de la ligne $my=nx$. Un chemin ayant cette propriété sera appelé un$\phi$-chemin. Puis,$\phi_k$ satisfait la relation de récurrence $$ k(m+n)\phi_k = \sum_{j=1}^{k}\binom{j(m+n)}{jm}\phi_{k-j} $$ pour tous $k \in \mathbb{Z}^+$, comme le montre Bizley (1954) .

Bizley a déclaré que «ces relations peuvent être déduites directement par un raisonnement général à partir des propriétés géométriques des chemins». Cependant, je n'ai pas réussi à obtenir une preuve combinatoire de ce théorème.

Question: Quelle est la preuve directe de la relation de récurrence mentionnée ci-dessus?

Ma première pensée à propos de cette relation a été que le côté gauche de l'équation compte le nombre de permutations cycliques de tous $\phi$-chemin de $(0,0)$ à $(km,kn)$. Dans son article, Bizley définit le point le plus élevé d'un chemin de treillis comme «un point de treillis$X$ sur le tracé de telle sorte que la ligne de dégradé $\frac{n}{m}$ à travers $X$ coupe l'axe y à une valeur de $y$pas moins que celui correspondant à tout autre point de treillis du chemin ». (Il est important de noter que le premier point$(0,0)$ est considéré comme n'appartenant pas au chemin.) Ainsi, le nombre de permutations cycliques de tous $\phi$-les chemins peuvent être exprimés comme la somme de $t$ fois le nombre de tous les chemins de réseau avec exactement $t$ points les plus élevés pour tous $t=1,2,\ldots,k$. Cependant, apparemment le côté droit de l'équation n'a rien à voir avec le nombre de chemins de réseau avec un nombre spécifié de points les plus élevés.

J'ai peur de manquer quelque chose d'évident concernant les propriétés géométriques du $\phi$-paths et je serais si heureux si quelqu'un pouvait fournir une preuve combinatoire ou une astuce que je ne pourrais pas voir. Merci pour votre attention à l'avance.

Answer 1

L'astuce consiste à ajouter $\phi_k$aux deux côtés de l'équation, et interpréter le côté gauche comme comptant des chemins avec un pas horizontal ajouté au début, et un de ses pas marqué. Ensuite, faites de l'étape marquée la première étape d'un chemin à partir de$(-1, 0)$ à $(km, kn)$. Laisser$j$ être minimal pour que ce chemin frappe $(jm, jn)$ et reste en dessous $my = nx$après ça. Puis les étapes avant le point de rencontre, à l'exclusion de la dernière étape horizontale, forment un chemin arbitraire compté par le coefficient binomial dans la sommation avec index$j$, et les étapes restantes forment un chemin compté par $\phi_{k-j}$.