wu :: forums - Print Page


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

        riddles >> medium >> Number of ways
        
(Message started by: raj1 on Feb 4^th, 2008, 1:18pm)

Title: Number of ways
Post by raj1 on Feb 4^th, 2008, 1:18pm

Given that you can take one step or two steps forward from a given step. So find the total number of ways of reaching Nth step.

Title: Re: Number of ways
Post by Eigenray on Feb 4^th, 2008, 2:59pm

Discussed recently [link=http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_microsoft;action=display;num=1198687412]here[/link] (and a variation [link=http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_medium;action=display;num=1187504551]here[/link]).

Title: Re: Number of ways
Post by mad on Feb 9^th, 2008, 9:12pm

Given a grid of n X n squares, what are the number of ways to reach from one end vertex (bottom left) to another top right vertex walking only along edges of squares when
i) you can move only left anf above

ii) you can use any edge only once but can move in any of the 4 directions?

Title: Re: Number of ways
Post by Eigenray on Feb 9^th, 2008, 10:40pm

on 02/09/08 at 21:12:56, mad wrote:

There must be 2n moves; you can choose n of them to be right, and the other n to be up, in C(2n,n) ways.

Quote:

ii) you can use any edge only once but can move in any of the 4 directions?

[link=http://www.research.att.com/~njas/sequences/A013990]A lot[/link]. Over a billion just for a 5x5 grid!

Title: Re: Number of ways
Post by mad on Feb 9^th, 2008, 11:50pm

But, can't any formula be derived? I mean since we can use any edge only once, there must be an upper bound.

Title: Re: Number of ways
Post by towr on Feb 10^th, 2008, 7:14am

on 02/09/08 at 23:50:18, mad wrote:

But, can't any formula be derived? I mean since we can use any edge only once, there must be an upper bound.

Well, it won't go beyond (n*n)!, but that's not a very tight upper bound.

Title: Re: Number of ways
Post by Hippo on Feb 10^th, 2008, 9:34am

3^((N-2)^2)*2^(4(N-2))*2 is a bit tighter bound.
(I hope it's correct ;))