Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
add comment

2 Answers 2

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

share|improve this answer
    
Thank You for help. –  guram Dec 13 '10 at 22:53
add comment

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.

share|improve this answer
    
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
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. –  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
show 1 more comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.