Counting Up-Right Grid Paths With No k Consecutive Moves in One Direction

A frog starts at $(0, 0)$ and wants to reach $(X, Y)$, where $X$ and $Y$ are nonnegative integers. Each move takes it one unit right or one unit up. The frog may never move in the same direction $k$ or more times in a row, so every maximal run of consecutive right moves or consecutive up moves has length at most $k - 1$. How many valid paths are there? The specific values of $X$, $Y$ and $k$ are generated randomly, and the answer is an exact integer. ```hint What a partial path must remember Decide what you need to know about the end of a partial path to tell which next move is allowed, and how to avoid storing more than that. ``` ### Constraints and Clarifications - $X$, $Y$ and $k$ are integers with $X, Y \ge 0$ and $k \ge 2$. - A run of exactly $k$ moves is forbidden, and runs of $k - 1$ moves are allowed. - The same limit applies to both directions. ### Clarifying Questions - Is the rule that $k$ or more moves in a row are forbidden, or only more than $k$? - If one coordinate is zero, is the single straight path allowed when it is shorter than $k$? - How large can $X$ and $Y$ be, and should the count be exact or taken modulo a prime? ### What a Strong Answer Covers - A state definition that captures exactly the information the run limit needs - A correct recurrence, with base cases at the origin and along the axes - Time and space complexity, with a prefix-sum or combinatorial speedup - Verification on small cases that can be enumerated by hand ### Follow-up Questions - How would you count the paths with a sum over the numbers of runs instead of a table? - How does the method change if right moves and up moves have different run limits? - How would you sample a valid path uniformly at random?