polya定理是组合数学中比较难的一部分。首先需要对置换群、集合论有一定的了解，这样有助于理解burnside引理的证明。其次，polya定理只是对于在环上存在旋转、反射等等价的变换的一种计数方法，实际的题目中很多需要其他的知识来进行辅助。
　　环上的计数主要就是处理置换 -> 着色这种情况。很关键的一点是同一循环内着色相同。因此很多题目就在置换和着色上下文章。
　　最最简单的polya定理题目是置换数目很少，每种颜色不限，这种情况下只需手工数出所有的置换就可以了，一般就是一个公式。
　　难一点的要么是颜色数有限，需要用排列组合的知识或动态规划来帮助计数；要么是置换非常多，需要利用数论的知识来优化。当然还有其他的题型，比如对于相邻着色的限制，这样的题目就很困难了。

polya题目：
HOJ 2084 The Colored Cubes
HOJ 2647 Megaminx
POJ 1286 Necklace of Beads
POJ 2409 Let it Bead
TOJ 2795 The Queen's New Necklaces
HDU 1812 Count the Tetris
UVa 11255 Necklace
POJ 2154 Color
POJ 2888 Magic Bracelet
UVa 10601 Cubes
NUAA 1110 n阶常系数线性齐次递推关系的解法有很多，特征方程法、生成函数法，但是对于编程最实用的是矩阵解法。
我们定义所要求的f(n) = Ak-1 * f(n - 1) + Ak-2 * f(n - 2) + ... + A0 * f(n-k)，其中f(0)...f(k-1)的初值已经给好。
构造k * k的矩阵M：

其中A =(Ak-1 Ak-2 ... A1)，I是单位矩阵。
然后构造一个k * 1列向量b：

这样，M * b之后b0的值就是f(k)，以此类推，M ^ n * b之后b0的值就是f(k-1+n)，算法复杂度O(k ^ 3 * logn)。

主要分成以下几个部分：
　　排列组合与容斥原理
　　二项式定理
　　递推关系与生成函数
　　polya定理

1.排列组合与容斥原理
排列组合里面的4个重要的基本原理：加法原理、乘法原理、减法原理、除法原理
前面两个最为基本，后面两个是根据前两个派生出来的。乘法原理有的时候的应用很巧妙，可以作为一种打开思路的办法。
基本的排列组合之后，接下来引出了多重集。多重集的排列组合是一个很经典的问题，总结如下：
多重集的排列：
　　全排列的话只需应用除法原理就可以了。n个元素的多重集的r排列需要利用指数生成函数来做。
多重集的组合：
　　n个元素的多重集的r组合，如果r小于等于任何一个元素可选的个数，那么就归结为经典的不定方程的解数问题，可以利用“隔板法”来做。结果就是一个组合数。如果r大于某些元素的可选个数，那么一种方法是利用容斥原理，一种方法还是要依靠生成函数（编程序的时候可以用动归做）。
如果是一个环形的排列组合，那么问题就困难许多，要利用置换群和polya定理。
　　单纯的依靠四项基本原理来计数，有的时候会显得力不从心，这个时候就需要容斥原理的帮助。容斥原理特别适合解决若干限制条件的交、并问题，也是打开思路的一种方法。
　　利用容斥原理解决的经典问题有：错排问题，带禁止位置的排列。禁位排列总觉得用容斥原理解决的不够优美，不知道有没有可以编程的数学方法。还有一个困惑的问题就是容斥原理和mobius反演的关系，那个地方好晦涩。。
　　跟排列组合相关的还有就是生成排列和组合。生成排列利用那个什么字典序法好像足够了，编程好实现。生成组合方法类似。

