1
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.