Menu Close

In-how-many-ways-can-you-go-up-a-staircase-with-20-steps-if-you-take-one-two-or-three-steps-at-a-time-

Tinku Tara 0 Comments
Pin




Question Number 166770 by mr W last updated on 27/Feb/22
In how many ways can you go up a staircase with 20 steps if you take one, two or three steps at a time?
$${In}\:{how}\:{many}\:{ways}\:{can}\:{you}\:{go}\:{up}\:{a}\: \\ $$$${staircase}\:{with}\:\mathrm{20}\:{steps}\:{if}\:{you}\:{take}\: \\ $$$${one},\:{two}\:{or}\:{three}\:{steps}\:{at}\:{a}\:{time}? \\ $$
Commented by MJS_new last updated on 27/Feb/22
is it 121415?
$$\mathrm{is}\:\mathrm{it}\:\mathrm{121415}? \\ $$
Commented by mr W last updated on 28/Feb/22
i havn′t calculated it yet sir.
$${i}\:{havn}'{t}\:{calculated}\:{it}\:{yet}\:{sir}. \\ $$
Commented by peter frank last updated on 28/Feb/22
very tough
$$\mathrm{very}\:\mathrm{tough}\: \\ $$
Commented by MJS_new last updated on 28/Feb/22
not tough. just arrange as follows: 333333 2 333333 11 33333 221 33333 2111 33333 11111 3333 2222 3333 22211 ... then count the permutations of each row
$$\mathrm{not}\:\mathrm{tough}.\:\mathrm{just}\:\mathrm{arrange}\:\mathrm{as}\:\mathrm{follows}: \\ $$$$\mathrm{333333}\:\mathrm{2} \\ $$$$\mathrm{333333}\:\mathrm{11} \\ $$$$\mathrm{33333}\:\mathrm{221} \\ $$$$\mathrm{33333}\:\mathrm{2111} \\ $$$$\mathrm{33333}\:\mathrm{11111} \\ $$$$\mathrm{3333}\:\mathrm{2222} \\ $$$$\mathrm{3333}\:\mathrm{22211} \\ $$$$… \\ $$$$\mathrm{then}\:\mathrm{count}\:\mathrm{the}\:\mathrm{permutations}\:\mathrm{of}\:\mathrm{each}\:\mathrm{row} \\ $$
Commented by mr W last updated on 28/Feb/22
MJS sir: 121415 is correct. i got the same.
$${MJS}\:{sir}: \\ $$$$\mathrm{121415}\:{is}\:{correct}.\:{i}\:{got}\:{the}\:{same}. \\ $$
Commented by MJS_new last updated on 28/Feb/22
thank you!
$$\mathrm{thank}\:\mathrm{you}! \\ $$
Answered by nadovic last updated on 27/Feb/22
One Step: 20 ways Two Steps: 10 ways Three Steps: 7 ways Number of Ways = 20 + 10 + 7 = 37 ways
$$\mathrm{One}\:\mathrm{Step}:\:\mathrm{20}\:{ways} \\ $$$$\mathrm{Two}\:\mathrm{Steps}:\:\mathrm{10}\:{ways} \\ $$$$\mathrm{Three}\:\mathrm{Steps}:\:\mathrm{7}\:{ways} \\ $$$$ \\ $$$${Number}\:{of}\:{Ways}\:=\:\mathrm{20}\:+\:\mathrm{10}\:+\:\mathrm{7} \\ $$$$\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:=\:\mathrm{37}\:{ways} \\ $$$$ \\ $$
Commented by mr W last updated on 27/Feb/22
wrong!
$${wrong}! \\ $$
Answered by nadovic last updated on 28/Feb/22
= ^(20) P_1 +^(20) P_2 +^(20) P_3 = 7240 ways
$$\:\:\:\:\:\:=\:\:^{\mathrm{20}} \mathrm{P}_{\mathrm{1}} \:+\:^{\mathrm{20}} \mathrm{P}_{\mathrm{2}} \:+\:^{\mathrm{20}} \mathrm{P}_{\mathrm{3}} \\ $$$$\:\:\:\:\:=\:\mathrm{7240}\:{ways} \\ $$
Commented by MJS_new last updated on 28/Feb/22
maybe test your hypothetical formula with an easy example? 5 stairs: 32 23 311 131 113 221 212 122 2111 1211 1121 1112 11111 13 possibilities 6 stairs: 33 321 312 231 213 132 123 3111 1311 1131 1113 222 2211 2121 2112 1221 1212 1122 21111 12111 11211 11121 11112 111111 24 possibilities ...
$$\mathrm{maybe}\:\mathrm{test}\:\mathrm{your}\:\mathrm{hypothetical}\:\mathrm{formula}\:\mathrm{with} \\ $$$$\mathrm{an}\:\mathrm{easy}\:\mathrm{example}? \\ $$$$\mathrm{5}\:\mathrm{stairs}: \\ $$$$\mathrm{32}\:\mathrm{23}\:\mathrm{311}\:\mathrm{131}\:\mathrm{113}\:\mathrm{221}\:\mathrm{212}\:\mathrm{122}\:\mathrm{2111}\:\mathrm{1211} \\ $$$$\mathrm{1121}\:\mathrm{1112}\:\mathrm{11111} \\ $$$$\mathrm{13}\:\mathrm{possibilities} \\ $$$$\mathrm{6}\:\mathrm{stairs}: \\ $$$$\mathrm{33}\:\mathrm{321}\:\mathrm{312}\:\mathrm{231}\:\mathrm{213}\:\mathrm{132}\:\mathrm{123}\:\mathrm{3111}\:\mathrm{1311}\:\mathrm{1131} \\ $$$$\mathrm{1113}\:\mathrm{222}\:\mathrm{2211}\:\mathrm{2121}\:\mathrm{2112}\:\mathrm{1221}\:\mathrm{1212}\:\mathrm{1122} \\ $$$$\mathrm{21111}\:\mathrm{12111}\:\mathrm{11211}\:\mathrm{11121}\:\mathrm{11112}\:\mathrm{111111} \\ $$$$\mathrm{24}\:\mathrm{possibilities} \\ $$$$… \\ $$
Answered by mr W last updated on 01/Mar/22
let′s look at the case that we make n moves to go up the staircase. each move can be of one, two or three steps. the number of ways to go up the staircase in n moves is the number of integer solutions of the equation a_1 +a_2 +a_3 +...+a_n =20 with 1≤a_i ≤3. using generating function it is the coefficient of the x^(20) term in the expansion of (x+x^2 +x^3 )^n . (x+x^2 +x^3 )^n =x^n (1+x+x^2 )^n =((x^n (1−x^3 )^n )/((1−x)^n )) =x^n {Σ_(k=0) ^n (−1)^k C_k ^n x^(3k) }{Σ_(m=0) ^∞ C_(n−1) ^(m+n−1) x^m } x^n x^(3k) x^m =x^(n+3k+m) =^! x^(20) n+3k+m=^! 20 ⇒3k+m=20−n 0≤k≤n, m≥0 ⇒7≤n≤20 (this is clear, we need at least 7 moves and at most 20 moves to go up the staircase.) example n=10: k=0, m=10 ⇒C_0 ^(10) C_9 ^(19) =92378 k=1, m=7 ⇒−C_1 ^(10) C_9 ^(16) =−114400 k=2, m=4 ⇒C_2 ^(10) C_9 ^(13) =32175 k=3, m=1 ⇒−C_3 ^(10) C_9 ^(10) =−1200 that means the coef. of x^(20) is 92378−114400+32175−1200=8953 the results for all values of n see following table. the total result is 121415. i.e. there are 121415 ways to go up the staircase.
$${let}'{s}\:{look}\:{at}\:{the}\:{case}\:{that}\:{we}\:{make}\:{n}\: \\ $$$${moves}\:{to}\:{go}\:{up}\:{the}\:{staircase}.\:{each}\: \\ $$$${move}\:{can}\:{be}\:{of}\:{one},\:{two}\:{or}\:{three}\: \\ $$$${steps}. \\ $$$$ \\ $$$${the}\:{number}\:{of}\:{ways}\:{to}\:{go}\:{up}\:{the} \\ $$$${staircase}\:{in}\:{n}\:{moves}\:{is}\:{the}\:{number} \\ $$$${of}\:{integer}\:{solutions}\:{of}\:{the}\:{equation} \\ $$$${a}_{\mathrm{1}} +{a}_{\mathrm{2}} +{a}_{\mathrm{3}} +…+{a}_{{n}} =\mathrm{20} \\ $$$${with}\:\mathrm{1}\leqslant{a}_{{i}} \leqslant\mathrm{3}. \\ $$$${using}\:{generating}\:{function}\:{it}\:{is}\:{the}\: \\ $$$${coefficient}\:{of}\:{the}\:{x}^{\mathrm{20}} \:{term}\:{in}\:{the} \\ $$$${expansion}\:{of}\:\left({x}+{x}^{\mathrm{2}} +{x}^{\mathrm{3}} \right)^{{n}} . \\ $$$$ \\ $$$$\left({x}+{x}^{\mathrm{2}} +{x}^{\mathrm{3}} \right)^{{n}} \\ $$$$={x}^{{n}} \left(\mathrm{1}+{x}+{x}^{\mathrm{2}} \right)^{{n}} \\ $$$$=\frac{{x}^{{n}} \left(\mathrm{1}−{x}^{\mathrm{3}} \right)^{{n}} }{\left(\mathrm{1}−{x}\right)^{{n}} } \\ $$$$={x}^{{n}} \left\{\underset{{k}=\mathrm{0}} {\overset{{n}} {\sum}}\left(−\mathrm{1}\right)^{{k}} {C}_{{k}} ^{{n}} {x}^{\mathrm{3}{k}} \right\}\left\{\underset{{m}=\mathrm{0}} {\overset{\infty} {\sum}}{C}_{{n}−\mathrm{1}} ^{{m}+{n}−\mathrm{1}} {x}^{{m}} \right\} \\ $$$${x}^{{n}} {x}^{\mathrm{3}{k}} {x}^{{m}} ={x}^{{n}+\mathrm{3}{k}+{m}} \overset{!} {=}{x}^{\mathrm{20}} \\ $$$${n}+\mathrm{3}{k}+{m}\overset{!} {=}\mathrm{20} \\ $$$$\Rightarrow\mathrm{3}{k}+{m}=\mathrm{20}−{n} \\ $$$$\mathrm{0}\leqslant{k}\leqslant{n},\:{m}\geqslant\mathrm{0} \\ $$$$\Rightarrow\mathrm{7}\leqslant{n}\leqslant\mathrm{20}\:\left({this}\:{is}\:{clear},\:{we}\:{need}\:{at}\right. \\ $$$${least}\:\mathrm{7}\:{moves}\:{and}\:{at}\:{most}\:\mathrm{20}\:{moves} \\ $$$$\left.{to}\:{go}\:{up}\:{the}\:{staircase}.\right) \\ $$$$ \\ $$$${example}\:{n}=\mathrm{10}: \\ $$$${k}=\mathrm{0},\:{m}=\mathrm{10}\:\Rightarrow{C}_{\mathrm{0}} ^{\mathrm{10}} {C}_{\mathrm{9}} ^{\mathrm{19}} =\mathrm{92378} \\ $$$${k}=\mathrm{1},\:{m}=\mathrm{7}\:\Rightarrow−{C}_{\mathrm{1}} ^{\mathrm{10}} {C}_{\mathrm{9}} ^{\mathrm{16}} =−\mathrm{114400} \\ $$$${k}=\mathrm{2},\:{m}=\mathrm{4}\:\Rightarrow{C}_{\mathrm{2}} ^{\mathrm{10}} {C}_{\mathrm{9}} ^{\mathrm{13}} =\mathrm{32175} \\ $$$${k}=\mathrm{3},\:{m}=\mathrm{1}\:\Rightarrow−{C}_{\mathrm{3}} ^{\mathrm{10}} {C}_{\mathrm{9}} ^{\mathrm{10}} =−\mathrm{1200} \\ $$$${that}\:{means}\:{the}\:{coef}.\:{of}\:{x}^{\mathrm{20}} \:{is} \\ $$$$\mathrm{92378}−\mathrm{114400}+\mathrm{32175}−\mathrm{1200}=\mathrm{8953} \\ $$$$ \\ $$$${the}\:{results}\:{for}\:{all}\:{values}\:{of}\:{n}\:{see} \\ $$$${following}\:{table}. \\ $$$$ \\ $$$${the}\:{total}\:{result}\:{is}\:\mathrm{121415}.\:{i}.{e}.\:{there} \\ $$$${are}\:\mathrm{121415}\:{ways}\:{to}\:{go}\:{up}\:{the}\:{staircase}. \\ $$
Commented by mr W last updated on 28/Feb/22
Commented by Tawa11 last updated on 28/Feb/22
Great sir
$$\mathrm{Great}\:\mathrm{sir} \\ $$
Answered by mr W last updated on 02/Mar/22
AN OTHER METHOD let′s say there are N(n) ways to go up a staircase with n steps. if we make a move with one step, then there are n−1 steps remaining and there are N(n−1) ways to go up the remaining steps. if we make a move with two steps, then there are n−2 steps remaining and there are N(n−2) ways to go up the remaining steps. similarly if we make a move with three steps, then there are N(n−3) ways to go up the remaining steps. therefore we have following recurrence relation: N(n)=N(n−1)+N(n−2)+N(n−3) we also have N(1)=1 N(2)=2 N(3)=4 applying the recurrence relation above, we get N(4)=7 N(5)=13 N(6)=24 N(7)=44 N(8)=81 N(9)=149 N(10)=274 N(11)=504 N(12)=927 N(13)=1705 N(14)=3136 N(15)=5768 N(16)=10609 N(17)=19513 N(18)=35890 N(19)=66012 N(20)=121415 ✓ we can also find a closed formula for N(n) by solving following characteristic equation λ^3 −λ^2 −λ−1=0 let λ=s+(1/3) s^2 −(4/3)s−((38)/(27))=0 with u=((3(√(33))+19))^(1/3) , v=((3(√(33))−19))^(1/3) λ_1 =(1/3)(1+u−v) λ_(2,3) =(1/6)[2−u+v±(√3)(u+v)i] ⇒N(n)=Aλ_1 ^n +Bλ_2 ^n +Cλ_3 ^n N(0)=N(3)−N(2)−N(1)=1 N(−1)=N(2)−N(1)−N(0)=0 N(1)=Aλ_1 +Bλ_2 +Cλ_3 =1 N(0)=A+B+C=1 N(−1)=(A/λ_1 )+(B/λ_2 )+(C/λ_3 )=0 [(λ_1 ,λ_2 ,λ_3 ),(1,1,1),((1/λ_1 ),(1/λ_2 ),(1/λ_3 )) ] ((A),(B),(C) ) = ((1),(1),(0) ) ⇒ ((A),(B),(C) ) = [(λ_1 ,λ_2 ,λ_3 ),(1,1,1),((1/λ_1 ),(1/λ_2 ),(1/λ_3 )) ]^(−1) ((1),(1),(0) )
$$\boldsymbol{{AN}}\:\boldsymbol{{OTHER}}\:\boldsymbol{{METHOD}} \\ $$$${let}'{s}\:{say}\:{there}\:{are}\:{N}\left({n}\right)\:{ways}\:{to}\:{go}\:{up} \\ $$$${a}\:{staircase}\:{with}\:{n}\:{steps}.\:{if}\:{we}\:{make} \\ $$$${a}\:{move}\:{with}\:{one}\:{step},\:{then}\:{there}\:{are} \\ $$$${n}−\mathrm{1}\:{steps}\:{remaining}\:{and}\:{there}\:{are} \\ $$$${N}\left({n}−\mathrm{1}\right)\:{ways}\:{to}\:{go}\:{up}\:{the}\:{remaining} \\ $$$${steps}.\:{if}\:{we}\:{make}\:{a}\:{move}\:{with} \\ $$$${two}\:{steps},\:{then}\:{there}\:{are}\:{n}−\mathrm{2}\:{steps}\: \\ $$$${remaining}\:{and}\:{there}\:{are}\:{N}\left({n}−\mathrm{2}\right)\: \\ $$$${ways}\:{to}\:{go}\:{up}\:{the}\:{remaining}\:{steps}.\: \\ $$$${similarly}\:{if}\:{we}\:{make}\:{a}\:{move}\:{with}\: \\ $$$${three}\:{steps},\:{then}\:{there}\:{are}\:{N}\left({n}−\mathrm{3}\right)\: \\ $$$${ways}\:{to}\:{go}\:{up}\:{the}\:{remaining}\:{steps}.\: \\ $$$${therefore}\:{we}\:{have}\:{following} \\ $$$${recurrence}\:{relation}: \\ $$$${N}\left({n}\right)={N}\left({n}−\mathrm{1}\right)+{N}\left({n}−\mathrm{2}\right)+{N}\left({n}−\mathrm{3}\right) \\ $$$${we}\:{also}\:{have}\: \\ $$$${N}\left(\mathrm{1}\right)=\mathrm{1} \\ $$$${N}\left(\mathrm{2}\right)=\mathrm{2} \\ $$$${N}\left(\mathrm{3}\right)=\mathrm{4} \\ $$$${applying}\:{the}\:{recurrence}\:{relation}\:{above},\: \\ $$$${we}\:{get} \\ $$$${N}\left(\mathrm{4}\right)=\mathrm{7} \\ $$$${N}\left(\mathrm{5}\right)=\mathrm{13} \\ $$$${N}\left(\mathrm{6}\right)=\mathrm{24} \\ $$$${N}\left(\mathrm{7}\right)=\mathrm{44} \\ $$$${N}\left(\mathrm{8}\right)=\mathrm{81} \\ $$$${N}\left(\mathrm{9}\right)=\mathrm{149} \\ $$$${N}\left(\mathrm{10}\right)=\mathrm{274} \\ $$$${N}\left(\mathrm{11}\right)=\mathrm{504} \\ $$$${N}\left(\mathrm{12}\right)=\mathrm{927} \\ $$$${N}\left(\mathrm{13}\right)=\mathrm{1705} \\ $$$${N}\left(\mathrm{14}\right)=\mathrm{3136} \\ $$$${N}\left(\mathrm{15}\right)=\mathrm{5768} \\ $$$${N}\left(\mathrm{16}\right)=\mathrm{10609} \\ $$$${N}\left(\mathrm{17}\right)=\mathrm{19513} \\ $$$${N}\left(\mathrm{18}\right)=\mathrm{35890} \\ $$$${N}\left(\mathrm{19}\right)=\mathrm{66012} \\ $$$${N}\left(\mathrm{20}\right)=\mathrm{121415}\:\checkmark \\ $$$$ \\ $$$${we}\:{can}\:{also}\:{find}\:{a}\:{closed}\:{formula} \\ $$$${for}\:{N}\left({n}\right)\:{by}\:{solving}\:{following} \\ $$$${characteristic}\:{equation} \\ $$$$\lambda^{\mathrm{3}} −\lambda^{\mathrm{2}} −\lambda−\mathrm{1}=\mathrm{0} \\ $$$${let}\:\lambda={s}+\frac{\mathrm{1}}{\mathrm{3}} \\ $$$${s}^{\mathrm{2}} −\frac{\mathrm{4}}{\mathrm{3}}{s}−\frac{\mathrm{38}}{\mathrm{27}}=\mathrm{0} \\ $$$${with}\:{u}=\sqrt[{\mathrm{3}}]{\mathrm{3}\sqrt{\mathrm{33}}+\mathrm{19}},\:{v}=\sqrt[{\mathrm{3}}]{\mathrm{3}\sqrt{\mathrm{33}}−\mathrm{19}} \\ $$$$\lambda_{\mathrm{1}} =\frac{\mathrm{1}}{\mathrm{3}}\left(\mathrm{1}+{u}−{v}\right) \\ $$$$\lambda_{\mathrm{2},\mathrm{3}} =\frac{\mathrm{1}}{\mathrm{6}}\left[\mathrm{2}−{u}+{v}\pm\sqrt{\mathrm{3}}\left({u}+{v}\right){i}\right] \\ $$$$\Rightarrow{N}\left({n}\right)={A}\lambda_{\mathrm{1}} ^{{n}} +{B}\lambda_{\mathrm{2}} ^{{n}} +{C}\lambda_{\mathrm{3}} ^{{n}} \\ $$$${N}\left(\mathrm{0}\right)={N}\left(\mathrm{3}\right)−{N}\left(\mathrm{2}\right)−{N}\left(\mathrm{1}\right)=\mathrm{1} \\ $$$${N}\left(−\mathrm{1}\right)={N}\left(\mathrm{2}\right)−{N}\left(\mathrm{1}\right)−{N}\left(\mathrm{0}\right)=\mathrm{0} \\ $$$$ \\ $$$${N}\left(\mathrm{1}\right)={A}\lambda_{\mathrm{1}} +{B}\lambda_{\mathrm{2}} +{C}\lambda_{\mathrm{3}} =\mathrm{1} \\ $$$${N}\left(\mathrm{0}\right)={A}+{B}+{C}=\mathrm{1} \\ $$$${N}\left(−\mathrm{1}\right)=\frac{{A}}{\lambda_{\mathrm{1}} }+\frac{{B}}{\lambda_{\mathrm{2}} }+\frac{{C}}{\lambda_{\mathrm{3}} }=\mathrm{0} \\ $$$$\begin{bmatrix}{\lambda_{\mathrm{1}} }&{\lambda_{\mathrm{2}} }&{\lambda_{\mathrm{3}} }\\{\mathrm{1}}&{\mathrm{1}}&{\mathrm{1}}\\{\frac{\mathrm{1}}{\lambda_{\mathrm{1}} }}&{\frac{\mathrm{1}}{\lambda_{\mathrm{2}} }}&{\frac{\mathrm{1}}{\lambda_{\mathrm{3}} }}\end{bmatrix}\begin{pmatrix}{{A}}\\{{B}}\\{{C}}\end{pmatrix}\:=\begin{pmatrix}{\mathrm{1}}\\{\mathrm{1}}\\{\mathrm{0}}\end{pmatrix} \\ $$$$\Rightarrow\begin{pmatrix}{{A}}\\{{B}}\\{{C}}\end{pmatrix}\:=\begin{bmatrix}{\lambda_{\mathrm{1}} }&{\lambda_{\mathrm{2}} }&{\lambda_{\mathrm{3}} }\\{\mathrm{1}}&{\mathrm{1}}&{\mathrm{1}}\\{\frac{\mathrm{1}}{\lambda_{\mathrm{1}} }}&{\frac{\mathrm{1}}{\lambda_{\mathrm{2}} }}&{\frac{\mathrm{1}}{\lambda_{\mathrm{3}} }}\end{bmatrix}^{−\mathrm{1}} \begin{pmatrix}{\mathrm{1}}\\{\mathrm{1}}\\{\mathrm{0}}\end{pmatrix} \\ $$

Pin

Leave a Reply

Your email address will not be published. Required fields are marked *