完满单调矩阵计数问题

hujunhua

定义（完满单调矩阵Perfect Monotonic Matrix）满足以下条件的实矩阵$A_{m×n}$称为完满单调矩阵（PMM）： (1)每一行的n个数严格单调递增； (2)每一列的m个数严格单调递降； (3)m×n个矩阵元素刚好来自自然数前段Range(mn):={1, 2, 3, ..., mn-1, mn}。 记不同的m×n阶完满单调矩阵的总数为PMM(m,n)，求PMM(m,n)的公式。 几点说明： 1、这是从本论坛的一个帖子http://bbs.emath.ac.cn/thread-2931-2-1.html中分离出来的问题。这里定义的PMM是那里定义的二叉矩阵的一种特例，也可以叫做完满二叉矩阵。 2、单调矩阵（Monotonic Matrix）这个名称已经被使用，并且仅我所发现的就有三种本质不同的定义， ------ 《矩阵论》（方保镕等著，清华大学出版社2004年11月）中的定义：逆为正数矩阵的 n阶矩阵。 ------Mathworld网站的定义 ------经典面试题 之 在单调矩阵中查找元素，此题中的定义基本与本帖相同。 ------http://everything2.com/title/hard+interview+questions第26题Monotonic matrix solution。这是《算法与数据结构》课的一道练习题。

hujunhua

偶手工计算的结果： PMM(1,n)=1 PMM(2,2)=2 PMM(2,3)=5 PMM(2,4)=14 PMM(3,3)=64

zgg___

喜欢hujunhua的问题和定义，很透彻，呵呵。 胡乱发表议论如下： 1、如果将定义的第2条中的“降”字改为“增”字，那么问题的答案PMM()不变； 2、定义“PMM涂色”为这样一种将m*n的白色格子全部涂黑的方式：对于某白色格子，只有当它左面和上面的格子是黑色格子或者没有格子的时候才可以将其涂黑。不同的格子图色顺序为不同的方式，那么方式的总数T()等于PMM()； 3、对于一个已知的PMM，所对应“那个帖子中mathe的9层问题”的序列数也等于T()，因为将序列中数字一次放入格子的方式，可以采用PMM涂色方式； 4、由上面，强化了那个帖子中15层的说法。呵呵。

mathe

是的，这个应该是一个已经解决的（并且为一些人熟知的）问题

Lwins_G

首先应当注意到 这个矩阵是Young Tableaux的特例。 而Young Tableaux的固定元素的总方案数的求法是为人所知的，此即钩子公式 (Hook-length Formula)。出人意料，该公式形式简单，但是证明并不是显然的。大家可尝试寻找一个不太复杂的证明。 相关链接： http://en.wikipedia.org/wiki/Young_tableau 内有对于Young Tableaux与钩子公式的详细介绍。

BeerRabbit

5# Lwins_G 精彩而优美！ # -*- coding: utf-8 -*- """ Hook-length Formula """ # MainFunction : Calculate the Number of Young Matrix using Hook-length Formula def Hook(n,m): HookProd=1 for i in range(1,n+1): for j in range(1,m+1): HookProd=HookProd*((n+m)-(i+j)+1) return Fact(n*m)/HookProd # SubFunction : Calculate the Factorial of Integer Number n def Fact(n): if n==0: return 1 else: return n*Fact(n-1) # Test row=int(raw_input('Input Row Number n = ')) for col in range(1,20): print 'When Col Number = ',col,', the result is = ',Hook(row,col) Input Row Number n = 2 When Col Number = 1 , the result is = 1 When Col Number = 2 , the result is = 2 When Col Number = 3 , the result is = 5 When Col Number = 4 , the result is = 14 When Col Number = 5 , the result is = 42 When Col Number = 6 , the result is = 132 When Col Number = 7 , the result is = 429 When Col Number = 8 , the result is = 1430 When Col Number = 9 , the result is = 4862 When Col Number = 10 , the result is = 16796 When Col Number = 11 , the result is = 58786 When Col Number = 12 , the result is = 208012 When Col Number = 13 , the result is = 742900 When Col Number = 14 , the result is = 2674440 When Col Number = 15 , the result is = 9694845 When Col Number = 16 , the result is = 35357670 When Col Number = 17 , the result is = 129644790 When Col Number = 18 , the result is = 477638700 When Col Number = 19 , the result is = 1767263190

BeerRabbit

2# hujunhua P( 1, 1)=1 P( 2, 2)=2 P( 3, 3)=42 P( 4, 4)=24024 P( 5, 5)=701149020 P( 6, 6)=1671643033734960 P( 7, 7)=475073684264389879228560 P( 8, 8)=22081374992701950398847674830857600 P( 9, 9)=220381378415074546123953914908618547085974856000 P(10,10)=599868742615440724911356453304513631101279740967209774643120000

hujunhua

P(3,3)=42? 我手工算錯了么，也不知道当初推算的了。