find the number of ways to reach the nth stair

Question

I have to find the number of ways to reach the $n$th stair step (where $n=20$) by taking at most 5 steps at a time, with the restriction that the $5$th, $10$th, and $15$th should not be accessed.

Working

I know how to find the number of way to reach the $n$th step given at most $k$ steps for this. If $n=20$ and $k=5$, the total number of ways are $400096$, but I don't know how to count if exceptions are given, like the $5$th, $10$th, and $15$th steps should not be accessed.

Answer 1

First a question: If we ignore the "must not touch 5th, 10th, 15th steps" constraint, you seem to have a way to calculate $f(n=20,k=5) = 400096$. How do you do that? One can obviously write a simple recurrence (dynamic program, loop) - is that how you do it? Or do you have some other way?

Anyway, the answer: assuming you can calculate $f(n,k)$ for other values, then the problem with the constraint can simply be handled by inclusion exclusion. Let $P_5, P_{10}, P_{15}$ be the set of paths that touch each of the name restricted step (and satisfying $n=20, k=5$), then your answer is

$$f(20,5) - |P_5| - |P_{10}| - |P_{15}| + |P_5 \cap P_{10}| + |P_5 \cap P_{15}| + |P_{10} \cap P_{15}| - |P_5 \cap P_{10} \cap P_{15}| $$

Calculating each of the terms is easy. E.g.

• $|P_5| = f(5,5) \times f(15,5)$ because you must first reach the 5th step (there being $f(5,5)$ ways to do so), then continue for 15 more ($f(15,5)$ ways to do so);

• $|P_{10}| = f(10,5) \times f(10,5)$ because you must first reach the 10th step, then continue for 10 more;

• $|P_5 \cap P_{10}| = f(5,5)\times f(5,5)\times f(10,5)$;

• $|P_5 \cap P_{10} \cap P_{15}| = f(5,5) \times f(5,5)\times f(5,5)\times f(5,5)$ etc.

• In each case, by specifying which (forbidden) step(s) you must touch, you have broken up the 20-step path into segments, and you can calculate $f(n',k)$ for each segment of length $n'$ and just multiply them all together.

Answer 2

Your problem can be set up recursively.

Let $A=\{n : $ we must avoid stair $n \}$.

Let $b_n$ be the number of ways to reach stair $n$.

You will need to find initial conditions for $b_0$ through $b_4$. (Note: $b_0 = 1$. There is $1$ way to be at the foot of the stairs.)

Then our recursion will be, for $n\ge 5$: $$b_n = \left\{ \begin{array}{cc} 0 & {\rm if\:} n\in A\\b_{n-1}+b_{n-2}+b_{n-3}+b_{n-4}+b_{n-5}& \rm otherwise\end{array}\right.$$