Many results in combinatorics can be generated counting all the different ways to make something in the real world. As an example, consider the lines connecting points in a grid or lattice:
o-------o . .
|
. . o---o .
|
. . . | .
|
. . . o---o
|
. . . . o
This figure can be associated to many objects in the real world, like a walk through the streets of a city or multiple movements of a chess rook. The number of different paths like this in a grid of NxN points using only two directions to move and not crossing the main diagonal of the grid is equal to the Catalan number N, and these paths are also known as Dyck paths. Interestingly, including the moves crossing the main diagonal generates exactly the numbers of the famous Pascal's triangle, that is, the Binomial coeficients.
OK, but, what happens if we use a chess queen instead?
Thinking in that question I wrote a program to print these paths, and I generalized it to optionally include moves surpassing the main diagonal of the grid and to optionally include diagonal paths. I published the result in LatticePath and it prints the paths in ASCII:
> java -jar LatticePath.jar --pass --diag 5
...
o---o---o
|
o---o
|
o
|
o
|
o---o
o---o---o
|
o
'.
'o---o
|
o
|
o
o---o---o
|
o
'.
'o
'.
'o
|
o
...
> java -jar LatticePath.jar --pass --diag --count 5
1 1 1 1 1
1 3 5 7 9
1 5 13 25 41
1 7 25 63 129
1 9 41 129 321
After writing the first version of the program I realized that including diagonal moves generates different kinds of numbers: The number of paths not surpassing the main diagonal of the grid is called Schröder number, and the number of paths surpassing the main diagonal of the grid is called Delannoy number. How many connections from only a few simple rules! Thanks also to the OEIS site for being so useful for knowing the name of any sequence of numbers.
I hope you enjoy the program LatticePath and the minimalistic style in which it is programmed!
