Fun with Combinatorics - Determining n Paths for any Grid

Sat 30 April 2011

Working on a recent puzzle, I had to find out the number of paths from opposite corners on a grid. So, for example, on a 57 by 35 square grid, to get to the opposite corner of the grid there are 29702210220359396517113784 possible paths. The formula for determining this is k! / n! * (k - n)!, where k is 57+35 and n is 57 or 35. So to plug our numbers in, it would look like this: (57+35)! = 57! * 35!

If you were wondering how this is relevant to your daily life, just imagine you live in the Calgary downtown (which is a grid), and think of the path you take to walk to work. If your workplace is 8 blocks east and 6 blocks north, there are 3003 possible paths you can take to work. If you took two different paths a day, it would take over 4 years to walk all the different paths!

blogroll

social