2
$\begingroup$

A stair flight has 10 steps. A kid can move in jumps of 1, 2 or 3 steps. Assume the kid starts on the floor (step 0), and always has to end in step 10 because there is a door that needs to be open. In how many possible ways can the kid reach the last step?

For example, the kid may do 8 "one step" jumps, and 1 "two steps" jump. There would be 9 possible ways of reaching step 10 this way. (211111111,121111111, ...etc...)

The approach I took is that considering the three types of jump:

  • j1 : 1 step.
  • j2 : 2 steps.
  • j3 : 3 steps.

I found these 12 possible ways of doing the stair in 10 steps:

j1x10 j2x0 j3x0
j1x8  j2x1 j3x0
j1x7  j2x0 j3x1
j1x6  j2x2 j3x0
j1x5  j2x1 j3x1
j1x4  j2x3 j3x0
j1x4  j2x0 j3x2
j1x3  j2x2 j3x1
j1x2  j2x4 j3x0
j1x1  j2x0 j3x3
j1x0  j2x2 j3x2
j1x0  j2x5 j3x0

The first possibility would be ten jumps by doing j1*10 j2*0 j3*0, that would be 10!/10! = 1 possibility.

Next possibility would be nine jumps by doing j1x8 j2x1 j3x0, 9!/(8!*1!) = 9 possibilities.

Next would be eight jumps by doing j1x6 j2x2 j3x0, 8!/(6!*2!) = 28 possibilities. .. etc..

The sum of all the possibilities would be the result.

Even if the result is right, I found the approach very rough, and difficult to scale to a 100 steps stair flight. Which would be a better approach for this problem that can be applied to a 100 steps stair?

Thanks.

$\endgroup$
5
$\begingroup$

You will end up getting a recursion. Denote by $f_n$ the number of ways of going up $n$ stairs.

It is clear $f_1=1, f_2=2,f_3=4$ (if not clear easily checkable).

We now get the recursion $f_n=f_{n-1}+f_{n-2}+f_{n-3}$. This is because the number of ascensions ending with a 1-step is $f_{n-1}$,the number of ascensions ending with a 2-step is $f_{n-2}$,the number of ascensions ending with a 3-step is $f_{n-3}$.

so now all you have to do is follow the recursion up to $f_{10}$

looking at oeis $f_n=t(n+2)$ where $t(n)$ is the $n$'th tribonacci number. So $f_{10}=274$.

also according to oeis:

$$f_n=\frac{3(\sqrt[3]{19+3\sqrt{33}}+\sqrt[3]{19-3 \sqrt{33}}+1)}{3^n(\sqrt[3]{19+3\sqrt{33}}^2+\sqrt[3]{19-3 \sqrt{33}}^2+4)}$$

Another way to compute $f_n$ using the recursion is to observe that it has a nice generating function. If one rewrites the formal power series $F(x):=\sum_{n=0}^\infty f_n x^n$ using the recursion, then we can solve to find $F(x)=(1-x-x^2-x^3)^{-1}$. Since this has coefficients of $f_n$, we can read them off quickly if we ask WolframAlpha; this gives the first ten terms as $$F(x)=1+x+2 x^2+4 x^3+7 x^4+13 x^5+24 x^6+44 x^7+81 x^8+149 x^9+274 x^{10}+\ldots$$ and we see that each coefficient is the sum of the three preceeding it. If we want $f_{100}$ in particular, we can ask WolframAlpha and receive

$$f_{100}=180396380815100901214157639\approx 1.8\times^{26}=180\text{ septillion}.$$

$\endgroup$
  • $\begingroup$ Great. Thanks for that. $\endgroup$ – NullOrEmpty Aug 26 '14 at 14:13
  • $\begingroup$ Added a bit on the generating function of $f_n$. $\endgroup$ – Semiclassical Aug 26 '14 at 18:04
  • $\begingroup$ Can someone double check the formula for $f_n$? Right now, it looks like $f_n = \frac{C}{3^n}$, which decays to $0$ as $n \to \infty$. $\endgroup$ – JimmyK4542 Aug 26 '14 at 18:06
  • $\begingroup$ the cube roots are squared in the denominator. $\endgroup$ – Jorge Fernández Hidalgo Aug 27 '14 at 21:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.