每行、每列都是顺序的矩阵

hbghlyj

将1到$mn$不重复填入$m×n$矩阵, 使每行、每列都是顺序的方法数?
$m×n$和$n×m$按矩阵转置一一对应, 所以只需考虑$m≤n$的情形.
$1×n$ 有 1 种.
$2×2$ 有 2 种.
$\pmatrix{1&2\\3&4}\pmatrix{1&3\\2&4}$
$2×3$ 有 5 种.
$\pmatrix{1&2&3\\4&5&6}\pmatrix{1&2&4\\3&5&6}\pmatrix{1&2&5\\3&4&6}\pmatrix{1&3&4\\2&5&6}\pmatrix{1&3&5\\2&4&6}$
$2×4$ 有 14 种.
$\pmatrix{
1 & \square  & \square  & 7 \\
\square  & \square  & \square  & 8}$有5种
$\pmatrix{
1 & \square  & 5 & 6 \\
\square  & \square  & 7 & 8}$有2种
$\pmatrix{
1 & \square  & 4 & 6 \\
\square  & 5 & 7 & 8}$有2种
$\pmatrix{
1 & \square  & \square  & 6 \\
4 & 5 & 7 & 8}$有1种
$\pmatrix{
1 & \square  & 4 & 5 \\
\square  & 6 & 7 & 8}$有2种
$\pmatrix{
1 & \square  & \square  & 5 \\
4 & 6 & 7 & 8}$有1种
$\pmatrix{
1 & \square  & \square  & \square \\
5 & 6 & 7 & 8}$有1种
$3×3$ 有多少种?

1. M = sort(sort(reshape(randperm(9),[3 3])),2,'ascend')

Copy the Code

用Matlab或Octave生成很多这样的矩阵(使用这帖的结论):

hbghlyj

怀疑$2×n$方法数1,2,5,14⋯是Catalan数列

hbghlyj

hbghlyj 发表于 2022-10-15 23:56
怀疑$2×n$方法数1,2,5,14⋯是Catalan数列

哇, 还真是的.
Wikipedia
A Catalan number $C_{n}$ counts Dyck paths with $n$ steps going up (U) interspersed with $n$ steps going down (D), such that at each step there are never more preceding D's than U's. These are in bijection with the Young tableaux of shape $λ = ( n , n )$ $\lambda =(n,n)$: a Dyck path corresponds to the tableau whose first row lists the positions of the U-steps, while the second row lists the positions of the D-steps. For example, UUDDUD correspond to the tableaux with rows 125 and 346.

This shows that $C_{n}=f^{(n,n)}$, so the hook formula specializes to the well-known product formula
\[C_{n}={\frac {(2n)!}{(n+1)(n)\cdots (3)(2)(n)(n-1)\cdots (2)(1)}}={\frac {(2n)!}{(n+1)!\,n!}}={\frac {1}{n{+}1}}{\binom {2n}{n}}.\]

hbghlyj

Czhang271828 发表于 2022-11-1 05:50
3*3 有9!/(5*4*4*3*3*3*2*2*1)=42 种, 这是 Young diagram 的 hook length formula.

integral-domain.org/lwilliams/Applets/Math/YoungDiagrams.php