Question and Answers Forum

All Questions      Topic List

Permutation and Combination Questions

Previous in All Question      Next in All Question      

Previous in Permutation and Combination      Next in Permutation and Combination      

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} \\ $$

Terms of Service

Privacy Policy

Contact: info@tinkutara.com