1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
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
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?

Similar Discussions: Counting paths
  1. Who's counting? (Replies: 23)

  2. Shortest path (Replies: 6)

  3. Stepping paths (Replies: 16)

  4. Counting Game (Replies: 56)

  5. Post Count (Replies: 2)