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


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

$I n h o w m a n y w a y s c a n y o u g o u p a$ $s t a i r c a s e w i t h 20 s t e p s i f y o u t a k e$ $o n e, t w o o r t h r e e s t e p s a t a t i m e ?$
Commented by MJS_new last updated on 27/Feb/22

$is it 121415 ?$
Commented by mr W last updated on 28/Feb/22

$i {h a v n}^{'} t c a l c u l a t e d i t y e t s i r .$
Commented by peter frank last updated on 28/Feb/22

$very 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$
Commented by mr W last updated on 28/Feb/22

$M J S s i r :$ $121415 i s c o r r e c t . i g o t t h e s a m e .$
Commented by MJS_new last updated on 28/Feb/22

$thank you!$
	Answered by nadovic last updated on 27/Feb/22

	$One Step : 20 w a y s$ $Two Steps : 10 w a y s$ $Three Steps : 7 w a y s$ $N u m b e r o f W a y s = 20 + 10 + 7$ $= 37 w a y s$
	Commented by mr W last updated on 27/Feb/22

	$w r o n g!$
	Answered by nadovic last updated on 28/Feb/22

	$=^{20} P_{1} +^{20} P_{2} +^{20} P_{3}$ $= 7240 w a y s$
	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$ $. . .$
	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.$
	${l e t}^{'} s l o o k a t t h e c a s e t h a t w e m a k e n$ $m o v e s t o g o u p t h e s t a i r c a s e . e a c h$ $m o v e c a n b e o f o n e, t w o o r t h r e e$ $s t e p s .$ $t h e n u m b e r o f w a y s t o g o u p t h e$ $s t a i r c a s e i n n m o v e s i s t h e n u m b e r$ $o f i n t e g e r s o l u t i o n s o f t h e e q u a t i o n$ $a_{1} + a_{2} + a_{3} + . . . + a_{n} = 20$ $w i t h 1 ⩽ a_{i} ⩽ 3 .$ $u s i n g g e n e r a t i n g f u n c t i o n i t i s t h e$ $c o e f f i c i e n t o f t h e x^{20} t e r m i n t h e$ $e x p a n s i o n o f {(x + x^{2} + x^{3})}^{n} .$ ${(x + x^{2} + x^{3})}^{n}$ $= x^{n} {(1 + x + x^{2})}^{n}$ $= \frac{x^{n} {(1 - x^{3})}^{n}}{{(1 - x)}^{n}}$ $= x^{n} {\underset{k = 0}{\sum^{n}} {(- 1)}^{k} C_{k}^{n} x^{3 k}} {\underset{m = 0}{\sum^{\infty}} C_{n - 1}^{m + n - 1} x^{m}}$ $x^{n} x^{3 k} x^{m} = x^{n + 3 k + m} \overset{!}{=} x^{20}$ $n + 3 k + m \overset{!}{=} 20$ $\Rightarrow 3 k + m = 20 - n$ $0 ⩽ k ⩽ n, m ⩾ 0$ $\Rightarrow 7 ⩽ n ⩽ 20 (t h i s i s c l e a r, w e n e e d a t$ $l e a s t 7 m o v e s a n d a t m o s t 20 m o v e s$ $t o g o u p t h e s t a i r c a s e .)$ $e x a m p l e n = 10 :$ $k = 0, m = 10 \Rightarrow C_{0}^{10} C_{9}^{19} = 92378$ $k = 1, m = 7 \Rightarrow - C_{1}^{10} C_{9}^{16} = - 114400$ $k = 2, m = 4 \Rightarrow C_{2}^{10} C_{9}^{13} = 32175$ $k = 3, m = 1 \Rightarrow - C_{3}^{10} C_{9}^{10} = - 1200$ $t h a t m e a n s t h e c o e f . o f x^{20} i s$ $92378 - 114400 + 32175 - 1200 = 8953$ $t h e r e s u l t s f o r a l l v a l u e s o f n s e e$ $f o l l o w i n g t a b l e .$ $t h e t o t a l r e s u l t i s 121415 . i . e . t h e r e$ $a r e 121415 w a y s t o g o u p t h e s t a i r c a s e .$
	Commented by mr W last updated on 28/Feb/22

	Commented by Tawa11 last updated on 28/Feb/22

	$Great sir$
	Answered by mr W last updated on 02/Mar/22

	$A N O T H E R M E T H O D$ ${l e t}^{'} s s a y t h e r e a r e N (n) w a y s t o g o u p$ $a s t a i r c a s e w i t h n s t e p s . i f w e m a k e$ $a m o v e w i t h o n e s t e p, t h e n t h e r e a r e$ $n - 1 s t e p s r e m a i n i n g a n d t h e r e a r e$ $N (n - 1) w a y s t o g o u p t h e r e m a i n i n g$ $s t e p s . i f w e m a k e a m o v e w i t h$ $t w o s t e p s, t h e n t h e r e a r e n - 2 s t e p s$ $r e m a i n i n g a n d t h e r e a r e N (n - 2)$ $w a y s t o g o u p t h e r e m a i n i n g s t e p s .$ $s i m i l a r l y i f w e m a k e a m o v e w i t h$ $t h r e e s t e p s, t h e n t h e r e a r e N (n - 3)$ $w a y s t o g o u p t h e r e m a i n i n g s t e p s .$ $t h e r e f o r e w e h a v e f o l l o w i n g$ $r e c u r r e n c e r e l a t i o n :$ $N (n) = N (n - 1) + N (n - 2) + N (n - 3)$ $w e a l s o h a v e$ $N (1) = 1$ $N (2) = 2$ $N (3) = 4$ $a p p l y i n g t h e r e c u r r e n c e r e l a t i o n a b o v e,$ $w e g e t$ $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 ✓$ $w e c a n a l s o f i n d a c l o s e d f o r m u l a$ $f o r N (n) b y s o l v i n g f o l l o w i n g$ $c h a r a c t e r i s t i c e q u a t i o n$ $λ^{3} - λ^{2} - λ - 1 = 0$ $l e t λ = s + \frac{1}{3}$ $s^{2} - \frac{4}{3} s - \frac{38}{27} = 0$ $w i t h u = \sqrt[3]{3 \sqrt{33} + 19}, v = \sqrt[3]{3 \sqrt{33} - 19}$ $λ_{1} = \frac{1}{3} (1 + u - v)$ $λ_{2, 3} = \frac{1}{6} [2 - u + v \pm \sqrt{3} (u + v) i]$ $\Rightarrow 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) = \frac{A}{λ_{1}} + \frac{B}{λ_{2}} + \frac{C}{λ_{3}} = 0$ $[\begin{matrix} λ_{1} & λ_{2} & λ_{3} \\ 1 & 1 & 1 \\ \frac{1}{λ_{1}} & \frac{1}{λ_{2}} & \frac{1}{λ_{3}} \end{matrix}] (\begin{matrix} A \\ B \\ C \end{matrix}) = (\begin{matrix} 1 \\ 1 \\ 0 \end{matrix})$ $\Rightarrow (\begin{matrix} A \\ B \\ C \end{matrix}) = {[\begin{matrix} λ_{1} & λ_{2} & λ_{3} \\ 1 & 1 & 1 \\ \frac{1}{λ_{1}} & \frac{1}{λ_{2}} & \frac{1}{λ_{3}} \end{matrix}]}^{- 1} (\begin{matrix} 1 \\ 1 \\ 0 \end{matrix})$
Terms of Service
Privacy Policy
Contact: info@tinkutara.com

Question and Answers Forum