Question 342272: In how many ways can you walk up a stairway that has 7 steps if you can take 1 or 2 steps at a time.
Answer by Theo(13342)   (Show Source):
You can put this solution on YOUR website! 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
|
|
|
