Bizleyによって与えられた格子パス列挙に関する漸化式の直接的な証拠は何ですか？
しましょう $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}^+$、Bizley（1954）によって示されているように。
ビズリーは、「これらの関係は、経路の幾何学的特性から一般的な推論によって直接推論できる」と述べています。しかし、私はこの定理の組み合わせ論的証明を得ることができませんでした。
質問：上記の漸化式の直接的な証拠は何ですか？
この関係について最初に考えたのは、方程式の左辺がすべての巡回置換の数を数えるということでした。 $\phi$-からのパス $(0,0)$ に $(km,kn)$。彼の論文では、Bizleyは格子パスの最高点を「格子点」と定義しています。$X$ 勾配の線が $\frac{n}{m}$ 使って $X$ y軸を次の値でカットします $y$パスの他の格子点に対応するもの以上」。（最初のポイントに注意することが重要です$(0,0)$ パスに属していないものと見なされます。）したがって、すべての巡回置換の数 $\phi$-パスは、の合計として表すことができます $t$ すべてのラティスパスの数を正確に $t$ すべての最高点 $t=1,2,\ldots,k$。ただし、方程式の右辺は、指定された最高点の数を持つ格子パスの数とは関係がないようです。
私は、の幾何学的特性について明らかな何かが欠けているのではないかと心配しています。 $\phi$-パスと私は、誰かが私が見ることができなかった組み合わせ論的証明またはトリックを提供できればとてもうれしいです。よろしくお願いします。
回答
秘訣は追加することです $\phi_k$方程式の両側に、左側を、水平ステップが付加され、そのステップの1つがマークされたパスを数えるものとして解釈します。次に、マークされたステップをからのパスの最初のステップにします$(-1, 0)$ に $(km, kn)$。しましょう$j$ このパスがヒットするように最小限にする $(jm, jn)$ 下にとどまる $my = nx$その後。次に、最後の水平ステップを除く、合流点の前のステップは、インデックス付きの被加数の二項係数によってカウントされる任意のパスを形成します。$j$、および残りのステップは、によってカウントされるパスを形成します $\phi_{k-j}$。