Climbing Stairs

[BMAD]

How many different paths can I make up a flight of 20 stairs if I can take the steps either one at a time or two at a time (in any order)?

[rocdocmac]

Spoiler

10946

(Fibonacci #22)

 

[harey]

Same as rocdocmac

Spoiler

Before reaching 20 (n) stairs, you can either:
- go up 1 stair  and apply the solution for 19 (n-1) stairs -- or --
- go up 2 stairs and apply the solution for 18 (n-2) stairs.

This gives the formula: f(n)=f(n-1)+f(n-2). (Looks like Fibonacci...)

For 1 stair,  there is 1 possibility.
For 2 stairs, there is 2 possibilities. => Fibonacci

Combinatorics:

Spoiler

Maximum number of double stair steps is given by the integer division of number of stairs by 2.
Complete sigle stair steps.
Take all permutations with repetitions:

Spoiler

from math import factorial as MF

FIBO_1,FIBO_2=1,1

# staircase will take the values 1,2,3,...20 (yes, 20)
for staircase in range(1,21):
  FIBO_1,FIBO_2=FIBO_2,FIBO_1+FIBO_2
  combi=0
  doubles=staircase//2

  # double will take values 0,1,2...doubles (see staircase)
  for double in range(0,doubles+1):
    single=staircase-double*2
    combi=combi+MF(single+double)//MF(double)//MF(single)
  # remove # in the next line for intermediate results
  # print(staircase,single,double,combi)

  print('stairs =',staircase,'combinations =',combi,'Fibonacci =',FIBO_1)
 

Output:

Spoiler

stairs = 1 combinations = 1 Fibonacci = 1
stairs = 2 combinations = 2 Fibonacci = 2
stairs = 3 combinations = 3 Fibonacci = 3
stairs = 4 combinations = 5 Fibonacci = 5
stairs = 5 combinations = 8 Fibonacci = 8
stairs = 6 combinations = 13 Fibonacci = 13
stairs = 7 combinations = 21 Fibonacci = 21
stairs = 8 combinations = 34 Fibonacci = 34
stairs = 9 combinations = 55 Fibonacci = 55
stairs = 10 combinations = 89 Fibonacci = 89
stairs = 11 combinations = 144 Fibonacci = 144
stairs = 12 combinations = 233 Fibonacci = 233
stairs = 13 combinations = 377 Fibonacci = 377
stairs = 14 combinations = 610 Fibonacci = 610
stairs = 15 combinations = 987 Fibonacci = 987
stairs = 16 combinations = 1597 Fibonacci = 1597
stairs = 17 combinations = 2584 Fibonacci = 2584
stairs = 18 combinations = 4181 Fibonacci = 4181
stairs = 19 combinations = 6765 Fibonacci = 6765
stairs = 20 combinations = 10946 Fibonacci = 10946