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

    NateTG

    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)

Loading...