Polya 定理

Redfield-Polya （Pólya enumeration theorem，簡稱PET）定理是組合數(shù)學(xué)理論中最重要的定理之一。

其提出者波里亞在眾多數(shù)學(xué)的分支：函數(shù)論、變分學(xué)、概率論、數(shù)論、組合數(shù)學(xué)以及計(jì)算數(shù)學(xué)和應(yīng)用數(shù)學(xué)領(lǐng)域中，都頗有建樹，他共發(fā)表了200多篇著名論文，以他的名字命名的Polya計(jì)數(shù)定理，則是近代組合數(shù)學(xué)的重要工具。波里亞還是杰出的數(shù)學(xué)教育家，有著豐富的數(shù)學(xué)教育思想和精湛的數(shù)學(xué)教學(xué)藝術(shù)，他對(duì)數(shù)學(xué)思維一般規(guī)律的研究，堪稱是對(duì)人類思想寶庫的特殊貢獻(xiàn)。

Polya 定理可以用于解決關(guān)于集合互異狀態(tài)的計(jì)數(shù)問題，是解決此類問題的簡潔高效的一個(gè)工具

例題引入

描述

把一個(gè) \(2\times 2\) 的方格棋盤用黑白兩色涂色，規(guī)定經(jīng)過旋轉(zhuǎn)重合的圖案是一種圖案，問能涂出多少種不同的圖案？

分析

不考慮旋轉(zhuǎn)，所有涂色方案如下圖：

可以發(fā)現(xiàn)圖中共有 16 種涂色方案，但是把經(jīng)過旋轉(zhuǎn)的 \(\begin{Bmatrix} 1&2&3&4 \end{Bmatrix}\)，\(\begin{Bmatrix} 5&6&7&8 \end{Bmatrix}\)，\(\begin{Bmatrix} 9&10&11&12 \end{Bmatrix}\)，\(\begin{Bmatrix} 13&14 \end{Bmatrix}\) 都算作一種方案，我們發(fā)現(xiàn)方案數(shù)其實(shí)只有 6 種

問題規(guī)模較小時(shí)，我們固然可以通過枚舉所有可能的情況計(jì)算得出滿足題目條件的情況數(shù)目，但如果我們面對(duì)了一個(gè) \(20\times 20\)，甚至 \(200\times 200\)，窮舉算法在那時(shí)將會(huì)達(dá)到 \(O(2^{200})\) 的時(shí)間復(fù)雜度，就連計(jì)算機(jī)也不能保證在有生之年給我們問題的答案

于是，數(shù)學(xué)家就開始研究這類問題的共性，試圖得出這類問題的通式，然后就有了 Polya 定理

預(yù)備知識(shí)

群

若一個(gè)一個(gè)集合 \(G\) 和二元運(yùn)算 \(a \bullet b\) ，滿足下列條件：

封閉性：對(duì)于 \(\forall a,\;b\in G\)，有 \((a \bullet b)\in G\)

結(jié)合律：對(duì)于 \(\forall a,\;b,\;c\in G\)，有 \((a\bullet b)\bullet c=a\bullet (b\bullet c)\)

單位元：對(duì)于 \(\forall a\in G\)， 存在 \(e\in G\)，使得 \(a\bullet e=a\)

逆元：對(duì)于 \(\forall a\in G\)，存在 \(f\in G\)，使得 \(a\bullet f=f\bullet a=e\)，且記 \(f=a^{-1}\)

則稱集合 \(G\) 是運(yùn)算法則 \(\bullet\) 下的一個(gè)群， \(\bullet\) 通常表示乘法運(yùn)算，此時(shí)則稱 \(G\) 是一個(gè)乘法群

一個(gè)簡單的例子：對(duì)于 \(\forall a\in Z\)，即所有整數(shù)組成的集合，在加法原則下滿足上面四個(gè)條件，其中 1，2 很好解釋，單位元?jiǎng)t是 0，逆元?jiǎng)t是 \(a\) 的對(duì)應(yīng)相反數(shù)，這個(gè)群便叫做 整數(shù)加法群

群按照集合中元素個(gè)數(shù)分為 無限群 和 有限群，Polya定理 主要針對(duì)有限群進(jìn)行分析操作

置換和置換群

簡單來說，置換就是把集合 \(A\) 中的所有元素 \(a_i\) 重新排列，形成集合 \(B\)，然后做映射 \(a_i \to b_i,\;i\in[1,\;n]\) ，例如：

