I have the following question, usually I'd solve by a modification of pascals triangle but I'm not sure how to approach this using pascals since step D is problematic. How could I go about this?
Consider paths on the square grid. We allow three types of step:
• R: moving one unit right, from $(x, y)$ to $(x + 1, y)$,
• D: moving one unit down, from $(x, y)$ to $(x, y − 1)$,
• K: a “knight’s move”, from $(x,y)$ to $(x+1,y+2)$.
Using these steps, how many allowable paths are there from (0, 0) to (m, 0) which use exactly $t$ K -steps?
In particular, how many allowable paths in all are there from (0, 0) to (3, 0)?
Each step never goes left, and the R and K steps move exactly $1$ unit to the right. It is then clear that we must take $m-t$ R steps; the D steps only cancel the upwards movement of the R steps so there must be $2t$ D steps.
So $m+2t$ steps are made in total, and the number of possible paths is $$\binom{m+2t}{2t,t,m-t}$$ For the second question, just fix $m=3$, calculate the number of paths for $0\le t\le3$ and add up.