10
$\begingroup$

Given $N$, I would like to know the number of matrices constructed from $1$ to $N$ which satisfy the following conditions:
1. Each row entry should be in increasing order.
2. Each column entry should be in increasing order.

For example: when $N = 4$, there are 4 matrices which satisfy these conditions:
1. $\left( \begin{array}{c} 1 & 2 & 3 & 4\end{array} \right) $
2. $\left( \begin{array}{c} 1 \\ 2 \\ 3 \\ 4\end{array} \right) $
3. $\left( \begin{array}{cc} 1 & 2 \\ 3 & 4\end{array} \right) $
4. $\left( \begin{array}{cc} 1 & 3 \\ 2 & 4\end{array} \right) $

My observations:
$N$ should be a composite number to construct a valid matrix.
If a matrix $A$ satisfies the condition then $A^T$ also satisfies the condition.

$\endgroup$
5
  • 1
    $\begingroup$ Why should $N$ be composite if we are including row and column vectors like you have shown? Either way it doesn't matter, we always get $2$ for $N$ prime. $\endgroup$ – muzzlator Mar 21 '13 at 15:16
  • $\begingroup$ you can construct a valid matrix when $N$ is prime. But of course, for $N$ prime, the answer is always 2 :-) $\endgroup$ – Djaian Mar 21 '13 at 15:16
  • $\begingroup$ Perhaps you can ask firstly for $N$ a square prime, do all the larger numbers have to be on the outside? Then make a conjecture on the number for $N$. Hm, the answer is no :( $\endgroup$ – muzzlator Mar 21 '13 at 15:19
  • 1
    $\begingroup$ Such a matrix is called a Young tableau. That should help you search for an answer. $\endgroup$ – Samuel Mar 21 '13 at 15:37
  • $\begingroup$ Agreed. When $N$ is prime, the number of matrix is 2 :) $\endgroup$ – Learner Mar 21 '13 at 16:08
3
$\begingroup$

You should read about Young Tablau and specifically the Hook Length Formula. You are asking about the number of standard Young tableau of rectangular shape. The hook length formula is precisely what you want, and is where the formula brogrenkp posted comes from.

$\endgroup$
1
$\begingroup$

This seemed like a good one for the OEIS. I searched the first $7$ elements $(1,2,2,4,2,12,2)$.

http://oeis.org/A067228

Hopefully this will help get you started and you can justify the formula for the $Nth$ term which is given at the OEIS by Alois P. Heinz as $N! \sum_{i|N}\left(\prod_{k=0}^{\frac{n}{i}-1}\frac{k!}{(i+k)!}\right)$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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