A stairway consists of 100 steps which can be ascended by one step at a time, two steps, three steps or, by four steps.
Determine the total number of ways to ascend the staircase.
The program calculates the separate ways of combining different numbers of four, three, two and one step strides. For each of these it calculates the diffent orders in which such numbers can be arranged.
clearvars,clc
ways=sym(0);
fct(1)=sym(1);
for i=2:100
fct(i)=fct(i-1)*sym(i);
end
fct(101)=sym(1);
for fours=0:25
r=100-4*fours;
fo=fours;
if fours==0 fo=101;
end
for threes=0:floor(r/3)
r=r-3*threes;
th=threes;
if th==0 th=101;
end
for twos=0:floor(r/2)
tw=twos;
if tw==0 tw=101;
end
r=r-2*twos;
ones=r;
on=ones;
if on==0 on=101;
end
ways=ways+fct(sum([fours threes twos ones]))/prod([fct(fo) fct(th) fct(tw) fct(on)]);
r=r+2*twos;
end
r=r+3*threes;
end
end
ways
Note that 101 substitutes for zero in accessing the fct array of factorials.
finds
ways =
17,943,803,336,550,012,914,104,102,513
almost 18 octillion.
Broken down by number of 4-step spans:
4-step
spans number of ways
0 180396380815100901214157639
1 954928556342366067274633529
2 2373653862659491588398782460
3 3682063267098381284270263732
4 3995652589735241848122196280
5 3222656601776583191365005378
6 2003488087676279973735157464
7 982664396367673758866090769
8 386034592872635754784747569
9 122624859093830702676066285
10 31664370713601424024336682
11 6659252162938648591143618
12 1139311453858724637234556
13 157922369138174060067382
14 17608103781144296392200
15 1562523525599984043852
16 108731056292501153942
17 5815098902459235186
18 232593221015248744
19 6702103740084000
20 131955035141160
21 1641619479885
22 11398005580
23 35404395
24 30225
25 1
-----------------------------
17943803336550012914104102513
|
|
Posted by Charlie
on 2023-03-07 09:38:03 |
computer solution
