How do you find the number of unique paths in a grid, while only going up or to the right?

Question

Ok, so here's the deal, I know how to do a full grid, it's (L + W)! / (L! * W!). However, how would I figure out the number of unique paths if there was one of the lines in the middle of the grid missing?

So, like this: http://img593.imageshack.us/img593/5060/wt0r.png

Would I separate it into sections around the empty space and evaluate and add up all the sections?

Then, how would I do a grid that has one diagonal section?

Like this: http://img844.imageshack.us/img844/5319/ysh8.png

Thank you for any help!

Awms A · Accepted Answer

The easiest way would be to count the number of paths that use the missing edge or the additional diagonal, then either subtract or add that number to the original number of paths.

For instance, in the first one, there are
7! / (5! 2!) = 21
ways to go from the start to the bottom of the missing edge, and
5! / (3! 2!) = 10
ways to go from the top of the missing edge to the end.  Therefore, in the complete grid, exactly
21 * 10 = 210
paths would use missing edge.  To get the number of paths after you remove that edge, subtract 210 from the total:
13! / (8! 5!) - 210 = 1077.

Trending News

How do you find the number of unique paths in a grid, while only going up or to the right?

1 Answer