2.二项式定理
有很多公式，用的时候可以现查。终于知道了三角形数原来跟排列组合有关，而且是一个很简洁的公式。
很多公式的推导用的思想很妙。有一个很好的思想就是把(1 + x) ^ n利用二项式定理展开，然后求导、求积分，居然可以导出很多不可思议的公式。
还有一个很重要的定理就是pascal定理，pascal递推式很有用（展开后有两种形式，一种是上下限均不定，一种是下限不定），可以解决很多组合数的求和问题。
另外一个重要的定理就是牛顿二项式定理，在生成函数中应用广泛，可就是推导起来有点繁。

3.递推关系和生成函数
　　求解线性递推关系的特征方程的方法还是有一定价值的，但是编程不适用。n解线性齐次递推方程有矩阵解法。稍微复杂点的递推关系（非线性），特征方程就不够用了，必须祭出生成函数这个有力的武器。感觉生成函数实在是太优美、太强大了。生成函数的关键就是要把多项式拆分成(1-rx)^n这种形式，这样就可以利用牛顿二项式定理展开了。
　　在特殊计数序列里面提到了盒装球问题。将p个不同的球放入k个相同的盒子（每个盒子非空）的方法数是第二类Stirling数S(p, k)；将p个相同的球放入k个相同的盒子（每个盒子非空）的方法数是分拆数，可以归结为整数划分问题，用动态规划求解；将p个不同的盒子放入不同的k个盒子并且每个非空的方法数为k! * S(p, k)。
　　有几个很经典的递推关系：斐波那契数列、Catalan数（几种经典的形式：三角剖分数、二叉生成树个数、+1-1序列、加括号序列等等）、Stirling数（两种，第二种比较常用）、汉诺塔、n个圆切割平面数、n条直线k个交点切割平面数等等。此外，格路径中提到的平移、反射和一一对应这三种分析问题的方法也很值得借鉴。

4.polya定理

比较复杂，过一阵子好好总结下。 偏序集的两个定理：
定理1 令（X,≤）是一个有限偏序集，并令r是其最大链的大小。则X可以被划分成r个但不能再少的反链。
其对偶定理称为Dilworth定理：
定理2 令（X,≤）是一个有限偏序集，并令m是反链的最大的大小。则X可以被划分成m个但不能再少的链。
说白了就是 链的最少划分数=反链的最长长度
相关的题目有pku 1065，pku 3636，pku 1548。
这三个题目可以归结为：
　　给定n个二元组(x, y)，问存在最少多少个划分使得每个划分里面的二元组都满足x1 <= x2并且y1 <= y2。
　　如果定义x1 <= x2 && y1 <= y2为偏序关系的话，那么问题就转化成求这个集合的链的最少划分数。可以通过找最长反链长度来解决，这里的反链关系是x1 > x2 || y1 > y2。如果把n个二元组按照x递增排序，相同的x按照y递增排序，那么我们只需对y找到一个最长递减子序列就是所求的答案，复杂度O(nlogn)。对于相同的x之所以按照y递增排序是因为这里偏序关系带等号，这样相同的x其实可以划分到一起，把y按照递增排序就可以使得相同的x最多只选择一个y。
　　还有的题目要求满足x1 < x2 && y1 < y2，这就需要把偏序关系相应修改。修改之后对于相同的x，每一个都会被划分到不同的集合（因为相等是不满足偏序关系的），所以这里的排序关系要改一下，x相同的y要按照降序排列，这样求一个最长不递增子序列就是答案，y递减保证可能会有多个x相同的二元组选入到结果中。
　　可惜对于贪心做法的正确性依然想不出来>.< 　　做得很郁闷的一道题。我开始已经想到是要用置换来算，但是提交后总是WA。查代码查了N久也没有发现错误，感觉算法又没有问题。后来找到往年的解题报告，才发现我的基本思路没错，但是少考虑了一种情况。我之前认为最小代价等于一个置换内所有元素和 +（元素个数-2）* 置换内最小元素。但是解题报告说还有一种可能是这个置换内的最小元素和整个数列的最小元素交换，然后利用那个最小元素进行交换。这的确会产生更优的解，我原来怎么想不到呢！
题目代码：