Problem
For a n x n grid, how many different ways are there to get from the southeast corner to the northwest corner if I can move one cell west, north, or northwest at any given time?
Recurrence
The number of possible paths starting at cell $(i, j)$ is the sum of the number of paths starting at all of its neighbors:
$$T(i, j) = T(i - 1, j) + T(i - 1, j - 1) + T(i, j - 1)$$
The cell at the northwest corner has only one path (not moving at all) and serves as the base case.
$$T(0, 0) = 1$$
If we're at the west edge, we can only move up. Likewise, if we're at the north edge, we can only move left. There is only one path from these cells.
$$T(i, 0) = 1$$ $$T(0, j) = 1$$
If each cell is assigned a number $m = T(i, j)$. this produces a grid that is symmetric about the diagonal - in other words:
$$T(i, j) = T(j, i)$$
If we just follow along the diagonal, then the symmetry can be used to somewhat simplify the recurrence:
$$T(n, n) = T(n - 1, n - 1) + 2T(n - 1, n) = T(n - 1, n - 1) + 2T(n, n - 1)$$
Is there a closed form T(n) for this recurrence relation? I know it grows exponentially with increasing n, but the exact equation is hard to pin down.
These are the Delannoy numbers. So far as I know, they have no nice closed form, though they do satisfy
$$T(m,n)=\sum_k\binom{m+n-k}m\binom{m}k=\sum_k2^k\binom{m}k\binom{n}k\;.$$
They are OEIS A008288, and Wolfram has more information. All three links have more information and references.