Roads in a grid $(s+m+1) \times (n-m)$

Question

Let $s, m,n \in \mathbb{N_0}$.

For $n \geq m$ we have the grid $(s+m+1) \times (n-m)$.

(a) How can one find out how many different grid roads from $(0,0)$ to $(s,k)$ exist for a fixed $k$? (A grid road is defined as a way, which only consists of (1,0) (going right) or (0,1) (going to the top) steps.

(b) And how many different grid roads exist from $(s+1,k)$ to $(s+m+1,n-m)$ exist for a fixed $k$?

For (a) I would say that for a fixed $k$ we have $$(s+m+1)+(n-m) \choose (s+m+1) $$ because in a normal grid there are $n+m \choose n$.

For (b) I would say $$(s+m+1+1) + (n-m) \choose s+m$$

Is it possible to show Vandermonde's identity by using what is given above?

Answer 1

The number of paths from $(0,0)$ to $(s+m+1,n-m)$ is \begin{align*} \binom{(s+m+1)+(n-m)}{s+m+1}=\binom{s+n+1}{s+m+1} \end{align*} since the length of each path is $(s+m+1)+(n-m)=s+n+1$ and we have to select $s+m+1$ $(1,0)$-steps in $x$-direction, leaving $n-m$ $(0,1)$-steps in $y$-direction.

Now we fix a vertical line going through $(s,0)$. Each path from $(0,0)$ to $(s+m+1,n-m)$ will cross the line at some point $(s,k)$ with $0\leq k\leq n-m$.

We can so partition all valid paths by taking paths crossing the line at a specific height $k$.

The number of paths from $(0,0)$ to $(s+m+1,n-m)$ passing $(s,k)$ is the number of paths from $(0,0)$ to $(s,k)$ times the number of paths from $(s,k)$ to $(s+m+1,n-m)$.

Note that from $(s,k)$ we do horizontal step $(1,0)$ to $(s+1,k)$, since the vertical step from $(s,k)$ to $(s,k+1)$ is already contained when considering all paths from $(0,0)$ to $(s,k+1)$.

• The number of paths from $(0,0)$ to $(s,k)$ is $$\binom{s+k}{s}$$

• The number of paths from $(s,k)$ to $(s+1,k)$ is $1$

• The number of paths from $(s+1,k)$ to $(s+m+1,n-m)$ is $$\binom{((s+m+1)-(s+1))+((n-m)-k)}{(s+m+1)-(s+1)}=\binom{n-k}{m}$$

• The number of paths from $(0,0)$ to $(s+m+1,n-m)$ passing $(s,k)$ and $(s+1,k)$ is $$\binom{s+k}{s}\binom{n-k}{m}$$

Since $k$ may vary from $0$ to $n-m$ we finally get the Chu-Vandermonde Identity in the form

\begin{align*} \color{blue}{\sum_{k=0}^{n-m}\binom{s+k}{s}\binom{n-k}{m}=\binom{s+n+1}{s+m+1}} \end{align*}