Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Counting paths

  1. Feb 15, 2005 #1
    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. jcsd
  3. Feb 15, 2005 #2


    User Avatar
    Science Advisor
    Homework Helper

    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.
  4. Feb 15, 2005 #3
    I know that. Adding them all up concisely is a harder problem.
  5. Feb 15, 2005 #4
    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
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook