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….
Best Answer
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.