\(\begin{pmatrix} 1&2&3&4\\\\2&3&4&1 \end{pmatrix}\)，下面的 \(\begin{pmatrix} 2&3&4&1 \end{pmatrix}\)，就是對(duì)上面的 \(\begin{pmatrix} 1&2&3&4 \end{pmatrix}\) 的重新排列，并映射 \(1\to2\)，\(2\to3\)，\(3\to4\)，\(4\to1\)，置換群就是 若干個(gè)置換組成的集合和置換之間的二元運(yùn)算法則構(gòu)成的群，這種置換之間的二元運(yùn)算法則可以理解成是 連續(xù)映射（或者是向量求和），例如置換之間的運(yùn)算：（運(yùn)算符定義為 \(\bullet\) ）

\(\begin{pmatrix} 1&2&3&4\\\\3&1&2&4 \end{pmatrix} \bullet \begin{pmatrix} 1&2&3&4\\\\4&3&2&1 \end{pmatrix}=\begin{pmatrix} 1&2&3&4\\\\3&1&2&4 \end{pmatrix} \bullet \begin{pmatrix} 3&1&2&4\\\\2&4&3&1 \end{pmatrix} = \begin{pmatrix} 1&2&3&4\\\\2&4&3&1\end{pmatrix}\)

可以發(fā)現(xiàn)運(yùn)算結(jié)果是連續(xù)映射的結(jié)果，如 \(1\to3\to2\)，\(2\to1\to4\)，\(3\to2\to3\)，\(4\to4\to1\)

可以證明，這樣的運(yùn)算法則和置換之間構(gòu)成的集合滿足構(gòu)成群的 4 個(gè)條件

現(xiàn)在，設(shè)順時(shí)針轉(zhuǎn)動(dòng) 0度，90度，180度，270度 為原來的 16 種方案的四個(gè)置換，可以得到：

\(\begin{pmatrix} a_1=&1&2&3&4&5&6&7&8&9&10&11&12&13&14&15&16\\\\ a_2=&2&3&4&1&6&7&8&5&12&11&9&10&14&13&15&16\\\\ a_3=&3&4&1&2&7&8&5&6&10&9&12&11&13&14&15&16\\\\ a_4=&4&1&2&3&8&5&6&7&11&12&10&9&14&13&15&16 \end{pmatrix}\)

下面，我們對(duì)上述 4 種置換深入研究

不動(dòng)置換類：\(Z_K\)

設(shè) \(G\) 是 \(1……n\) 的一個(gè)置換群，且 \(K\) 是 \(G\) 的集合中的一個(gè)元素，\(G\) 中使得 \(K\) 映射之后不變的置換組成的集合稱之為 K不動(dòng)置換類：\(Z_K\)，通常用 \(\lvert Z_K \rvert\) 表示這個(gè)集合當(dāng)中的元素個(gè)數(shù)，如上述例子中：

K=1 時(shí)，使得 1 在映射之后保持不變的置換只有 \(a_1\)，故 \(Z_1=\begin{Bmatrix} a_1 \end{Bmatrix}\)，\(\lvert Z_1 \rvert=1\)

K=13 時(shí)，使得 13 映射之后不變的置換只有 \(a_1\)，\(a_3\)，故 \(Z_{13}=\begin{Bmatrix} a_1&a_3 \end{Bmatrix}\)，\(\lvert Z_{13} \rvert=2\)

K=15 時(shí)，使得 15 映射之保持不變的置換有 \(a_1\)，\(a_2\)，\(a_3\)，\(a_4\)，故 \(Z_{15}=\begin{Bmatrix} a_1&a_2&a_3&a_4 \end{Bmatrix}\)，\(\lvert Z_{15} \rvert=4\)

等價(jià)置換類：\(E_K\)

設(shè) \(G\) 是 \(1……n\) 的一個(gè)置換群，且 \(K\) 是 \(G\) 的集合中的一個(gè)元素，\(K\) 在 \(G\) 中的置換作用下能變化到的元素組成的集合叫做 \(K\) 的等價(jià)置換類：\(E_K\)，通常用 \(\lvert E_K \rvert\) 表示這個(gè)集合當(dāng)中的元素個(gè)數(shù)，如上述例子中：

K=1 時(shí)，1 能變化到的元素集合為 \(\begin{Bmatrix} 1&2&3&4 \end{Bmatrix}\)，故 \(\lvert E_1 \rvert=4\)

K=13 時(shí)，13 能變化到的元素集合為 \(\begin{Bmatrix} 13&14 \end{Bmatrix}\)，故 \(\lvert E_{13} \rvert=2\)

K=15 時(shí)，15 能變化到的元素集合為 \(\begin{Bmatrix} 15 \end{Bmatrix}\)，故 \(\lvert E_{15} \rvert=1\)

