Grid Paths – How Many Paths Exist on an $n\times m$ Grid?

Question

How many paths exist on an $n\times m$ grid?

The Path requirements are

1. You start at the bottom left and end at the top right
2. The Path can not intersect it's self
3. Each Line has to start and end on a point on the grid
4. Reflections and flips of a Path are not necessary an equivalent Path.

I found $26$ Paths for a $2$ by $3$ grid I believe that I found all paths for a $2$ by $3$ grid.

What can I use to try to make a general formula for an $n\times m$ grid?

Answer 1

We shall find the desired number for $m = 2$.

Let $V(G) = \{1, 2,\dots, n\}\times \{1, 2\}$ be the set of points of our grid $G$.

Note that a path on $G$ is uniquely determined by the edges (path segments that connect two points) that change column (because anywhere in a path you're forced to go up until you change column). Let's call those edges transversals. Since a path ends in a different column than the one it starts, there must be an odd number transversals in it. Also, any odd number of transversals that do not intersect determines a valid path, so we just have to count how many of those are there.

Let us now argue that the number of ways to choose our non crossing transversals is the number of ways to choose two multisubsets of $\bar{n}_2 = \{1, 1, 2, 2, \dots, n, n\}$ with the same odd number of elements. To this end, we will establish the following bijection:

• Given a valid path $P$, let $E$ be the multisubset of $V(G)$ of the extreme points of the transversals of $P$, where an element appears twice if it is the extreme point of two distinct transversals (of course a point cannot be the extreme of three or more distinct transversals). So we can relate the path to the two multisubsets of $\bar{n}_2$ given by $E_1 = \{i:(i, 1)\in E\}$ and $E_2 = \{i:(i,2)\in E\}$. As each transversal connects a distinct element of $E_1\times \{1\}$ to a distinct element of $E_2\times \{2\}$, it is clear that $|E_1| = |E_2|$ is odd.
• Given two multisubsets $E_1$ and $E_2$ of $\bar{n}_2$ with the same odd number of elements $e$, there is only one set of non crossing transversals, each one connecting a distinct element of $E_1\times \{1\}$ to a distinct element of $E_2\times \{2\}$, which is the one given by $\{t_1, t_2, \dots, t_e\}$ where $t_k$ connects the $k$-th smallest element of $E_1$ to the $k$-th smallest element of $E_2$ (since, otherwise, there would be an inversion, therefore, an intersection).

If I didn't get my maths wrong, it's not hard to show that the number of ways to choose a multisubset with $s$ elements of $\bar{n}_2$ is given by

$$\sum_{r=1}^s \binom{n}{r}\binom{r}{s-r} = \sum_{r=1}^s \frac{n!}{(n-r)!(s-r)!(2r-s)!}$$

So the number of ways to choose two multisubsets with an odd number of elements from $\bar{n}_2$ is

$$\sum_{p=0}^{n-1}\left[\sum_{r=1}^{2p+1} \binom{n}{r}\binom{r}{2p+1-r}\right]^2$$

---

Honestly, I don't think the methods used can be generalized to different values ​​of $m$. Many particular features of the $m = 2$ case were used. Also, I believe that the value obtained for the case $m = 2$ may be simplified to a nicer expression, but I failed to get it. Anyway, I hope these elaborations give someone some insight.