Number of lattice paths from $(0, 0)$ to $(n, m)$ that make exactly $k$ turns

Question

I've tried using the number of positive integer solutions to $x_1 + x_2 \cdots + x_l = n$ and $y_1+y_2\cdots y_{k-l} = m$ and adding their product over $l$. I am highly unsure of this approach.

Any hints would be highly appreciated.

Edit : Only right and up moves are allowed

Answer 1

You need to go $n$ units horizontal and $m$ units vertical. If $k$ is odd you have $\frac 12(k+1)=p$ runs in each direction and you have to split the total distance among those runs. You have $n-1 \choose p-1$ ways to split the horizontal runs and $m-1 \choose p-1$ ways to split the vertical runs. You can also start horizontal or vertical, so there are $$2{n-1 \choose \frac 12(k-1)}{m-1 \choose \frac 12(k-1)}$$ ways.

I leave the case of $k$ even to you. It is the same idea but more complicated because you have a different number of horizontal and vertical runs.