Suppose you're on a 4 × 6 grid, and want to go from the bottom left to the top right. How many different paths can you take? Avoid backtracking -- you can only move right or up.
This is, I'm sure, answered somewhere else. It is also related to Pascal's triangle.
Simply fill out the grid as follows:
In this grid, each number represents the number of ways of getting to that particular intersection. And that number is precisely the number of ways to get to the intersection below it added to the number of ways to get to the intersection to the left of it.
Here is a small python program which solves it. Every step we can go up or right with the goal being 4,6.
def count(up, right): if up > 4: return 0 if right > 6: return 0 if up == 4 and right == 6: return 1 return count(up + 1, right) + count(up, right + 1) print count(0,0)
output : 210