Mathnasium Journal

We start with the symmetric version first: from $(0, 0)$ to $(n, n)$ , moving only right or up.

Each valid path uses exactly $n$ right moves and $n$ up moves, so every route has Manhattan (taxi-cab) length:

d_{M} = n + n = 2 n

For comparison, the straight-line Euclidean distance to $(n, n)$ is:

d_{E} = n^{2} + n^{2} = n 2

That is the key taxi-cab idea: on city blocks, you count grid steps, not diagonal shortcuts.

The number of distinct paths in the $(n, n)$ case is:

(n 2 n) = \frac{( 2 n )!}{n ! n !}

Square Target: From `(0,0)` to `(n,n)`

Each valid route has exactly n right moves and n up moves, so every path has Manhattan length 2n.

$d_\text{Manhattan}=n+n=2n=12$

$d_\text{Euclidean}=\sqrt{n^2+n^2}=n\sqrt{2}\approx8.49$

$\binom{2n}{n}=\binom{12}{6}$ Paths: 924

Choose n: 6

Taxi-cab view: you travel on grid streets, so you count blocks. Euclidean view: you measure the straight-line diagonal.

Build a Path for `(6,6)`

Desktop mode: drag from the orange point right or up to place the next move.

Move Ledger (for `(6,6)`)

Right left: 6

Up left: 6

Placed: 0/12

Current point: (0,0)

Sequence

No moves yet.

$\binom{2n}{n}=\binom{12}{6}$ There are 924 valid step strings with 6 R's and 6 U's.

General Case: From `(0,0)` to `(m,n)`

Now you need m rights and n ups, so you count arrangements of two move types in m+n slots.

$d_\text{Manhattan}=m+n=11$

$\binom{m+n}{m}=\frac{(m+n)!}{m!\,n!}$

$\binom{11}{7}$ Paths: 330

Choose m: 7 Choose n: 4

Why the binomial coefficient appears

Think of a path as a string of length $2 n$ made of letters $R$ and $U$ .

You must place exactly $n$ copies of $R$ .
The remaining slots are automatically $U$ .

So the count is “choose which $n$ of the $2 n$ slots are $R$ ”, which is $(n 2 n)$ .

In the interactive $(9, 9)$ builder, that means you can place only 9 right steps and 9 up steps total. As each move is placed, the ledger tracks how many of each move type are still available.

General version at the bottom: from $(0, 0)$ to $(m, n)$

Now the move totals are not equal:

right moves: $m$
up moves: $n$
total steps: $m + n$

So the number of valid up-right routes is:

(m m + n) = (n m + n) = \frac{( m + n )!}{m ! n !}

Use the sliders in the final panel of the interactive to change $m$ and $n$ and see the count update live.

Square Target: From (0,0) to (n,n)

Build a Path for (6,6)

Move Ledger (for (6,6))