# Closed-form for finding the number of paths on an nxm board

Let a board $$B$$ be of size $$n \times m$$ squares where $$n, m \in \mathbb{Z}$$ and $$n, m \ge 1$$. Starting from the upper-left square, $$B_{1,1}$$, find the number of paths to the bottom-right square, $$B_{n,m}$$, by going right or down at any given square.

For example, let $$B$$ be $$2\times 2$$, then the total number of paths is two: $$(B_{1,1}, B_{1,2}, B_{2,2}), (B_{1,1},B_{2,1},B_{2,2})$$.

One can calculate the total number of paths for an $$n\times m$$ board by representing the board as a matrix where the top row are 1s and the left-most column are 1s, then the number of paths to get to $$B_{n,m} = B_{n-1,m} + B_{n,m-1}$$. Going further, the total paths can be expressed as the closed-form $$\frac{(n-1+m-1)!}{(n-1)!(m-1)!}$$.

When the problem is extended to allow movements of right, right-down, and down at any given square, the closed-form above breaks down. As an example for a board $$B$$ of size $$2\times 2$$, the total number of paths is three now: $$(B_{1,1}, B_{1,2}, B_{2,2}), (B_{1,1}, B_{2,2}), (B_{1,1},B_{2,1},B_{2,2})$$. One could still calculate the total paths doing the matrix method above, but I'm interested in whether a closed-form exist?

Let $$t$$ be the number of diagonal moves. Then there are $$n-1-t$$ horizontal moves and $$m-1-t$$ vertical moves, for a total of $$\binom{n+m-2-t}{t,n-1-t,m-1-t}$$ paths (this is a multinomial coefficient). Therefore the total number of paths is $$\sum_{t=0}^{\min(n,m)-1} \binom{n+m-2-t}{t,n-1-t,m-1-t}.$$ I'm not sure this can be simplified any further.