2
$\begingroup$

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.. enter image description here

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


$\endgroup$
2
+50
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ my doubt is only with the step in question that how did we conclude that Bad paths are all paths from $(y_0,x_0)$ to $(x_m,y_m)$ .......... $\endgroup$ – spectraa Oct 4 '14 at 11:48
  • $\begingroup$ @spectraa: I've added some notes in my answer. Hope it helps! :-) Regards. $\endgroup$ – Markus Scheuer Oct 4 '14 at 14:39
  • $\begingroup$ thanks a lot the answer is clear to me now... $\endgroup$ – spectraa Oct 4 '14 at 16:18
  • 1
    $\begingroup$ Great! And thanks for the bounty! :-) $\endgroup$ – Markus Scheuer Oct 4 '14 at 16:36
7
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.