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.