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
    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