# Array of numbers, how many solutions/ways?

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.

[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

-

These are Young tableaux. OEIS has the numbers. For the square case, see A039622. For the rectangular case, see A060854

-
Thank You for help. – guram Dec 13 '10 at 22:53

You are counting the number of standard Young tableaux of shape $(m, m, m, ...)$ (where $m$ occurs $n$ times). The formula that counts these is called the hook length formula. It correctly reproduces the answer

$$\frac{9!}{5 \cdot 4 \cdot 4 \cdot 3 \cdot 3 \cdot 3 \cdot 2 \cdot 2} = 42$$

for the example you gave. The general formula seems annoying to write down. In the special case $n = 2$ you get Catalan numbers; this is a nice exercise and it is worth trying to prove this with and then without the hook length formula.

-
Thanks. But is there a way, to compute this in faster way? – guram Dec 13 '10 at 22:52
@guram: you can probably deduce a recursive formula, either from the hook-length formula or directly. But I don't know what you mean by "faster way." For small values of m, n these formulas work quite nicely, and for large m, n the problem is just hard; it is just hard to compute factorials exactly. Do you want an asymptotic formula? – Qiaochu Yuan Dec 13 '10 at 22:57
@Qiaochu Yuan: as You wrote: "it is just hard to compute factorials exactly". Is there a way to avoid computing factorials by using other formula? And, what do You mean by "small values"? – guram Dec 13 '10 at 23:01
@guram: I don't know, but my guess is no. By small values I meant, say, single-digit (really small). You asked for a method that works by hand; this is such a method. That's all. If what you actually want is something else, you should say so. – Qiaochu Yuan Dec 13 '10 at 23:12
@Qiaochu Yuan: Now I am interested in fast algorithm to solve this problem. I know it's possible with backtracking method, but I'm not sure, how to do this. Or is there another method to find the answer. – guram Dec 13 '10 at 23:21