Count of Matrices
 

Call an m x n matrix of real numbers "ascending" if
every row and column is in ascending (increasing) order,
i.e. a[sub]i+1,j[/sub] > a[sub]i,j[/sub] and a[sub]i,j+1[/sub] > a[sub]i,j[/sub].

Call an m x n matrix "sequential" if its m*n entries consist of
all the integers 1 through mn inclusive.

How many ascending sequential m x n matrices are there?

(I think this is a hard problem. I think I have a partial answer.)

[url]http://mathworld.wolfram.com/YoungTableau.html[/url]

[url]http://mathworld.wolfram.com/HookLengthFormula.html[/url]

I think that's the answer you're looking for. The definition given for hook length formula doesn't explicitly mention it, but the formula tells you the number of [I]standard[/I] Young tableau there are for a given Young diagram. Your question essentially asks "How many standard Young tableaux are there corresponding to the Young diagram that is an mxn rectangle?"

I'd suggest you keep working for a while before you look at the answer and proofs of it. I don't know for sure, but on the surface it at least seems doable if you're sufficiently interested in the question/subject to put some time and thought into it.

That general formula gives (mn)! / (product of hook lengths),
which for an m x n rectangle is in a relatively simple form.
In particular for n x 2 (or 2 x n) rectangles, the formula gives
(2n)! / (n! * (n+1)!), i.e. the Catalan numbers 1,2,5,14,42,etc.
This much I had confirmed empirically.