Burnside引理與Polya定理

感覺這兩個東西好鬼畜= = ，考場上出了肯定不會qwq。不過還是學一下吧用來裝逼也是極好的

群的定義

與下文知識無關。。

給出一個集合$G = \{a, b, c, \dots \}$和集合上的二進制運算"$*$"，并滿足

(1).封閉性：$\forall a, b \in G, \exists c \in G, a * b = c$

(2).結合律：$\forall a, b, c \in G, (a * b) * c = a * (b * c)$

(3).機關元：$\exists e \in G, \forall a \in G, a * e = e * a = a$

(4). 逆元：$\forall a \in G, \exists b \in G, a * b = b * a = e$，記$b = a^{-1}$

則稱集合$G$在運算“$*$”之下是一個群，簡稱$G$是群

置換

$n$個元素， $1, 2, \dots n$之間的一個置換$\begin{pmatrix} 1 & 2 & \ldots n \\ a_{1} & a_{2} & \ldots a_{n} \end{pmatrix}$表示$1$被$1$到$n$中的某個數$a_1$取代，$1$被$1$到$n$中的某個數$a_2$取代，$\dots$直到$n$被$1$到$n$中的某個數$a_n$取代，且$a_1, a_2, \dots a_n$互不相同

置換群

置換群的标準定義涉及到新定義，在OI中你可以簡單的認為

置換群的元素是置換，運算是置換的連接配接，

例如$$\begin{pmatrix} 1 & 2 & 3 & 4 \\ 3 & 1 & 2 & 4 \end{pmatrix}\begin{pmatrix} 1 & 2 & 3 & 4 \\ 4 & 3 & 2 & 1 \end{pmatrix}=\begin{pmatrix} 1 & 2 & 3 & 4 \\ 2 & 4 & 3 & 1 \end{pmatrix}$$

解釋一下：

在第一個置換中，$1$變為$3$，第二個置換中$3$變為$2$，是以$1$先變為$3$再變為$2$

在第一個置換中，$2$變為$1$，第二個置換中$1$變為$4$，是以$2$先變為$1$再變為$4$

在第一個置換中，$3$變為$2$，第二個置換中$2$變為$3$，是以$3$先變為$2$再變為$3$

在第一個置換中，$4$變為$4$，第二個置換中$4$變為$1$，是以$4$先變為$4$再變為$1$

Burnside引理

設$G= \{a_1,a_2, \dots a_g\}$是目标集$[1,n]$上的置換群，$D(a_i)$表示在置換$a_i$作用下不動點的個數。$L$表示本質不同的方案數，則

$$L = \frac{1}{|G|} \sum_{j = 1}^s D(a_j)$$

P♂lya定理

在Burnside引理中，$D(a_i)$，也就是不動點的個數往往不是很好計算。如果采用枚舉每個元素的搜尋算法，總時間複雜度為$O(nsp)$，其中$n$表示元素個數，$s$表示置換個數，$p$表示格子數

Polya定理對于特定的題目，提供了一種高效的計算方法

首先介紹一下循環的概念

$$\left( a_{1}a_{2}\ldots a_{n}\right) =\begin{pmatrix} a_{1} & a_{2} & \ldots & a_{n-1}a_{n} \\ a_{2} & a_{3} & \ldots & a_{n}a_{1} \end{pmatrix}$$

稱為$n$階循環。每個置換都可以寫成若幹不相交的循環的乘積，兩個循環$(a_1, a_2, \dots a_n)$和$(b_1b_2 \dots b_n)$互不相交是指$a_i \not =b_j,i, j = 1,2, \dots n$

例如

$$\begin{pmatrix} 1 & 2 & 3 & 4 & 5 \\ 3 & 5 & 1 & 4 & 2 \end{pmatrix}=\left( 13\right) \left( 25\right) \left( 4\right)$$

解釋一下，$1$先變成$3$，$3$再變成$1$，這樣無限遞歸下去$(1,3)$便構成了一個循環

同理，$(2,5)$也會構成一個循環。

$4$隻能變成自己，是以自己構成為一個循環

Polya定理：

設$G$是$p$個對象的一個置換群，用$m$種顔色塗染$p$個對象，則不同染色方案為$$L = \frac{1}{|G|} (m^{c(g_1)} + m^{c(g_2)} + \dots + m^{c(g_s)})$$

其中$G = \{g_1, g_2, \dots g_s \}$，$c(g_i)$為置換$g_i$的循環節數$(i = 1, 2, \dots s)$

Polya定理沒有枚舉元素，是以它的複雜度為$O(sp)$

但是它也有一定的限制條件，比如說某種顔色的不能選

這時候我們就需要利用一個高端操作(例如dp)，來推廣Polya定理

作者：自為風月馬前卒

個人部落格http://attack204.com//

出處：http://zwfymqz.cnblogs.com/

本文版權歸作者和部落格園共有，歡迎轉載，但未經作者同意必須保留此段聲明，且在文章頁面明顯位置給出原文連接配接，否則保留追究法律責任的權利。