Is this a known symmetry of lattice paths?

Question

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.

Answer 1

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.

Answer 2

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$.