Geodesics in taxicab geometry

I was interested in the taxicab geometry from class, so I decided to examine one particular problem. Suppose you are on one corner of a city whose streets form a perfect grid, and you wish to reach the opposite corner in the shortest possible distance. How many possible paths can you take? More abstractly, how many geodesics are there in a taxicab geometry grid of a given size?

It turns out that there is a very elegant formula to find the answer; as I discovered, in a city with c × n blocks, there are exactly

geodesics between opposite corners.

My goal here will be to document my personal "discovery process" for this remarkable little formula, rather than arrive at it in the most logical or efficient way.

So, my first step was to realize that any size grid can be broken into smaller grids. When the traveler begins in the corner of a c × n grid, he can take only one of two paths.

Either way, after one step, he finds himself on a "new" grid of size (c – 1) × n or c × (n – 1). The number of possible geodesics in the old grid, which I notate A_c,n, is equal to the sum of the number of possibilities in each of the two smaller grids. In other words,

A_c,n = A_c-1,n + A_c,n–1

The other thing to know is that any grid with a dimension 0 automatically has only one geodesic—a single path from end to end.

So, we can begin constructing some grids and seeing what patterns emerge. With a 1 × 1 grid, it should be fairly obvious by intuition that there are two paths:

but let's use the formula nonetheless:

A_1,1 = A_0,1 + A_1,o = 1 + 1 = 2.

For a 1 × 2 grid, we would imagine there are three geodesics:

A_1,2 = A_0,2 + A_1,1 = 1 + 2 = 3.

In fact, it very quickly becomes clear that for any 1 × n grid, there are

A_1,n = (n + 1)

geodesics. So far, so good. Now let's calculate the geodesics in some 2 × n grids:

A_2,2 = A_1,2 + A_2,1 = 3 + 3 = 6

A_2,3 = A_1,3 + A_2,2 = 4 + 6 = 10

A_2,4 = A_1,4 + A_2,3 = 5 + 10 = 15

A_2,5 = A_1,5 + A_2,4 = 6 + 15 = 21

A_2,6 = A_1,6 + A_2,5 = 7 + 21 = 28

This is a familiar pattern; in a grid size 2 × n, we are summing the integers from 1 to (n + 1). We know the formula for this behavior:

A_2,n = (n + 1)(n + 2)/2

It's probably too early to generalize from these two formulae so far, so let's keep gathering results.

Number of geodesics in a grid with the given dimensions (dimensions are commutative)

It's quite easy once we recognize that each number is the sum of the squares to above and to the left.

Since the differences between the values in a given row are determined by the row above, the direct formula for each row should be a higher-degree polynomial than the row above. I.e., row 1 is linear, row 2 quadratic, row 3 cubic, row 4 quartic, etc. I plugged the values for row 3 into my calculator for a cubic regression and found the roots:

Well, that's surely curious. Each time we've increased c by 1, we've multiplied that row's direct formula by (n + c)/c. That seems to suggest that any general formula would be of the form

A_c,n = (1/c!) ⋅ ((n + 1)(n + 2)(n + 3) ⋅ … ⋅ (n + c))

= (1/c!) ⋅ ((n + c)!/n!)

= (c + n)!/(c!n!)

which makes intuitive sense, since it's clear from this formula that n and c are indeed interchangeable, making the dimensions of a grid commutative.

Let's try one example: a 5 × 7 grid. From the formula,

A_5,7 = (5 + 7)!/(5!7!)

         = 12!/(5!7!)

         = 792

I'll decline to draw 792 paths on a grid, but you can glance up the page to see that this is indeed the number of paths we have in the table, which was constructed by sound methods.

Apart from being extremely simple and easy to use, this formula is a nice reminder that even the explosive factorial function is just repeated addition. Everything in the chart, up to the daunting 184756 paths in a 10 × 10 grid, comes from adding single digit numbers.