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 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

\dots

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

\dots

Answered by mr W last updated on 01/Mar/22

{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} + \dots + 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})

Facebook Tweet Pin