# How many matrices exist with this increasing row and increasing column condition?

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.

• 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. – muzzlator Mar 21 '13 at 15:16
• you can construct a valid matrix when $N$ is prime. But of course, for $N$ prime, the answer is always 2 :-) – Djaian Mar 21 '13 at 15:16
• 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 :( – muzzlator Mar 21 '13 at 15:19
• Such a matrix is called a Young tableau. That should help you search for an answer. – Samuel Mar 21 '13 at 15:37
• Agreed. When $N$ is prime, the number of matrix is 2 :) – Learner Mar 21 '13 at 16:08

This seemed like a good one for the OEIS. I searched the first $7$ elements $(1,2,2,4,2,12,2)$.
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)$.