Combinatorics and Graph Theory · Problem 1.3.1

Fundamentals — David Guichard

Mathematics — Combinatorics · lattice-paths

Problem

Suppose a street grid starts at position

(0,0)

and extends up and to the right. A shortest route along streets from

(0,0)

(i,j)

i+j

blocks long, going

i

blocks east and

j

blocks north. How many such routes are there? Suppose that the block between

(k,l)

and

(k+1,l)

is closed, where

k < i

and

l \leq j

. How many shortest routes are there from

(0,0)

(i,j)