Counting paths

Bartholomew

Is there a concise, easily calculable way to count the sum of all the paths from the lower left corner of a square of integer size to the upper right corner where you only move up or right in steps of 1 unit, PLUS all the partial paths? i.e. if you have a city with roads in a 10x10 grid (100 intersections/corners) how many shortest paths are there from one corner of the grid to any other intersection or corner on the grid?

NateTG

Why stop there? There's an easy solution for any point on a grid like that.


To get to the point m,n from 0,0 there are (m+n) choose n paths.

Bartholomew

I know that. Adding them all up concisely is a harder problem.

Bartholomew

It's easy to sum the paths in the triangle bounded by (and including) the line y = x + 10--that's 2^10 - 1 since each diagonal row of intersections/corners (with negative slope) in that triangle corresponds to a row of Pascal's triangle, so you get 2^0 + 2^1 + ... + 2^9 which is 1111111111 in binary.