Counting Rabbit's Paths Up a Staircase

This is a classic combinatorics question about counting paths in a simple constrained process: a rabbit moving up a staircase with fixed step sizes. The candidate is asked to determine how many different hop sequences reach the top, given a small set of allowed moves and a fixed total distance. It captures the idea of building global counts from local move options in a sequential setting, a pattern that appears in simple dynamic programming warm-ups, probability path counting, and introductory discrete math exercises.

The solution leans on recognizing and formulating a recurrence relation, then either solving it explicitly or computing it iteratively. It can also be approached via counting compositions with restricted part sizes, or via a small-state Markov-style viewpoint where only the current step matters. An interviewer is watching for the ability to abstract the process into states, express the dependency between neighboring states cleanly, and argue why the recurrence correctly counts all possibilities without double counting or omissions. Clear base cases, boundary handling, and an organized reasoning path are central to a strong answer.

What it tests

Problems where an agent can reach a target by making moves of variable sizes often reduce to recurrence relations, because each way to reach the target can be decomposed into the ways to reach the positions immediately before it. The key is that the process is memoryless: the number of ways to reach a given state depends only on the number of ways to reach the states from which it can be accessed in one move. This structure is common in combinatorial counting problems involving sequential decisions with limited options at each step. The recurrence arises because every complete path to the goal can be classified by its final move, and the set of paths to the goal is the union of the sets of paths to each possible pre-goal state, extended by the final move. This principle holds because the choices at each stage are independent and exhaustive, and the problem's constraints ensure no overlap or omission in the count.