5
$\begingroup$

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

2 Answers 2

6

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

5

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.

  • 0
    Thanks. But is there a way, to compute this in faster way?2010-12-13
  • 0
    @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?2010-12-13
  • 0
    @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"?2010-12-13
  • 1
    @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.2010-12-13
  • 0
    @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.2010-12-13
  • 0
    OK, I think, that the best optimization I can do is preprocessing, because either backtracking method takes long time to find solution for _big_ $m, n$ or computation directly from the formula requires a lot of big-numbers calculations (factorials).2010-12-14