1
$\begingroup$

There are $n$ stairs and a person standing at the bottom wants to reach the top. The person can climb either 1 stair or 2 stairs every time. What is the total number of ways they can reach the top?

There are many ways to do this by using code. But when I first read this problem was to use a combinatorics approach. This problems seems very similar to a "stars and bars" problem. The stars would be the number of stairs and the bars would be the number of steps that be taken.

Given this is the case, my solution is simply: ${(n)+(2-1)}\choose{1}$.

Is the concept of stars and bars the simplest approach to solving this problem or is there a simpler combinatorics concept at play here and if so, how do I recognize such things? By simple, I mean can I solve this problem by simpler computation than combinatorics (even if it requires some sort of brute force method)?

$\endgroup$
  • $\begingroup$ We discourage "please check whether my answer is correct" questions, as only "yes/no" answers are possible, which won't help you or future visitors. See here and here. Can you edit your post to ask about a specific conceptual issue you're uncertain about? As a rule of thumb, a good conceptual question should be useful even to someone who isn't looking at the problem you happen to be working on. If you just need someone to check your work, you might seek out a friend, classmate, or teacher. $\endgroup$ – D.W. Nov 8 '16 at 23:09
  • $\begingroup$ I see, well I have edited the question. Is it more apt? $\endgroup$ – Jonathan Nov 8 '16 at 23:11
  • $\begingroup$ What does "most optimal" mean? Anyway, I suggest you work through the approach suggested in my answer. $\endgroup$ – D.W. Nov 8 '16 at 23:11
3
$\begingroup$

You can usually check whether a solution is correct by running it on some small examples. For example, say you have a stair with two steps; how many ways are there to reach the top?

Well, you can either take $1 + 1$ steps or just a single step of $2$. Unfortunately, this gives a counter-example for the proposed solution.

However, fear-not, there is still a simple combinatorial interpretation here. Since each step is either $1$ or $2$ steps, then your problem revolves down to finding all sums of the form $1 + 2 + 1 + 1 + \dots + 2 = n$. In other words, you're looking for the compositions of $n$ using just $1$ and $2$.

To solve this problem, try to work through the problem top-down. Say you are at the top ($n$) of the stair, what are the two possible choices you could have made in your final step? Well, you could have either taken a single step from $n-1$ or a double-step from $n-2$; these are necessarily disjoint since they end at different steps. Therefore, the total number of ways to reach $n$ is the same as the total number of ways to reach $n-1$ along with the total number of ways to reach $n-2$. Now, this characterizes a familiar recurrence, so I'll leave the rest to you.

$\endgroup$
3
$\begingroup$

Let $W(n)$ be the number of ways you can reach step $n$ by 1- or 2-step moves. Then $W(1)=1, W(2)=2$ (by two 1-step moves or one 2-step move). Then to reach $n$ height, your last move is either a 1-step move from height $n-1$ or a 2-step move from height $n-2$, giving us the recurrence $W(n) = W(n-1) + W(n-2)$. I'll leave the solution of this recurrence to you. (Hint: it should be familiar.)

$\endgroup$
2
$\begingroup$

Hint: a good way to sanity-check your answer is to check your formula on small values of $n$ to see if it seems to give the right number for them. This is always a good first step. Then, if it appears to give the right answer for small numbers (say $n < 10$), the next step is to write out a proof of correctness: say, proof by induction.

$\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.