Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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):
[2] Catalan numbers (Wikipedia):
[3] Catalan numbers (OEIS):

share|cite|improve this question

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

share|cite|improve this answer
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.

share|cite|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
@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

Your Answer


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.