# Counting paths

1. Feb 15, 2005

### 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?

2. Feb 15, 2005

### 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.

3. Feb 15, 2005

### Bartholomew

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

4. Feb 15, 2005

### 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.

Last edited: Feb 15, 2005