下午在图书馆看了一下午组合数学，就复习了下高中就学过的“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种排列是可以出现的。
，唉这只能说明我比较有耐心~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为偶数
Prime8051 