Find the number of lattice paths from $(0,0)$ to $(n,k)$ with even direction changes. Movement is restricted to rightwards and upwards.

I've thought of two approaches, both of which I have not managed to come to a reasonable conclusion yet.

Approach 1: Recurrence relations.

Let $o_i$, $e_i$, $t_i$ be the number of odd paths, even paths, total paths from $(0,0)$ to $(i,i)$. I figured that if I can work out this case, then the generalization to $(n,k)$ will be along similar lines.

So far, I have that $t_i={{2i}\choose{i}}$ and I can see that $o_i$ is related to $e_{i-1}$ and $o_{i-2}$, and vice versa for $e_i$ but I have yet to produce a anything more than that.

Approach 2: Bijection to sequence of Rs (for rightwards) and Us (upwards).

In such a sequence, a direction change is identified by the existence of a pair of RU or UR. For instance, when $i=3$, RRRUUU has 1 direction change and RRUUUR has 2 direction changes. I've been trying to further characterise the sequence but have no ideas on how to proceed either.

Any help in either of these two approaches will be very helpful. Thanks.


Hint: An even number of direction changes means that the first and last steps must be in the same direction (both R or both U with your notation). So there are two cases: R...R and U...U. Then the remaining Rs and Us can be arranged in between as desired.


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.