14
$\begingroup$

Consider lattice paths consisting of $2n$ steps, each of which is either $(1,1)$ or $(1,-1)$. The number of such lattice paths that return to the horizontal axis only at times that are a multiple of $4$ is given by $2^n \binom{n}{n/2}$. Can someone provide a combinatorial proof of this fact?


Background: A few months ago on math.SE I asked for a combinatorial proof of the identity $$\sum_{k=0}^n \binom{2k}{k} \binom{2n-2k}{n-k} (-1)^k = 2^n \binom{n}{n/2},$$ when $n$ is even.

The non-alternating version is $$\sum_{k=0}^n \binom{2k}{k} \binom{2n-2k}{n-k} = 4^n.$$ There are several combinatorial proofs of the non-alternating version, and I hoped to adapt one of them. One such proof is that $\binom{2k}{k} \binom{2n-2k}{n-k}$ counts the number of paths of length $2n$ with $2k$ steps above the horizontal axis and $2n-2k$ steps below it. Summing up over all values of $k$ gives the total number of paths of length $2n$, which is $2^{2n} = 4^n$. (I believe I saw this argument in Feller's An Introduction to Probability Theory and Its Applications. It's also in this note by David Callan.)

If we take the alternating version, the paths with positive parity are those with $2k$ steps above the axis for $k$ even, and the paths with negative parity are those with $2k$ steps above the axis for $k$ odd. For each path, break it every time it returns to the horizontal axis. This partitions each path into a number of segments equal to the number of times it returns to the axis. For every path that has a last segment consisting of $2j$ steps for $j$ odd, flip this segment over the horizontal axis. This mapping is an involution and changes the path's parity. Since every odd-parity path must have at least one such odd segment, $$\sum_{k=0}^n \binom{2k}{k} \binom{2n-2k}{n-k} (-1)^k$$ must count the number of paths that have no odd segment; i.e., the number of paths whose returns to the horizontal axis occur only at multiples of $4$. If $n$ is odd, there are no such paths without an odd segment, but if $n$ is even, there are apparently $2^n \binom{n}{n/2}$ of them.

However, I was unable to find an independent combinatorial proof that $2^n \binom{n}{n/2}$ counts the number of lattice paths of length $2n$ with no odd segments. (Again, an "odd" segment here is one of length $2j$, where $j$ is odd.) The math.SE question remained unanswered for over two months until I found a different way to prove the identity I was after combinatorially, but this other way doesn't involve lattice paths. After all the time I spent trying the lattice path approach I would like to see an independent combinatorial proof that $2^n \binom{n}{n/2}$ counts the number of lattice paths whose return times to the axis are multiples of $4$.

$\endgroup$
4
  • 1
    $\begingroup$ Could you be more precise about the argument for the non-alternating version? Sorry, I just am very surprised to see anything combinatorial on less than 3 pages for that thing $\endgroup$ Jan 29, 2012 at 0:52
  • $\begingroup$ @darij: I've added a reference to a note by Callan that gives the argument for the non-alternating version. It's more than three pages. :) $\endgroup$ Jan 29, 2012 at 5:10
  • 3
    $\begingroup$ @darji grinberg: Let me see if the size of this margin, um comment, suffices. First, $2^{2n}$ counts paths of length $2n+1$ ending above the axis. Cut at the last visit to the axis into a balanced path of length $2k$ (obviously $\tbinom{2k}k$ possibilities), then an upstep, then a path of length $2(n-k)$ never descending below its starting point. To see that $\tbinom{2(n-k)}{n-k}$ counts the latter, map it bijectively to a balanced path by reversing every step that is last to attain a level $\leq$ half the ending level. The inverse mapping reverses every step first attaining a level below $0$. $\endgroup$ Jan 29, 2012 at 14:31
  • $\begingroup$ Please help here (or.stackexchange.com/questions/5147/…) in re here (math.stackexchange.com/questions/1095760/…) and here (math.stackexchange.com/questions/8393/…) $\endgroup$
    – BCLC
    Nov 4, 2020 at 8:11

1 Answer 1

7
$\begingroup$

For the record, this question is answered in a pair of papers:

Gábor V. Nagy, A combinatorial proof of Shapiroʼs Catalan convolution, In Advances in Applied Mathematics, Volume 49, Issues 3–5, 2012, Pages 391-396

Péter Hajnal and Gábor V. Nagy. A Bijective Proof of Shapiro’s Catalan Convolution. Electronic Journal of Combinatorics, 21(2), 2014

In particular Lemma 7 of the first paper is, I think, a satisfactory answer to this question. The second paper gives a fully bijective proof.

Thanks to Richard Stanley.


These paths also have an interesting interpretation as NSEW lattice paths (where the set of steps is the four cardinal directions N, S, E, W). They correspond, under the usual bijection between one-dimensional paths of length $2k$ and two-dimensional paths of length $k$, to NSEW lattice paths from $(0,0)$ of length $n$ that intersect the $x$-axis only at positions with an even $x$-coordinate. In other words, to paths on the perforated plane obtained by removing (punching out) all the odd-numbered lattice points on the $x$-axis.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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