If Abdur Rehman likes to walk up the stairs climbing either one or three stairs in each step, in how many ways can he walk up ten stairs?
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
Good approach of listing out the possible ways.
Once the number of 3's and 1's is fixed, do you know how to use stars and bars?
Nice display of information. If Abdur can climb one, two or three steps at a time there would be 2 7 4 ways of him walking up the ten stairs, (I think).
Log in to reply
Did you do the same way?
Log in to reply
2 years ago when I didn't know much combinatorics I also used to problems that way. But now simply I did 10C0+8C1+6C2+4C3
We can form an equation as a + 3 b = 1 0 . So, we obtain 4 solutions ;
b = 0 , a = 1 0
b = 1 , a = 7
b = 2 , a = 4
b = 3 , a = 1
Here the values of b indicate the number of steps in which he climbed up 3 stairs and a indicates the number of steps in which he climbed up 1 stair.
So for case I we have 1 0 steps of 1 stair hence permutations = 1 0 ! × 0 ! 1 0 ! = 1
For case I I we have 7 steps of 1 stair and 1 step of 3 stairs hence permutations = 7 ! × 1 ! 8 ! = 8
Similarly for cases I I I and I V we have permutations = 4 ! × 2 ! 6 ! = 1 5 and 3 ! × 1 ! 4 ! = 4
Adding all the cases : 1 + 8 + 1 5 + 4 = 2 8
Good approach applying stars and bars.
How would we solve this problem more generally? Like if there were 100 steps?
Good approach applying stars and bars.
How would we solve this problem more generally? Like if there were 100 steps?
Log in to reply
@Calvin Lin To solve it more generally I first thought of generating functions but I think that wouldn' t help much.. Sir can you suggest me the generalised form of the question...
Problem Loading...
Note Loading...
Set Loading...
Since I'm not so good at combinatorics, I chose to do it in a no-brainer method, i.e., by simple counting.
Hence, total ways to do it is = 1 + 8 + 1 5 + 4 = 2 8