First of all, what is a Lattice Point
Lattice points are points in a Point Lattice where two or more gridlines intersect.
there is only one lattice point here, in the center, as that is the only point where the grid lines intersect
So what are Lattice Paths
Lattice Paths are paths that lead from one lattice point to the next.
Counting the number of possible paths from a starting point to an endpoint
So how would one, given the need or want, go about counting the number of possible paths from one point to another? After a few failed attempts at creating my own method (all of which failed horribly), I ended up using the method described here by Robert Dickau.
Here, the solution is derived by counting the number of paths it takes to get to adjacent points and adding them together.
All points from the rightmost side to the top and bottom take 1 step to reach, so they are marked with one. The next point, diagonal to the rightmost point, takes 2 steps, because each point adjacent to it (the premise is that from the start point, you can only go towards the right, NE or SE) takes one step to get to. The point diagonal to that one, going towards the endpoint, takes 6 steps because the points adjacent to it both take 3 steps, and so on.
Now this is a great solution but to use it effectively when dealing with large lattices we will have to come up with a program that can do the counting for us. Even a small 4x4 grid contains 70 possible paths, it would be ridiculous for us not to use a computer to do this repetitive task (not to mention that computers are far more accurate and are not prone to "human error").
Translating the method into code
So the method's premise is counting the all paths that have 1 step and working from there to come up with all points that require 2 steps, and from there to 3 steps and so on. How would this translate to code?
While it would be possible to come up with an algorithm that would walk all paths with 1 step and from there work out the paths with 2 steps and so forth, there is actually an easier method. I actually came up with this myself after staring at the number of paths in the above 4x4 grid, though I'm sure it must be listed somewhere as a method for counting lattice paths.
If we take a look at the first northeastern rows in the 4x4 grid, we'll see that the number of paths are as follows:
If we take the third and fourth rows, we end up with the following matrix:
You'll note an interesting symmetry where the second row matches the second column, the third row the third column, etc. Yet that didn't really help any in coming up with a theoretical formula for calculating the next row from the preceeding one.
Then I realized that one didn't have to come up with both adjacent points to determine the next one, since the adjacent points mirrored each other (the adjacent points to the second point on the second row are both 1 for example and the point itself is 2). All you have to do is come up with one point and multiply it by 2, that would yield the next point. The pattern that i reasoned out was that multiplying the second element of the top row by 2 would yield the path count below that element. Then adding that number to the next element in the top row would yield the count below that element and so forth.
Starting from the first row:
Take the second element and multiply it by 2, placing it below the second element:
Add that to the next element in the above row (2 + 1):
And keep going on going:
Then work on the third row by taking the second element of the second row (3) and repeating the process, 3 * 2 = 6 hence:
Take 6 and add it to the next element in the second row (4):
And then take that and add it to the last element in the second row:
This algorithm allows you determine the number of paths from on edge to the other without actually drawing a diagram and manually counting the paths.
(defun initial-steps (width) (let ((steps '())) (dotimes (i width) (push 1 steps)) steps))
(defun count-next-steps (previous) (if (second previous) (let ((step (* (second previous) 2)) (previous-copy (cddr previous)) (steps '())) (push step steps) (loop until (null previous-copy) do (progn (incf step (car previous-copy)) (push step steps) (setf previous-copy (cdr previous-copy)))) (reverse steps)) previous))
(defun count-paths (width) (setf path-count '()) (push (initial-steps width) path-count) (dotimes (i (1- width)) (push (count-next-steps (car path-count)) path-count)))