0
$\begingroup$

Possible Duplicate:
Number of simple paths between two vertices on an $n \times m$ square-grid graph?

Given a N×M grid, how many different ways to walk from left down(denoted as $(0,0)$) to upper right(denoted as $(M-1, N-1)$)?

The path should not contains any circle(i.e for each path, any grid should not be walked more than once)

For a simpler case, if the walker can only walk right or walk up each grid each time, then the total number of paths should be $\binom{M+N-2}{M−1}$. However, for general case, when the walker is allowed to walk any direction(of course, none of the grids can be walked more than once), how to calculate the number of ways?

Thank you for any suggestion.

  • 2
    th$a$nk you, seems I should do more search before asking..2012-10-26

0 Answers 0