wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> medium >> Walking up stairs
        
(Message started by: Earendil on Aug 18th, 2007, 11:22pm)
Title: Walking up stairs
Post by Earendil on Aug 18th, 2007, 11:22pm
What is the number of ways you can walk up a stair with n steps only going up 1, 2 or 3 steps at a time?
Title: Re: Walking up stairs
Post by TenaliRaman on Aug 19th, 2007, 12:11am
::[hide]Solution to F(n) = F(n-1) + F(n-2) + F(n-3) with F(1) = 1, F(2) = 2, F(3) = 4[/hide]::

-- AI
Title: Re: Walking up stairs
Post by Barukh on Aug 19th, 2007, 4:40am

on 08/19/07 at 00:11:28, TenaliRaman wrote:
::[hide]Solution to F(n) = F(n-1) + F(n-2) + F(n-3) with F(1) = 1, F(2) = 2, F(3) = 4[/hide]::

-- AI

... which is called Tribonacci Number (http://mathworld.wolfram.com/TribonacciNumber.html).
Title: Re: Walking up stairs
Post by srn347 on Sep 6th, 2007, 4:39pm
I think it is similar to the subfactorial: http://en.wikipedia.org/wiki/Subfactorial.
Title: Re: Walking up stairs
Post by Obob on Sep 6th, 2007, 4:48pm
No, it has absolutely nothing to do with the subfactorial.
Title: Re: Walking up stairs
Post by srn347 on Sep 6th, 2007, 8:04pm
I'm 99.9999999999...% sure it does.
Title: Re: Walking up stairs
Post by ThudanBlunder on Sep 6th, 2007, 11:26pm

on 09/06/07 at 20:04:56, srn347 wrote:
I'm 99.9999999999...% sure it does.

Then back up your blinkeredness with some hard facts! Exactly how are they similar?
Title: Re: Walking up stairs
Post by JiNbOtAk on Sep 7th, 2007, 1:54am

on 09/06/07 at 23:26:48, ThudanBlunder wrote:
Then back up your blinkeredness with some hard facts! Exactly how are they similar?

This would prove to be interesting. ( And not only because T&B is getting riled up )  ;D


on 09/06/07 at 16:48:53, Obob wrote:
No, it has absolutely nothing to do with the subfactorial.


Hee hee..
Title: Re: Walking up stairs
Post by towr on Sep 7th, 2007, 2:25am

on 09/06/07 at 16:39:14, srn347 wrote:
I think it is similar to the subfactorial: http://en.wikipedia.org/wiki/Subfactorial.

If there is one step, you can take the stairs in 1 way (1)
If there are two steps, you can take it in 2 ways (1,1 or 2)
If there are three steps, you can take it in 4 ways (1,1,1 or 1,2 or 2,1 or 3)

subfactorials go
   !1 = 0
   !2 = 1
   !3 = 2
   !4 = 9
the observed sequence 1,2,4 does not fit, not even with a shift (i.e. if we take !(n+1) for n steps, or even !(n+k) for some fixed k).

Based on the first three observations it would have made more sense to suggest it goes like powers of 2 than subfactorials.
Title: Re: Walking up stairs
Post by TenaliRaman on Sep 7th, 2007, 6:43am
I dont know whether subfactorial has anything to do with this problem, but it certainly has something to do with derangement"s".

-- AI
Title: Re: Walking up stairs
Post by mikedagr8 on Sep 7th, 2007, 6:52am

on 09/07/07 at 02:25:53, towr wrote:
Based on the first three observations it would have made more sense to suggest it goes like powers of 2 than subfactorials.


Like Polynacci...? ???
Title: Re: Walking up stairs
Post by raj1 on Feb 4th, 2008, 9:33pm
So is the solution posted

Solution to F(n) = F(n-1) + F(n-2) + F(n-3) with F(1) = 1, F(2) = 2, F(3) = 4

correct?
Title: Re: Walking up stairs
Post by towr on Feb 5th, 2008, 1:16am

on 02/04/08 at 21:33:21, raj1 wrote:
So is the solution posted

Solution to F(n) = F(n-1) + F(n-2) + F(n-3) with F(1) = 1, F(2) = 2, F(3) = 4

correct?
Yes.
It is easy to check the first three cases must be correct; and then in general, you can get to the Nth step from 1, 2 or 3 steps back.
Title: Re: Walking up stairs
Post by Icarus on Feb 5th, 2008, 5:59pm
You can express it as

F(n) = Ar1n + Br2n + Cr3n,

Where r1, r2, r3 are the roots of the equation r3 - r2 - r - 1 = 0, and the coefficients A, B, C are chosen to make the first three values = 1, 2, 4 respectively. Unfortunately, the expressions for the 3 r's are not very nice, so you are generally better off just calculating values recursively.
Title: Re: Walking up stairs
Post by temporary on Feb 5th, 2008, 6:01pm

on 02/04/08 at 21:33:21, raj1 wrote:
So is the solution posted

Solution to F(n) = F(n-1) + F(n-2) + F(n-3) with F(1) = 1, F(2) = 2, F(3) = 4

correct?


Srn347 was not completely correct, but he was close. n-1, n-2, and n-3 would make it just like factorial if it didn't end right there, but instead ended at 1.
Title: Re: Walking up stairs
Post by Icarus on Feb 5th, 2008, 6:11pm
No. Factorials are products. This is a sum.
Title: Re: Walking up stairs
Post by temporary on Feb 14th, 2008, 8:39pm
Oh. So he was close to being close.
Title: Re: Walking up stairs
Post by JiNbOtAk on Feb 15th, 2008, 3:57am

on 02/14/08 at 20:39:52, temporary wrote:
Oh. So he was close to being close.


Nope, he was not right, and he was not close. He was not even wrong (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_easy;action=display;num=1185110775;start=11#11).


Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright © 2000-2004 Yet another Bulletin Board