The number of $n$-step NSEW lattice paths from $(0,0)$ to $(a,b)$ that intersect the line $y=k$ precisely $t$ times is independent of $k$, for $0\leq k\leq b$, where we assume $b\geq0$ for simplicity.

This is easy to show by exhibiting an involution on the set of $n$-step NSEW paths from $(0,0)$ to $(a,b)$: for $0\leq k<k'\leq b$, take the portion of the path from the first intersection with $y=k$ to the last intersection with $y=k'$, and rotate it by 180°. This exchanges intersections with $y=k$ and intersections with $y=k'$.

This seems to be quite a useful symmetry. For example it leads to a nice combinatorial interpretation of the “Andrews-Paule identity” $$\sum_{i=0}^n\sum_{j=0}^n{i+j\choose j}^2{4n-2i-2j\choose 2n-2i}=(2n+1){2n\choose n}^2$$

I imagine it is a well-known fact, but I’m not sure where to look. Perhaps it is known in the context of the 2D random walk? I’d be grateful for any suggestions or (even better) references.

Added: Since this question as written has no responses, let me explicitly widen the net to admit references to the 1-dimensional analogue of this observation, since the essential idea is the same in any number of dimensions, and 1-d paths have been better studied. (They’re usually described as NE/SE or N/E lattice paths in 2 dimensions, presumably because those representations map directly to readable diagrams).

In a now-deleted answer, Mark Wildon pointed to Lemma 4 in this nice paper of his (2009), which is indeed essentially the same idea in 1d. Does anyone know an earlier reference to this idea?


Your Answer

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

Browse other questions tagged or ask your own question.