Catalan数&Polya定理

下午在图书馆看了一下午组合数学,就复习了下高中就学过的“m个元素可重复地取n个的组合数”,”网格上的最短路径数”之类的。时间过得太快了。我看的是《组合数学与图论》和《组合数学笔记》,后者对我来说太难了,里面大量的符号都不认识,还有好多新概念,不愧是科学出版社出版的。我就看了它讲Catalan数的一节,一开始就指出了七个问题:它们都跟Catalan数有关。最经典的还是

1)三角剖分:把一个凸N边形分成若干个三角形的方案数

2)乘法结合:N个数相乘有多少种结合方式

3)网格路径:从(0,0)—>(N,N)有多少种路径不经过直线y=x

把它们联系在一起的是这么一个性质:假设我现在很饿要吃掉N块面包,但是太干了,必须要有牛奶才能吃下去。喝一口牛奶吃一块面包,要保证先有牛奶垫着肚子才能继续吃面包。所以任何时刻,喝牛奶的口数x一定要大于吃面包的块数y。可见开始必须要先喝牛奶,最后是吃掉一块儿面包,然后我的早饭就吃完了。

这个模型跟2)、3)是一样的,2)中,N个数相乘,要加N-1对括号,任何一个位置都要保证左括号数大于右括号数。3)中,要沿着x轴和y轴各走N步,由于中间不能碰到y=x,需要保证沿y走的步数始终大于沿x走的步数。与此类似的模型还有很多,比如我想到了堆栈的性质。假设有N个元素要顺序入栈,但出栈顺序不确定,共有2*N个操作数,问有多少种出栈顺序。在这里任何时刻入栈的元素必须大于出栈的元素。刚学堆栈的时候总是会问某一个出栈顺序是否可行,我当时就考虑究竟有多少可行多少不可行,还在CSDN上(当时还上CSDN)发了个帖,结果竟然没人明白我说的什么,要么就是说没有一般解法。我当时竟然一步步考察四个元素的24种情况,准确地指出有14种排列是可以出现的。Wink,唉这只能说明我比较有耐心~14刚好是Catalan_4=C(4,8)/5=14。

第一个就只能根据递推关系(其它两个也有相同的递推关系)看出些东西了,设答案是F(n),那么有F(n)=∑F(i)F(n-i),1<=i<=n-1

如果要解这个递推方程的话就只能用母函数了(据我了解),要么就直接跟最后的答案比较:答案C(n,2n)/(n+1)满足这个递推关系所以。。。额,母函数我还不是很会,相乘的时候还不理解。人说母函数就是个工具,看起来用的是幂级数,但其实幂级数并不一定要收敛!这个,我觉得太不显然了,不收敛的东西是不能随便推来推去的,但人家母函数有理论基础:对乘法构成交换群什么的~

好吧,以上全废话。开始主题。其实这个主题我一点儿也不明白,我有太多的疑问了。但觉得Polya这个定理还算巧妙,就写个代码实现下。

它主要解决用C种颜色给N个球染色的问题。若球排成一排,那么有的排列就是多余的,可以通过旋转得到(圆排列)。如果再假设,一个圆排列从上往下看和从下往上看是同一个排列(项链排列),又会有一些是多余的。

现在给N个球编上号码1…N,以上所说的每次变换其实对应着一个置换,比如将(123456)—>(345612),群中每个置换都可以写成循环的形式,这个置换就可以写成(135)(246),有两个循环,这个置换是旋转。

再考虑翻转,对于这个例子,将六个球放在正六边形六个顶点,它有六条对称轴:3条通过相对顶点,例如(123456)沿通过1,4号球的对称轴翻转变为(156432),该置换有两个循环(1)(4)(2356);三条通过对边中点例如(123456)沿过12和45中点的对称轴翻转后变为(165432),分解为4个循环(1)(4)(26)(35)。在考虑奇数顶点在翻转时候的情况:只有过每个顶点的N条对称轴,(12345)—>(15432),分解为(1)(25)(34),3个循环。然后可以推广到所有的整数反转时候的表现了。

其实上面无缘无故来了这么一堆谁都受不了,但它们是有用的,所以只好忍了。Polya定理指出,C种颜色给N个球染色,假设要求的方案中有G个置换使方案保持不变(即这G个置换不论作用到哪个已知的方案上都不会改变这个方案),每个置换可分解成c_i个循环,那么方案总数是(C^(c_1)+C^(c_2)+C^(c_3)+…+C^(c_G))/G

光知道了这个还不能写出高效的代码,循环数怎么求呢?结论是,旋转k个球的置换的循环数是gcd(k,N)。N为奇数时N个翻转置换的循环都是(N+1)/2。N为偶数时,有N/2个翻转置换的循环是N/2(对称轴过顶点),N/2个翻转置换的循环是N/2+1(对称轴过中点)。

于是对于旋转翻转是同样的方案的情况,总方案数是

{C^gcd(0,N)+C^gcd(1,N)+…+C^gcd(N-1,N)+N*C^((N+1)/2)}/(2*N)             N为奇数

{C^gcd(0,N)+C^gcd(1,N)+…+C^gcd(N-1,N)+(N/2)*C^(N/2)+(N/2)*C^(N/2+1)}/(2*N)         N为偶数