Number of lattice paths

Question

In my notes I have this:

A lattice path is path consisting of step points $(x_0,y_0),(x_1,y_1),\ldots,(x_m,y_m).$ where either

$x_{i+1}=x_{i}$ and $y_{i+1}=y_i+1$

or $x_{i+1}=x_{i}+1$ and $y_{i+1}=y_i$.

If in a lattice path , $x_i \gt y_i$ $\forall i$ except $i=0$ or $i=m,$we say path is a good path ,otherwise a bad path..

After that I can't understand this:

then it is written that total no. of paths are: $\binom{x_m+y_m-x_0-y_0}{x_m-x_0}$,

Please help how to arrive at this formula ....

---

EDIT:I got answer for total no. of paths but can't understand this:

Book says to find Bad path consider this:

Let $\tau$ be a path from $(x_0,y_0)$ to $(x_m,y_m)$ ,$\tau$ is a bad path so it touches line $y=x$ .

Let $\tau=\tau_1+\tau_2$

$\tau_1$ is path from $(x_0,y_0)$ to $(i,i)$,and

$\tau_2$ is path from $(i,i)$ to $(x_m,y_m)$.Take $\tau_1'$ =reflection of $\tau_1$ about $y=x$ .

$\tau'=\tau_1'+\tau_2$ is path from $(y_0,x_0)$ to $(x_m,y_m)$.

So,there is 1-1 correspondence between bad paths from $(x_0,y_0)$ to $(x_m,y_m)$ by $\tau=\tau'$.

Bad paths are all paths from $(y_0,x_0)$ to $(x_m,y_m)$ =$\binom{x_m+y_m-x_0-y_0}{x_m-y_0}$

But I can't still understand

• how to conclude that Bad paths are all paths from $(y_0,x_0)$ to $(x_m,y_m)$ .

Please help....

---

Answer 1

A hint: The technique in your example is called Andre's reflection principle. An example with reflection at the diagonal (and ties allowed!) can be found in Bertrand's ballot theorem.

Added 2014-10-04: according to comment below of @spectraa

The idea is to construct a bijection between the bad pathes and all pathes starting in $(y_0,x_0)$ end ending in $(x_m,y_m)$.

We have following situation:

Startvalue $A=(x_0,y_0)$ is below the diagonal $y=x$, since $x_0 > y_0$

Endvalue $B=(x_m,y_m)$ is below the diagonal $y=x$, since $x_m > y_0$

All pathes are the pathes containing $(1,0)$-steps or $(0,1)$-steps from $A$ to $B$

Good pathes are the pathes from $A$ to $B$ which are below the diagonal $y=x$

Bad pathes are all pathes from $A$ to $B$, which are not good pathes.

We observe:

• A bad path is a path from $A$ to $B$ which touches (or crosses) the diagonal $y=x$.

• Let's say a bad path $p$ touches (or crosses) the diagonal (the first time!) at $Z=(z,z)$

• We reflect this bad path at the diagonal $y=x$ and get a path $\overline{p}$ starting at $\overline{A}=(y_0,x_0)$, which touches (or crosses) the diagonal $y=x$ the first time at $Z$ and ends in $B$.

Now the following holds:

• All reflected pathes of bad pathes have the property that they start at $\overline{A}$ and end in $B$.

• Since $\overline{A}=(y_0,x_0)$ with $y_0 > x_0$ all reflected pathes have to cross the diagonal in order to reach $B$.

This is so because $B=(x_m,y_m)$ with $x_m > y_m$ and therefore along a reflected bad path we walk through a point $Z^\prime$ with $x$-value equal $y$-value.

On the other hand:

Since all pathes starting in $\overline{A}$ and ending in $B$ have to cross the diagonal in order to reach $B$. Therefore they themselves can be reflected at the diagonal. After reflection they:

• start in $A$

• touch (or cross) the diagonal and

• end in $B$.

So they are a bad path.

Conclusion There is a bijection between the bad pathes and those pathes starting in the reflected point $\overline{A}$ and ending in $B$, therefore the number of them is equal.

Answer 2

The discussion about good/bad paths seems to have no relevance to the question, so let's ignore that.

We can assume WLOG that $x_0 = y_0 = 0$. Now, any path from $(0,0)$ to $(x_m,y_m)$ satisfying your condition will have length $x_m+y_m$. At each vertex you have the choice between going up or to the right, and you know that at exactly $x_m$ points, you'll have to go to the right to end up in $(x_m,y_m)$. This is the only condition though: a path is given by choosing which $x_m$ of the $x_m+y_m$ of the points will be the points after which you head to the right. There are exactly $\binom{x_m+y_m}{x_m}$ such choices.