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.



Is this a known symmetry of lattice paths?
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](https://www.math.ucla.edu/%7Epak/papers/excited_multivariate.pdf)  and yet [further](https://www.combinatorics.org/ojs/index.php/eljc/article/view/v27i3p44) by Pak and myself.


