¿Cuál es la prueba directa de la relación de recurrencia sobre la enumeración de rutas de celosía dada por Bizley?

Question

Dejar $k$ ser un número entero no negativo y dejar $m,n$ser enteros coprimos positivos. Dejar$\phi_k$ sea ​​el número de caminos de celosía de $(0,0)$ a $(km,kn)$ con escalones $(0,1)$ y $(1,0)$ que nunca se elevan por encima de la línea $my=nx$. Un camino que tenga esta propiedad se llamará$\phi$-camino. Luego,$\phi_k$ satisface la relación de recurrencia $$ k(m+n)\phi_k = \sum_{j=1}^{k}\binom{j(m+n)}{jm}\phi_{k-j} $$ para todos $k \in \mathbb{Z}^+$, como lo muestra Bizley (1954) .

Bizley ha afirmado que “estas relaciones pueden deducirse directamente mediante un razonamiento general a partir de las propiedades geométricas de los caminos”. Sin embargo, no pude conseguir una demostración combinatoria de este teorema.

Pregunta: ¿Cuál es la prueba directa de la relación de recurrencia mencionada anteriormente?

Mi primer pensamiento sobre esta relación fue que el lado izquierdo de la ecuación cuenta el número de permutaciones cíclicas de todas $\phi$-rutas de $(0,0)$ a $(km,kn)$. En su artículo, Bizley define el punto más alto de una ruta de celosía como "un punto de celosía$X$ en el camino de tal manera que la línea de gradiente $\frac{n}{m}$ mediante $X$ corta el eje y a un valor de $y$no menos que el correspondiente a cualquier otro punto de celosía del camino ”. (Es importante señalar que el primer punto$(0,0)$ se considera que no pertenece al camino) .Así, el número de permutaciones cíclicas de todas las $\phi$-los caminos pueden expresarse como la suma de $t$ multiplicado por el número de todas las rutas de celosía con exactamente $t$ puntos más altos para todos $t=1,2,\ldots,k$. Sin embargo, aparentemente el lado derecho de la ecuación no tiene nada que ver con el número de caminos de celosía con un número específico de puntos más altos.

Me temo que me estoy perdiendo algo obvio acerca de las propiedades geométricas del $\phi$-paths y estaría muy contento si alguien pudiera proporcionar una prueba combinatoria o truco que no pude ver. Gracias por su atención de antemano.

Answer 1

El truco es agregar $\phi_k$a ambos lados de la ecuación, e interprete el lado izquierdo como caminos de conteo con un paso horizontal antepuesto y uno de sus pasos marcado. Luego, haga que el paso marcado sea el primer paso de un camino desde$(-1, 0)$ a $(km, kn)$. Dejar$j$ ser mínimo para que este camino golpee $(jm, jn)$ y se queda abajo $my = nx$después. Luego, los pasos antes del punto de encuentro, excluyendo el último paso horizontal, forman una ruta arbitraria contada por el coeficiente binomial en el sumando con índice$j$, y los pasos restantes forman un camino contado por $\phi_{k-j}$.