# Find the number of lattice paths from $(0,0)$ to $(n,k)$ with even direction changes.

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.