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$:

Solution for h=2,3,4,5,6,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}$).

  • $\begingroup$ I strongly suspect that you meant to write $(h-1,b)$ instead of $(b,h-1)$ and that the allowed moves are $(1,0), (1,1), (1,-1)$. $\endgroup$ – Andrew Woods Mar 25 '15 at 15:39
  • $\begingroup$ @AndrewWoods fixed the $(h−1,b)$. Thanks! I'm not sure what you mean with $(1,-1)$. Considering only up to 1-diagonal moves, if we are on $(2,3)$ we can go to $(3,3)$ (right), $(3,4)$ (up 1-diagonal), or $(3,2)$. $\endgroup$ – Panagiotis Panagi Mar 25 '15 at 15:47
  • 1
    $\begingroup$ This is oeis.org/A081113 and you can find several recurrences and formulas there. $\endgroup$ – J. J. Mar 25 '15 at 16:03

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)}$$


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.