Question 342272
The total number of possible ways can be found as follows:


Find the possible combinations you can use to get to the number of steps.

Fin the possible number of ways each combination can be done.


Example:


Number of steps = 3

This can be done using the following possible combinations.

111
21


Add each number in each string and you get a total of 3.


111 can be done in 1 way.


21 can be done in 2 ways.


They would be 12 and 21.


Total number of possible ways to get up a flight of 3 steps is 3.


Those ways are:


111
12
21


Go to a flight of 4 steps.


Total number of possible combinations involving either 1 step or 2 steps are:


1111
22
211


you can do 1111 only 1 way.


you can do 22 only 1 way.


You can do 211 in 3 ways.


Those ways are:


211
121
112


There is therefore a total of 5 ways to get up a flight of 4 steps.


Those ways are


1111
22
211
121
112


Go to a flight of 5 steps.


Total number of possible combinations involving either 1 step or 2 steps are:


11111
1112
122


11111 can be done in only 1 way.


1112 can be done in 4 ways.


Those ways are:


1112
1121
1211
2111


122 can be done in 3 ways.


Those ways are:


122
212
221


Total number of ways to get up a flight of 5 steps is equal to:


1 + 4 + 3 = 8 ways


Those ways are:


11111
1112
1121
1211
2111
122
212
221


We could do 6, but you should have the idea by now, so we'll jump to 7 steps.


Possible combinations using only 1 step and 2 steps are:


1111111
111112
11122
1222


If you sum the digits in each string, you will get a total of 7 for each.


1111111 can be done in only 1 way.


111112 can be done in 6 ways.


Those ways are:


111112
111121
111211
112111
121111
211111


11122 can be done in 10 ways.


Those ways are:


11122
11212
11221
12112
12121
12211
21112
21121
21211
22111


1222 can be done in 4 ways.


those ways are:


1222
2122
2212
2221


The total number of ways you can get up a flight of 7 steps if you take 1 step at a time or 2 steps at a time would therefore be equal to:


1 + 6 + 10 + 4 = 21 ways.


There might be an easier way to do this but I haven't figured it out.


This way works, even though it does involve a little work.


How you determine the number of ways for each of the combinations is as follows:


Suppose one of the possible combinations for getting up a flight of 7 steps is as follows:


11122


That 3 of your strides that take 1 step at a time, and 2 of your strides that take 2 steps at a time.


You have taken a total of 5 strides.


The formula to determine how many possible ways you can do this is as follows:


Let n = total number of strides.
Let x = number of strides that take 2 steps at a time.
Let n-x = number of strides that take 1 step at a time.


The formula is n! / (x! * (n-x)!)


You should recognize that formula as the number of combinations formula (order is not important).


In this instance:


n = total number of strides = 5
x = total number of strides taking 2 steps at a time = 2
(n-x) = total number of strides taking 1 step at a time = 3.


The formula becomes:


5!/(2! * 3!)


This translates to 5*4*3! / (2*1*3!)


The 3! cancels out and you get:


5*4 / 2*1


This simplifies to 5*2 / 1 which equals 10.


That's how we got 10 possible ways to get the combination of 2 strides taking 2 steps at a time and 3 strides taking 1 step at a time which was shown as:


11122


We then determined what those possible ways could be.


This can be done with smaller numbers.   It's much more difficult to do with larger number without the aid of a computer.


Those possible ways were:


11122
11212
11221
12112
12121
12211
21112
21121
21211
22111