This works only if you assume that you do not go backwards i.e. your max path length is N+M-2. If you can go backwards, then I think that there are more paths than just these.
e.g. in 3x3 grid you can have path length more than 4 (1,1) -> (1,2) -> (2,2) -> (2,1) -> (3,1) -> (3,2) -> (3,3) I havent given much thought on how to count all possible paths ... maybe some variation of Floyd-Warshalls ... -Dhyanesh On 4/6/06, shishir <[EMAIL PROTECTED]> wrote: > > There's a small error in my formula. The formula holds for a NxM grid > (N horizontal and M vertical lines) where N= n+1 and M = m+1, which > essentially boils down to > > C(N+M-2, N-1) = C(N+M-2,M-1). > > This should work fine. > -Shishir > > > > > --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~----------~----~----~----~------~----~------~--~---