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）* 置換內最小元素。但是解題報告說還有一種可能是這個置換內的最小元素和整個數列的最小元素交換，然后利用那個最小元素進行交換。這的確會產生更優的解，我原來怎么想不到呢！
題目代碼：