Counting Paths through a Grid

the possible paths

1

number of rows n

6

B

A downward path joins the top spot A to the variable bottom spot B. For a fixed B, there are "

n

choose

k

" =



n

k



possible paths, where

n

is the row number and

k

counts how far B is along its row, with both

n

and

k

starting at zero. These numbers are the binomial coefficients that form Pascal's triangle.

George Beck, Rob Morris