6
$\begingroup$

Let $k$ be a nonnegative integer and let $m,n$ be coprime positive integers. Let $\phi_k$ be the number of lattice paths from $(0,0)$ to $(km,kn)$ with steps $(0,1)$ and $(1,0)$ that are never rising above the line $my=nx$. A path having this property will be called a $\phi$-path. Then, $\phi_k$ satisfies the recurrence relation $$ k(m+n)\phi_k = \sum_{j=1}^{k}\binom{j(m+n)}{jm}\phi_{k-j} $$ for all $k \in \mathbb{Z}^+$, as shown by Bizley (1954).

Bizley has stated that “these relations can be deduced directly by general reasoning from the geometrical properties of the paths”. However, I could not manage to obtain a combinatorial proof of this theorem.

Question: What is the direct proof of the recurrence relation mentioned above?

My first thought about this relation was that the left-hand side of the equation counts the number of the cyclical permutations of all $\phi$-paths from $(0,0)$ to $(km,kn)$. In his paper, Bizley defines the highest point of a lattice path as “a lattice point $X$ on the path such that the line of gradient $\frac{n}{m}$ through $X$ cuts the y-axis at a value of $y$ not less than that corresponding to any other lattice point of the path”. (It is important to note that the first point $(0,0)$ is regarded as not belonging to the path.) Thus, the number of the cyclical permutations of all $\phi$-paths may be expressed as the sum of $t$ times the number of all the lattice paths with exactly $t$ highest points for all $t=1,2,\ldots,k$. However, apparently the right-hand side of the equation has nothing to do with the number of the lattice paths with a specified number of highest points.

I am afraid I am missing something obvious about the geometrical properties of the $\phi$-paths and I would be so glad if anyone can provide a combinatorial proof or trick that I could not manage to see. Thanks for your attention in advance.

$\endgroup$
2

1 Answer 1

3
+50
$\begingroup$

The trick is to add $\phi_k$ to both sides of the equation, and interpret the left hand side as counting paths with a prepended horizontal step, and one of its steps marked. Then, make the marked step the first step of a path from $(-1, 0)$ to $(km, kn)$. Let $j$ be minimal such that this path hits $(jm, jn)$ and stays below $my = nx$ after that. Then the steps before the meeting point, excluding the final horizontal step, form an arbitrary path counted by the binomial coefficient in the summand with index $j$, and the remaining steps form a path counted by $\phi_{k-j}$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.