4
$\begingroup$

Find the number of lattice path of length $2n$ that starts on $(0, 0)$ such that for all the points $(x, y)$ in the path, $x < y$. So pretty much all the points besides the origin are strictly above the line $y = x$.

What I have done so far is that, given a point: $$p =(k, 2n-k)$$ We know that $$k < 2n - k$$ The total number of path paths will be $${2n \choose k}$$

so my approach is that in order for the paths to not meet the requirement, it must have some other point on the diagonal.

I defined a set $A(j)$, which consists of paths from $(0, 0)$ to $(j, j)$ where no points other than the origin and endpoint.

I found that $|A(j)| = \frac{2}{j} {2n-2 \choose n-1}$ because for every such path, if you take away the first and last step, it becomes dyck path from $(0, 0)$ to $(j-1, j-1)$.

Then you multiply that by the number of paths from$(j, j)$ to $(k, 2n-k)$. Which is $${2n-2j \choose k-j}$$

Thus, $$B(j) = |A(j)|{2n-2j \choose k-j} $$ will be the amount of paths from $(0, 0)$ to point $p$ such that $(j, j)$ is the first point in the diagonal.

Then I do $$F(p)=\sum_{j=1}^{k} B(j)$$ To get amount of all the paths that intersects with the diagonal at least once after the origin. Subtracting that from the total amount of paths possible I get the number of paths that meets the requirement for that point.

Then I do it for all the points to get a total number of paths that never intersects with diagonal. But I'm kinda stuck on the summation part. Is there another approach to this?

| cite | improve this question | | | | |
$\endgroup$
  • 1
    $\begingroup$ This problem typically has the constraint that you finish at $(n,n)$ and make only steps of the form $(x,y) \to (x+1,y)$ and $(x,y) \to (x,y+1)$. Is that the case here, or are you only constrained by $x < y$? $\endgroup$ – Eric Tressler Oct 5 '15 at 1:36
  • $\begingroup$ you don't have to finish at $(n, n)$. As long as the path is of the length $2n$. so an example will be $(0, 2n)$ or $(1, 2n-1)$ as end points. so I'm only constrained by $x < y$. $\endgroup$ – Phantom Oct 5 '15 at 1:53
  • $\begingroup$ Can the path intersect itself above the diagonal? For example could it go (0,0),(0,1),(0,2),(1,2),0,2) and count toward paths of length 2n where n=2? Also can the x coordinate decrease during the path, and or the y coordinate? $\endgroup$ – coffeemath Oct 6 '15 at 13:12
3
$\begingroup$

We consider lattice paths starting from $(0,0)$ containing horizontal $(1,0)$-steps and vertical $(0,1)$-steps only.

The following is valid. The number of paths of length $2n$ starting at $(0,0)$ and never touching the diagonal $x=y$ again is \begin{align*} \binom{2n-1}{n-1}\qquad\qquad\qquad n\geq 1 \end{align*}

Note, the number of paths of shortest length from $(x_0,y_0)$ to $(x_1,y_1)$ with $x_0\leq x_1$ and $y_0\leq y_1$ is \begin{align*} \binom{(x_1-x_0)+(y_1-y_0)}{x_1-x_0}\tag{1} \end{align*}

Paths of length $2n$ starting at $(0,0)$ and never touching the diagonal again end in points \begin{align*} (k,2n-k)\qquad\qquad\qquad 0\leq k \leq n-1 \end{align*}

Since the first step is always from $(0,0)$ to $(0,1)$ in order to walk above the diagonal, we consider at first the number of all paths from $(0,1)$ to $(k,2n-k)$. This number is according to (1)

\begin{align*} \binom{2n-1}{k}\qquad\qquad\qquad 0\leq k \leq n-1 \end{align*}

From this number we have to subtract the number of all paths from $(0,1)$ to $(k,2n-k)$ which touch (or cross) the diagonal $x=y$.

This can be determined using Andre's Reflection Principle: A path starting from $(0,1)$ going to $(k,2n-k)$ which touches the diagonal, will touch it the first time let's say at $(t,t)$. So, each such path consists of two parts. The first part from $(0,1)$ to $(t,t)$ and the second from $(t,t)$ to $(k,2n-k)$. We bijectively map paths of this shape by reflecting the first part at the diagonal and leaving the second part unchanged. This way we get a reflected path starting at $(1,0)$ crossing at $(t,t)$ the diagonal the first time and ending in $(k,2n-k)$.

We conclude: The number of paths from $(0,1)$ to $(k,2n-k)$ which touch the diagonal $x=y$ is equal to the number of all pathes from $(1,0)$ to $(k,2n-k)$ and is according to (1) \begin{align*} \binom{2n-1}{k-1} \end{align*}

Let's denote with $P_k(n)$ the number of all paths from $(0,0)$ to $(k,2n-k)$ which do not touch the diagonal again. The following is valid for $n\geq 1$ \begin{align*} P_k(n)= \begin{cases} 1\qquad\qquad &k=0\\ \binom{2n-1}{k}-\binom{2n-1}{k-1}\qquad\qquad &k\geq 1 \end{cases}\tag{2} \end{align*}

Note that for $k=0$ there is exactly one path from $(0,0)$ to $(0,2n)$. Since in this case there are no paths touching the diagonal which are to subtract, we interpret the binomial coeffient $\binom{r}{s}$ with negative $s$ as usual with zero and we obtain $P_0(n)=\binom{2n-1}{0}-\binom{2n-1}{-1}=1$.

Now it's time to harvest: The number of all paths of length $2n$ starting at $(0,0)$ and never touching the diagonal again is \begin{align*} \sum_{k=0}^{n-1}P_k(n)&=\sum_{k=0}^{n-1}\left(\binom{2n-1}{k}-\binom{2n-1}{k-1}\right)\\ &=\sum_{k=0}^{n-1}\binom{2n-1}{k}-\sum_{k=1}^{n-1}\binom{2n-1}{k-1}\tag{3}\\ &=\sum_{k=0}^{n-1}\binom{2n-1}{k}-\sum_{k=0}^{n-2}\binom{2n-1}{k}\\ &=\binom{2n-1}{n-1} \end{align*} and the claim is proved.

Comment: In (3) we split the sum and skip the index $k=0$ in the right hand sum since it's contribution is zero. In the following line we shift the index by $1$ in the right hand sum.

| cite | improve this answer | | | | |
$\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.