排列问题

northwolves

将数字1-m*n 放入m*n的矩阵中,使得对于其中任意元素c, 都大于其上面的元素a和左面的元素b,如下图: 共有多少种排列方法?

northwolves

m=2时,结果似乎等于: $(2n)!/n!(n+1)!$

KeyTo9_Fans

m=2是卡特兰数列$\frac{(2n)!}{n!(n+1)!}$

northwolves

有什么好的计算方法?

KeyTo9_Fans

我仅仅只排了一下两列的，发现是括号序列。 第一列对应左括号的位置，第二列对应右括号的位置。 例如： 1 3 2 4 5 6 对应 (())() 即第1、2、5位为左括号，3、4、6位为右括号。 所以就成卡特兰数列了。 m列的还没想出来。

rayfekeeper

x行y列的数p(x,y)必须满足充要条件： $ xy<=p(x,y)<=mn-(m-x+1)(n-y+1)$

northwolves

因为是只求排列总数,应该有一些很快的算法,动态规划?

KeyTo9_Fans

对于较小的m、n，结果如下： 3 1: 1 3 2: 5 3 3: 42 3 4: 462 3 5: 6006 3 6: 87516 3 7: 1385670 3 8: 23371634 4 1: 1 4 2: 14 4 3: 462 4 4: 24024 4 5: 1662804 4 6: 140229804 5 1: 1 5 2: 42 5 3: 6006 5 4: 1662804 5 5: 701149020 上述结果如果正确的话，那么所求排列方案数等于 $\frac{(nm)!}{\frac{n!}{0!}\frac{(n+1)!}{1!}\frac{(n+2)!}{2!}...\frac{(n+m-1)!}{(m-1)!}}$ 上述公式是根据前面的结果归纳得出来的，所以即使正确也只能作为一个猜想，需要加以证明才能作为最终结论。

mathe

http://www.research.att.com/~nja ... =0&language=english

gxqcn

由楼上给出的链接里面的公式，很容易变换出 8# 里的形式。 个人认为 KeyTo9_Fans 给出的形式更美好，也便于计算。