2
$\begingroup$

A child is running up a staircase with n steps and can hop either 1 step, 2 steps, or 3 steps at a time. Count how many possible ways the child can run up the stairs.

This is a problem on Cracking the Code Inteview but I'm wondering if there's a way to solve this with combinatorics; essentially directly calculate the answer without dynamic programming.

$\endgroup$
  • $\begingroup$ You may need to solve $x^3-x^2-x-1=0$ $\endgroup$ – Henry Jul 13 '17 at 20:54
3
$\begingroup$

You can certainly solve the recurrence explicitly. If $A(n)$ is the ordered number of ways to sum to $n$ using $1,2,3$ we have $A(n)=A(n-1)+A(n-2)+A(n-3)$, the Tribonacci numbers but offset by $2$ because in your case A(0)=$A(1)=1$. They are given in OEIS A000073. There are various forms of a closed form solution given. The usual approach to homogeneous recurrence relations applies, assume a solution of the form $r^n$. Plugging that in gives $r^3=r^2+r+1$, which has three roots $r_1,r_2,r_3$. The general solution is $ar_1^n+br_2^n+cr_3^n$. You find $a,b,c$ from the initial conditions.

$\endgroup$

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.