论坛 › 算法交流 › 排列问题

northwolves 发表于 2009-12-1 18:54:52

排列问题

将数字1-m*n 放入m*n的矩阵中,使得对于其中任意元素c, 都大于其上面的元素a和左面的元素b,如下图:



共有多少种排列方法?

northwolves 发表于 2009-12-1 19:11:24

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

KeyTo9_Fans 发表于 2009-12-1 19:26:06

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

northwolves 发表于 2009-12-1 19:33:00

有什么好的计算方法?

KeyTo9_Fans 发表于 2009-12-1 19:56:46

我仅仅只排了一下两列的，发现是括号序列。

第一列对应左括号的位置，第二列对应右括号的位置。

例如：

1 3
2 4
5 6

对应

(())()

即第1、2、5位为左括号，3、4、6位为右括号。

所以就成卡特兰数列了。

m列的还没想出来。

rayfekeeper 发表于 2009-12-1 20:16:18

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

northwolves 发表于 2009-12-1 20:35:01

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

KeyTo9_Fans 发表于 2009-12-1 21:11:37

对于较小的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 发表于 2009-12-2 08:13:55

http://www.research.att.com/~njas/sequences/?q=1%2C42%2C6006%2C1662804%2C701149020&sort=0&fmt=0&language=english

gxqcn 发表于 2009-12-2 08:39:15

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

查看完整版本: 排列问题