4
$\begingroup$

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.

$\endgroup$

2 Answers 2

6
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ This is great, thanks! $\endgroup$
    – Will Hardt
    Jan 4, 2023 at 21:06
4
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ 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.) $\endgroup$
    – Will Hardt
    Jan 10, 2023 at 0:29
  • 1
    $\begingroup$ 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. $\endgroup$
    – Ira Gessel
    Jan 10, 2023 at 2:13
  • $\begingroup$ Got it, thanks for explaining that! $\endgroup$
    – Will Hardt
    Jan 10, 2023 at 3:38

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.