Каково прямое доказательство рекуррентного соотношения о нумерации путей в решетке, данное Бизли?
Позволять $k$ - неотрицательное целое число и пусть $m,n$быть взаимно простыми положительными целыми числами. Позволять$\phi_k$ - количество путей решетки из $(0,0)$ к $(km,kn)$ со ступенями $(0,1)$ а также $(1,0)$ которые никогда не поднимаются над чертой $my=nx$. Путь, обладающий этим свойством, будет называться$\phi$-дорожка. Потом,$\phi_k$ удовлетворяет рекуррентному соотношению $$ k(m+n)\phi_k = \sum_{j=1}^{k}\binom{j(m+n)}{jm}\phi_{k-j} $$ для всех $k \in \mathbb{Z}^+$, как показано Бизли (1954) .
Бизли заявил, что «эти отношения могут быть выведены непосредственно путем общих рассуждений из геометрических свойств путей». Однако мне не удалось получить комбинаторное доказательство этой теоремы.
Вопрос: Какое прямое доказательство упомянутого выше рекуррентного соотношения?
Моя первая мысль об этом соотношении заключалась в том, что левая часть уравнения подсчитывает количество циклических перестановок всех $\phi$-путь от $(0,0)$ к $(km,kn)$. В своей статье Бизли определяет наивысшую точку решетчатого пути как «точку решетки.$X$ на пути так, чтобы линия градиента $\frac{n}{m}$ через $X$ обрезает ось Y на значение $y$не меньше, чем соответствующая любой другой точке решетки пути ». (Важно отметить, что первый пункт$(0,0)$ считается не принадлежащим пути.) Таким образом, количество циклических перестановок всех $\phi$-путь может быть выражен как сумма $t$ умноженное на количество всех путей решетки с точно $t$ самые высокие баллы для всех $t=1,2,\ldots,k$. Однако, по-видимому, правая часть уравнения не имеет ничего общего с количеством путей решетки с заданным количеством наивысших точек.
Боюсь, я упускаю что-то очевидное о геометрических свойствах $\phi$-paths, и я был бы очень рад, если бы кто-нибудь смог предоставить комбинаторное доказательство или трюк, который мне не удалось увидеть. Заранее благодарим за внимание.
Ответы
Уловка состоит в том, чтобы добавить $\phi_k$к обеим сторонам уравнения, и интерпретируйте левую часть как счетные пути с добавленным горизонтальным шагом, и один из его шагов отмечен. Затем сделайте отмеченный шаг первым шагом пути из$(-1, 0)$ к $(km, kn)$. Позволять$j$ быть минимальным таким, что этот путь попадает $(jm, jn)$ и остается ниже $my = nx$после этого. Тогда шаги до точки встречи, за исключением последнего шага по горизонтали, образуют произвольный путь, подсчитываемый биномиальным коэффициентом в слагаемом с индексом$j$, а оставшиеся шаги образуют путь, рассчитываемый $\phi_{k-j}$.