# Is this a known symmetry of lattice paths?

I recently came across the fact that NE lattice paths from $$(0,0)$$ to $$(m,n)$$ in aggregate pass through each row and column an equal number of times (which also has a corresponding binomial identity); I am wondering if this is a well-known fact and whether anyone can point me to a reference for it. Precise details below. This is joint work with Phillip Harris and John Yin.

Consider the set $$P_{m,n}$$ of lattice paths from (0,0) to (m,n) using North (0,1) and East (1,0) steps. To each lattice path L, we associate the 0-1 matrix $$M_L$$ indexed by $$\{0,1,...,n\} \times \{0,1,...,m\}$$ which has a 1 in position $$(i,j)$$ iff L passes through the point $$(i,j)$$. Let $$M_{m,n} = \sum_{L \in P_{m,n}} M_L$$.

By construction, the (downward-sloping) "diagonal sums" of each $$M_L$$ are all 1 -- where by "diagonal" I mean a set of the form $$\{(i,j): i+j=k\}$$. Therefore, $$M_{m,n}$$ also has uniform diagonal sums (equal to $$|P_{m,n}|$$).

What's more is that $$M_{m,n}$$ also has uniform row and column sums. This can be shown with bijections (in the column case) between lattice path-point pairs $$(L,p)$$, where $$p$$ is a point that $$L$$ passes through. To see that columns $$i$$ and $$j$$ have the same sum in $$M_{m,n}$$, we use the following involution. Given a pair $$(L,p)$$ with $$p$$ in column $$i$$, we rotate by $$180 ^\circ$$ the segment of $$L$$ between columns $$i$$ and $$j$$ inclusive. This results in a (presumably different) lattice path $$L'$$ and $$p$$ has been mapped to a point $$p'$$ in column $$j$$.

Since $$M_{m,n}$$ is a $$(n+1) \times (m+1)$$ matrix with all diagonal sums equal and all column sums equal, each column sum must be $$\frac{m+n+1}{m+1}$$ times each diagonal sum, so the corresponding binomial identity is:

For any integers $$m,n > 0$$ and $$0 \leq i \leq m$$, we have $$\sum_{j=0}^n \binom{i+j}{i} \binom{m-i+n-j}{m-i} = \frac{m+n+1}{m+1} \binom{m+n}{m}$$.

Can anyone point me to a reference for either the lattice path row/column symmetry or this binomial identity? Many thanks.

Edit: The RHS of the above identity also equals $$\binom{m+n+1}{n}$$, so one could alternatively derive it by employing a bijection between $$P_{m+1,n}$$ and paths in $$P_{m,n}$$ with a marked point; the bijection could be adding an eastward step at the marked point.

Not only sums, but the distribution of a value 'number of points in the $$j$$-th column' is independent of $$j$$, by the same bijection.
A more general result is that the sum $$\sum_{L}\prod_{(i,j)\in L}\frac1{x_i+y_j}=F(x_0,\ldots,x_n;y_0,\ldots,y_m)$$ is symmetric in $$x_i$$'s and symmetric in $$y_j$$'s. (To reproduce the aforementioned symmetry, put $$x_i=x$$ for all $$i$$, $$y_s=1$$, other $$y_j$$'s are equal to $$1-x$$, $$F$$ specifies to $$\sum_{L} (1+x)^{-|i:(i,s)\in L|}$$, and this generating function does not depend on $$s$$ that is equivalent to the claim that the distribution of $$|i:(i,s)\in L|$$ is independent of $$s$$.) This may be further generalized, as was done by Morales, Pak and Panova and yet further by Pak and myself.
The binomial identity is the well-known Vandermonde's theorem $$\sum_{j=0}^n \binom{a}{j}\binom{b}{n-j} = \binom{a+b}{n}$$ with $$a=-i-1$$, $$b=i-m-1$$.
• Sorry for not following, but are you saying that $\sum_{j=0}^n \binom{i+j}{j}\binom{m+n-i-j}{n-j} = \binom{m+n+1}{n}$ is a version of the Vandermonde identity? I don't see how it is, as the top binomial coefficients are changing. But maybe you mean in more than one step? (One can specialize it to the hockey-stick identity, though, e.g. by setting i=0.) Jan 10, 2023 at 0:29
• The binomial coefficient $\binom cn$ is defined to be $c(c-1)\cdots (c-n+1)/n!$ for all $c$. Then $\binom {-c}{n} = (-1)^n \binom{c+n-1}{n}$. Vandermonde's theorem as I stated it is an identity of polynomials in $a$ and $b$, so it is valid for all $a$ and $b$, not just nonnegative integers. If we set $a=-i-1$ and $b=i-m-1$ in $\sum_{j=0}^n \binom{a}{j}\binom{b}{n-j} = \binom{a+b}{n}$ and simplify using $\binom {-c}{n} = (-1)^n \binom{c+n-1}{n}$ we get $(-1)^n\sum_{j=0}^n \binom{i+j}{j}\binom{m-i+n-j}{n-j}=(-1)^n\binom{m+n+1}{n}$, which is equivalent to your identity. Jan 10, 2023 at 2:13