Let's say, we have an array/matrix $n \times m$ and we need to find, how many ways can we fill this array with numbers from $\{ 1, \ldots , m\cdot n \}$, but:
1) every number can be used only 1 time
2) every column and every row should be sorted in increasing order
For example, if we have $n = m = 3$, there are 42 different ways to do this.
I was thinking about this problem, but I can't find out any simple formula to compute this for every $n, m$.
We can solve this problem by writnig a program that uses backtracking method/algorithm [1] but it has huge complexity and problem is solved by computer, and I want to know, how to do this by hand.
Sombody told me, that in this problem I can use some kind of Catalan numbers [2] [3], but I'm not sure about this method.
So, what do You think about this problem and its solution?
[1] Backtracking (Wikipedia): http://en.wikipedia.org/wiki/Backtracking
[2] Catalan numbers (Wikipedia): http://en.wikipedia.org/wiki/Catalan_number
[3] Catalan numbers (OEIS): http://oeis.org/A000108