可以發(fā)現(xiàn)對(duì)于群 \(G\) 中的任一元素 \(K\)，總有 \(\lvert E_K \rvert \times \lvert Z_K \rvert = \lvert G \rvert\)，證明過程較為復(fù)雜，在此不詳細(xì)展開

Burnside 引理

若設(shè)函數(shù) \(f(x,\;y)\) 表示元素 \(x\) 在置換 \(a_y\) 的映射下是否發(fā)生改變，并定義函數(shù) \(a_i(x)=y\) 表示 \(x\) 在 \(a_i\) 置換下的映射

則 \(f(x,y)=\begin{cases} 1,\quad a_y(x)=x \\\\ 0, \quad a_y(x)\neq x \end{cases}\)，下面我們看看對(duì)于上述 4 個(gè)有關(guān)旋轉(zhuǎn)的置換中 \(f(x,y)\) 的情況

元素 / 置換\(a_1\)\(a_2\)\(a_3\)\(a_4\)

1	1	0	0	0
2	1	0	0	0
3	1	0	0	0
……	……	……	……	……
16	1	1	1	1
Sum()	16	2	4	2

可以發(fā)現(xiàn) \(\sum_{i=1}^{16}\lvert Z_i \rvert=\sum_{j=1}^4Sum(j)\)，其中 \(Sum(j)\) 為上表中的 \(a_j\) 對(duì)應(yīng)列之和，也就是在置換 \(a_j\) 下保持不變的元素個(gè)數(shù)，我們可以稱經(jīng)過旋轉(zhuǎn)重合的多種涂色方案（至少 2 種）組成的集合為一個(gè)等價(jià)類 \(E\)，則原來的 16 種涂色方案中實(shí)際上包含了 4 個(gè)等價(jià)類，為 \(\begin{Bmatrix} 1&2&3&4 \end{Bmatrix}\)，\(\begin{Bmatrix} 5&6&7&8 \end{Bmatrix}\)，\(\begin{Bmatrix} 9&10&11&12 \end{Bmatrix}\)，\(\begin{Bmatrix} 13&14 \end{Bmatrix}\)

可以發(fā)現(xiàn)當(dāng) \(i\) 和 \(j\) 同屬一個(gè)等價(jià)類時(shí)，\(\lvert Z_i \rvert = \lvert Z_j \rvert\)，設(shè)原方案集合中存在 \(m\) 個(gè)等價(jià)類

則 \(\sum_{i=1}^n \lvert Z_i \rvert =\sum_{i=1}^m\sum_{K\in E_i}\lvert Z_K \rvert=\sum_{i=1}^m \lvert E_i \rvert \times \lvert Z_i \rvert=m \times \lvert G \rvert\)，這個(gè)式子只是簡單變形，本質(zhì)和上述式子相同

Burnside 引理：集合中存在的所有互異組合狀態(tài)的個(gè)數(shù)就是等價(jià)類的個(gè)數(shù)，即 \(m=\frac{\sum_{i=1}^n\lvert Z_i \rvert}{\lvert G \rvert}\)，由于上述的等價(jià)關(guān)系也可以寫成 \(m=\frac{\sum_{j=1}^4Sum(j)}{\lvert G \rvert}\)，這里的 \(\lvert G \rvert\) 是指置換的個(gè)數(shù)，為 4

結(jié)合這個(gè)例子，我們發(fā)現(xiàn) \(m=\frac{16+2+4+2}{4}=6\)，與枚舉得到的答案吻合

有了 Burnside 引理，已經(jīng)可以大大降低計(jì)數(shù)的時(shí)間復(fù)雜度了，可是我們發(fā)現(xiàn) \(Sum(j)\) 并不是那么的好算，現(xiàn)在直接采用搜索的方法的話將會(huì)達(dá)到 \(O(n\times \lvert G \rvert \times N)\)，分別表示元素個(gè)數(shù)（涂色的方案數(shù)），置換個(gè)數(shù)（此例中為4）和實(shí)際的方格數(shù)，顯然還是會(huì)超時(shí)，Polya 算法就旨在尋找一種簡便的計(jì)算 \(Sum(j)\) 的方法，進(jìn)一步優(yōu)化

Polya 定理

高級(jí)循環(huán)

記一種對(duì)于 \(\begin{pmatrix} a_1&a_2&a_3&……&a_n \end{pmatrix}\) 的高級(jí)循環(huán)為它的一個(gè)置換，并滿足：

$\begin{pmatrix} a_1&a_2&a_3&……&a_n \end{pmatrix} \Rightarrow \begin{pmatrix} a_1&a_2&a_3&……&a_n \\ a_2&a_3&a_4&……&a_1 \end{pmatrix} $，這樣的涉及 \(n\) 個(gè)元素的高級(jí)循環(huán)稱之為 n階循環(huán)

