Given a $n\times m$ grid, which has the number 1 in the upper-left square and a positive integer $1\leq k\leq n+m-1$ in the lower right-square, I am trying to determine in how many ways can the remaining squares be filled in with integers such that they are either constant or increasing in both indices. That is, an array of elements $a_{i,j}$ such that $a_{1,1}=1$, $a_{n,m}=k$ and $a_{i+1,j}$ and $a_{i,j+1}$ are either $a_{i,j}$ or $a_{i,j}+1$.
For instance, for a $2\times 2$ grid, we can have $k=1,2,3$.
The case $k=1$ has only one solution:
$ \begin{matrix} 1 & 1 \\ 1 & 1 \\ \end{matrix} $
The case $k=2$ has four solutions:
$\{ \begin{matrix} 1 & 1 \\ 1 & 2 \\ \end{matrix} \quad,\quad \begin{matrix} 1 & 1 \\ 2 & 2 \\ \end{matrix} \quad,\quad \begin{matrix} 1 & 2 \\ 1 & 2 \\ \end{matrix} \quad,\quad \begin{matrix} 1 & 2 \\ 2 & 2 \\ \end{matrix} \}$
And the case $k=3$ also has only one solution:
$ \begin{matrix} 1 & 2 \\ 2 & 3 \\ \end{matrix} $
Meaning that the $2\times 2$ grid has $6$ solutions in total.
I know that the $1\times n$ grid has $2^{n-1}$ solutions in total, and the $2\times n$ has $2*3^{n-1}$ solutions. However, I still can't find a formula as a function of $k$ for a general $n\times m$ array.
The $3\times n$ case has $$Tr\{( \begin{matrix} 2 & 2 \\ 2 & 3 \\ \end{matrix} )^n. (\begin{matrix} 2 \\ 2 \\ \end{matrix})\}$$ solutions in total.
The problem is similar to that of plane partitions (although not exactly the same), and can also be thought as a problem of determining non-intersecting lattice paths (i.e., how many non-intersection north-east lattice paths can divide a $n\times m$ lattice into k regions. A region which contains all the adjacent 1's, a region with the 2's,.... The lattice paths can share a vertex but can't cross each other).
Just as an additional example, one of the solutions for a $3\times3$ array with $k=4$ is
$ \begin{matrix} 1 & 1 & 2 \\ 2 & 2 & 3 \\ 3 & 3 & 4 \\ \end{matrix} $
There are in total $82$ solutions for the $3\times3$ case.