# On an $h \times h$ square lattice, count all the paths from $(0,a)$ to $(h-1,b)$, $a,b \in$, with diagonal moves allowed

Consider an $h \times h$ upright square lattice, where a point is defined by $(x,y)$, $x,y \in [0,h-1]$. A valid path starts from the left boundary, $(0,a)$, $a \in [0,h-1]$ and ends to the right boundary $(h-1,b)$, $b \in [0,h-1]$. Allowed moves are:

• Diagonal, such as $(0,0) \rightarrow (1,1)$, or
• To the right, such as $(0,0) \rightarrow (1,0)$.

Vertical movement or any movement to the left is not valid.

What is the total number of all these paths? Its possible to calculate the paths programmatically up to a certain $h$ (after $h=8$ it becomes really slow). I’m looking for a closed form expression. Here are the number of paths for $h=2,\ldots,7$

Table 1:

• h=2, 4 paths
• h=3, 17 paths
• h=4, 68 paths
• h=5, 259 paths
• h=6, 950 paths
• h=7, 3387 paths

### A more general problem:

Now consider we can move on all the diagonal axes. For example consider an $4\times 4$ lattice. From $(0,0)$ we can go to $(1,0)$, $(1,1)$, $(1,2)$ or $(1,3)$. Lets denote these diagonal moves with $a$-diagonal. Therefore, $(0,0) \rightarrow (1,0)$ is a $0$-diagonal move, $(0,0) \rightarrow (1,1)$ is a $1$-diagonal move, $(0,0) \rightarrow (1,2)$ is a $2$-diagonal move, $(0,0) \rightarrow (1,3)$ is a $3$-diagonal move, etc.

Denote the set of all paths that start from the left boundary $(0,a)$ and end to the right boundary $(h-1,b)$, $b \in [0,h-1]$, and have at least one $a$-diagonal move but not an $(a+1)$-diagonal move with $\mathcal{B}_a$. The problem statement is: Calculate the number of paths in each $\mathcal{B}_0, \mathcal{B}_1,\ldots,\mathcal{B}_{h-1}$.
(Note that the numbers in Table 1 give $\mathcal{B}_0 + \mathcal{B}_1$). The following table shows the values for $h=2$ to $h=7$:

Any hint on how to approach this would be greatly appreciated.

Edit: The movitation for this problem is to calculate the number of piecewise linear functions $f:[0,1]\rightarrow [0,1]$ that have a maximum derivative of 0 (given by $\mathcal{B}_0$), 1 (given by $\mathcal{B}_1$), $\ldots$, $h-1$ (given by $\mathcal{B}_{h-1}$).

#### Solutions Collecting From Web of "On an $h \times h$ square lattice, count all the paths from $(0,a)$ to $(h-1,b)$, $a,b \in$, with diagonal moves allowed"

The only real difficulty here is producing a nice formula.

Write down a row of $h$ ones: $$1\quad1\quad1\quad\ldots\quad1\quad1\quad1$$
Then write down, under each number, the sum of the two/three numbers directly above or one place to the side: $$2\quad3\quad3\quad\ldots\quad3\quad3\quad2$$
And repeat this $h-1$ times. The final row will sum to the number desired. So you can find even by hand that for $h=8$, the answer is $11814$. Your more general problem can be solved similarly, summing the three/four/five nearest numbers instead.

The OEIS link given in the comments has a few formulas. The first one is in terms of Motzkin numbers, which are themselves quite difficult to give a closed formula for. The simplest recurrence is one by Václav Kotěšovec: $$a_n = \frac{(10n^2-39n+23)a_{n-1}-3(2n^2-n-9)a_{n-2}-9(n-3)(2n-5)a_{n-3}}{(n-1)(2n-7)}$$