每個(gè)置換都可以由若干個(gè)互不相交的循環(huán)組成（互不相交是指兩個(gè)循環(huán)沒有公共元素）如：

$ \begin{pmatrix} 1&2&3&4&5 \\ 3&5&1&4&2 \end{pmatrix}= \begin{pmatrix} 1&3 \end{pmatrix} \bullet \begin{pmatrix} 2&5 \end{pmatrix} \bullet \begin{pmatrix} 4 \end{pmatrix} = \begin{pmatrix} 1&3 \\ 3&1 \end{pmatrix} \bullet \begin{pmatrix} 2&5 \\ 5&2 \end{pmatrix} \bullet \begin{pmatrix} 4 \\ 4 \end{pmatrix}$，（定義 \(\bullet\) 表示連接或合并）

對(duì)于每個(gè)置換都有且僅有這樣一種被表示為循環(huán)的方式，且定義循環(huán)節(jié)的個(gè)數(shù) \(C\) 為組成的循環(huán)個(gè)數(shù)，如上例中循環(huán)節(jié)數(shù) \(C=3\)

按照上述規(guī)則，給 \(2\times 2\) 的方格編號(hào)，旋轉(zhuǎn)之后如圖：

定義 4 個(gè)置換為：轉(zhuǎn) 0度，90度，180度，270度，用 \(g\) 表示置換，\(C(g)\) 表示置換對(duì)應(yīng)的循環(huán)節(jié)個(gè)數(shù)，則：

轉(zhuǎn) 0 度時(shí)，\(g_1=\begin{pmatrix} 1&2&3&4 \\\\ 1&2&3&4 \end{pmatrix}=(1)\bullet(2)\bullet(3)\bullet(4)\)，故 \(C(g_1)=4\)

轉(zhuǎn) 90 度時(shí)，\(g_2=\begin{pmatrix} 1&2&3&4 \\\\ 3&2&4&1 \end{pmatrix}=(4\quad 3\quad2\quad 1)\)，故 \(C(g_2)=1\)

轉(zhuǎn) 180 度時(shí)，\(g_3=\begin{pmatrix} 1&2&3&4 \\\\ 3&4&1&2 \end{pmatrix}=(1\quad 3)\bullet(2\quad 4)\)，故 \(C(g_3)=2\)

轉(zhuǎn) 270 度時(shí)，\(g_4=\begin{pmatrix} 1&2&3&4 \\\\ 2&1&4&3 \end{pmatrix}=(1\quad 2\quad 3\quad 4)\)，故 \(C(g_4)=1\)

進(jìn)一步研究發(fā)現(xiàn)，\(Sum(i)=2^{C(g_i)}\)，也就是說，該置換下不變的涂色方案數(shù)和以它對(duì)應(yīng)的循環(huán)節(jié)個(gè)數(shù)為指數(shù)，涂色選擇數(shù)為底數(shù)的冪相同，若有 \(T\) 種顏色可以涂，則此處應(yīng)為 \(Sum(i)=T^{C(g_i)}\)

Polya 定理：設(shè) \(G\) 是 \(p\) 個(gè)對(duì)象的一個(gè)置換群，用 \(T\) 種顏色染色 \(p\) 個(gè)對(duì)象，則本質(zhì)不同的方案數(shù)為：

\(m=\frac{1}{\lvert G \rvert}\times \sum_{i=1}^sT^{C(g_i)}\)，其中 \(s\) 為置換的個(gè)數(shù)

利用 Polya 定理 的時(shí)間復(fù)雜度為 \(O(s\times N)\)，分別為置換的個(gè)數(shù)和格子總數(shù)，在前面的引理上實(shí)現(xiàn)了優(yōu)化

附言

對(duì)于一開頭提出的例子，利用 Polya 定理 求出表達(dá)式之后，其實(shí)還可以繼續(xù)找規(guī)律，最后答案的方案數(shù)應(yīng)為：
\(m=\frac{1}{4}\times (T^{n^2}+T^{\frac{n^2+3}{4}}+T^{\frac{n^2+1}{2}}+T^{\frac{n^2+3}{4}})\)

這與我們前面通過枚舉和歸納表達(dá)式計(jì)算出來的結(jié)果完全一致

參考文獻(xiàn)：Polya定理——符文杰

轉(zhuǎn)載于:https://www.cnblogs.com/Ewiges-Leben/p/11373682.html

總結(jié)

以上是生活随笔為你收集整理的Poly定理：学习笔记的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。