Given the integers from $1 \ldots mn$, how many ways are there to arrange those integers as an $m \times n$ matrix, using each one once, such that each row is always increasing going from left to right, and each column is always increasing going top to bottom?
Here is my work so far:
The problem is trivial for $n = 1$ (or $m = 1$) since the numbers must be in numerical order.
I have solved the problem for $n = 2$ (or $m=2$); the ways of arranging the numbers following those rules are isomorphic to random walk paths of $2m$ steps ending at the origin, and never going below zero, thus the answer is the Catalan number $C_m$. (The isomorphism is simple: Putting the next number in the top(bottom) row corresponds to taking a walk step in the positive (negative) direction.)
For $n = 3$, I have tried to find an isomorphism involving random walks on a hex grid, or involving 2-D walks, with no success.
It appears that for $mn =3 \times 3$ there are $40$ allowed arrangements, but that is just a brute force (and possibly error prone) observation.
Best Answer
If $n=3$, it’s the number of walks from $(0,0,0)$ to $(m,m,m)$ where each point $(i,j,k)$ on the walk satisfies $i\ge j\ge k$. The integer $a_{1d}$ at position $(1,d)$ of the matrix indicates that the $a_{1d}$th step of the walk was in the direction $(1,0,0)$; the entry $a_{2d}$ indicates that the $a_{2d}$th step was in the $(0,1,0)$ direction, and similarly for $a_{3d}$. The $a_{cd}$th step of the walk was the $d$th one the $c$ direction, which cannot have occurred until after the first $d$ steps in each direction $c'<c$ and after the first $d-1$ steps in direction $c$, so $a_{st}<a_{s't'}$ whenever $(s,t)$ precedes $(s',t')$ in lexicographical order.
For $n>3$, the walk proceeds along $n$-dimensional lattice points similarly.
The resulting array of numbers of distinct paths, $T(m,n)$, listed along antidiagonals, form sequence A060854 in the Online Encyclopedia of Integer Sequences.