跳转至

置換羣

引入

置換羣通常用來解決一些涉及「本質不同」的計數問題，例如用 3 種顏色給一個立方體染色，求本質不同的方案數（經過翻轉後相同的兩種方案視為同一種）。

有關羣的定義、子羣的定義，見 羣論基礎。

置換

置換的相關定義可見 置換和排列。

置換羣

集合 \(S\) 上的所有置換關於置換的乘法滿足封閉性、結合律、有單位元（恆等置換，即每個元素映射成它自己）、有逆元（交換置換表示中的上下兩行），因此構成一個羣。這個羣的任意一個 子羣 即稱為 置換羣。

循環置換

循環置換是一類特殊的置換，可表示為

\[ (a_1,a_2,\dots,a_m)=\begin{pmatrix}a_1,a_2,\dots,a_{m-1},a_m\\ a_2,a_3,\dots,a_m,a_1\end{pmatrix} \]

若兩個循環置換不含有相同的元素，則稱它們是 不相交 的。有如下定理：

任意一個置換都可以分解為若干不相交的循環置換的乘積，例如

\[ \begin{pmatrix}a_1,a_2,a_3,a_4,a_5\\ a_3,a_1,a_2,a_5,a_4\end{pmatrix}=(a_1,a_3,a_2)\circ(a_4,a_5) \]

該定理的證明也非常簡單。如果把元素視為圖的節點，映射關係視為有向邊，則每個節點的入度和出度都為 1，因此形成的圖形必定是若干個環的集合，而一個環即可用一個循環置換表示。

Burnside 引理

前面的都算是鋪墊，接下來我們進入正題。

定義

設 \(A\) 和 \(B\) 為有限集合，\(X\) 為一些從 \(A\) 到 \(B\) 的映射組成的集合。
\(G\) 是 \(A\) 上的置換羣，且 \(X\) 中的映射在 \(G\) 中的置換作用下封閉。
\(X/G\) 表示 \(G\) 作用在 \(X\) 上產生的所有等價類的集合
（若 \(X\) 中的兩個映射經過 \(G\) 中的置換作用後相等，則它們在同一等價類中），則

\[ |X/G|=\frac{1}{|G|}\sum_{g\in G}|X^g| \]

其中 \(|S|\) 表示集合 \(S\) 中元素的個數，且

\[ X^g=\{x|x\in X,g(x)=x\} \]

是不是覺得很難懂？別急，請看下面的例子。

解釋

我們還是以給立方體染色為例子，則上面式子中一些符號的解釋如下：

  • \(A\)：立方體 6 個面的集合
  • \(B\)：3 種顏色的集合
  • \(X\)：直接給每個面染色，不考慮本質不同的方案的集合，共有 \(3^6\) 種
  • \(G\)：各種翻轉操作構成的置換羣
  • \(X/G\)：本質不同的染色方案的集合
  • \(X^g\)：對於某一種翻轉操作 \(g\)，所有直接染色方案中，經過 \(g\) 這種翻轉後保持不變的染色方案的集合

接下來我們需要對 \(G\) 中的所有置換進行分析，它們可以分為以下幾類（方便起見，將立方體的 6 個面分別稱為前、後、上、下、左、右）：

  • 不動：即恆等變換，因為所有直接染色方案經過恆等變換都不變，因此它對應的 \(|X^g|=3^6\)
  • 以兩個相對面的中心連線為軸的 \(90^\circ\) 旋轉：相對面有 3 種選擇，旋轉的方向有兩種選擇，因此這類共有 6 個置換。假設選擇了前、後兩個面中心的連線為軸，則必須要滿足上、下、左、右 4 個面的顏色一樣，才能使旋轉後不變，因此它對應的 \(|X^g|=3^3\)
  • 以兩個相對面的中心連線為軸的 \(180^\circ\) 旋轉：相對面有 3 種選擇，旋轉方向的選擇對置換不再有影響，因此這類共有 3 個置換。假設選擇了前、後兩個面中心的連線為軸，則必須要滿足上、下兩個面的顏色一樣，左、右兩個面的顏色一樣，才能使旋轉後不變，因此它對應的 \(|X^g|=3^4\)
  • 以兩條相對稜的中點連線為軸的 \(180^\circ\) 旋轉：相對稜有 6 種選擇，旋轉方向對置換依然沒有影響，因此這類共有 6 個置換。假設選擇了前、上兩個面的邊界和下、後兩個面的邊界作為相對稜，則必須要滿足前、上兩個面的顏色一樣，下、後兩個面的顏色一樣，左、右兩個面的顏色一樣，才能使旋轉後不變，因此它對應的 \(|X^g|=3^3\)
  • 以兩個相對頂點的連線為軸的 \(120^\circ\) 旋轉：相對頂點有 4 種選擇，旋轉的方向有兩種選擇，因此這類共有 8 個置換。假設選擇了前面的右上角和後面的左下角作為相對頂點，則必須滿足前、上、右三個面的顏色一樣，後、下、左三個面的顏色一樣，才能使旋轉後不變，因此它對應的 \(|X^g|=3^2\)

因此，所有本質不同的方案數為

\[ \frac{1}{1+6+3+6+8}(3^6+6\times3^3+3\times3^4+6\times3^3+8\times3^2)=57 \]

證明

看懂本部分需要羣論的相關知識，如果你沒有學習過羣論或者對證明過程沒有興趣，建議直接跳過本部分。

為了證明 Burnside 引理，需要先引入軌道穩定子定理（Orbit-Stabilizer Theorem，也稱軌道 - 穩定集定理）。

軌道穩定子定理 \(G\) 和 \(X\) 的定義同上，\(\forall x\in X,G^x=\{g|g(x)=x,g\in G\},G(x)=\{g(x)|g\in G\}\)，其中 \(G^x\) 稱為 \(x\) 的 穩定子，\(G(x)\) 稱為 \(x\) 的 軌道，則有

\[ |G|=|G^x||G(x)| \]

軌道穩定子定理的證明 首先可以證明 \(G^x\) 是 \(G\) 的子羣，因為

  • 封閉性：若 \(f,g\in G\)，則 \(f\circ g(x)=f(g(x))=f(x)=x\)，所以 \(f\circ g\in G^x\)
  • 結合律：顯然置換的乘法滿足結合律
  • 單位元：因為 \(I(x)=x\)，所以 \(I\in G^x\)（\(I\) 為恆等置換）
  • 逆元：若 \(g\in G^x\)，則 \(g^{-1}(x)=g^{-1}(g(x))=g^{-1}\circ g(x)=I(x)=x\)，所以 \(g^{-1}\in G^x\)

則由羣論中的拉格朗日定理，可得

\[ |G|=|G^x|[G:G^x] \]

其中 \([G:G^x]\) 為 \(G^x\) 不同的左陪集個數。接下來只需證明 \(|G(x)|=[G:G^x]\)，我們將其轉化為證明存在一個從 \(G(x)\) 到 \(G^x\) 所有不同左陪集的雙射。令 \(\varphi(g(x))=gG^x\)，下證 \(\varphi\) 為雙射

  • 若 \(g(x)=f(x)\)，兩邊同時左乘 \(f^{-1}\)，可得 \(f^{-1}\circ g(x)=I(x)=x\)，所以 \(f^{-1}\circ g\in G^x\)，由陪集的性質可得 \((f^{-1}\circ g)G^x=G^x\)，即 \(gG^x=fG^x\)
  • 反過來可證，若 \(gG^x=fG^x\)，則有 \(g(x)=f(x)\)
  • 以上兩點説明對於一個 \(g(x)\)，只有一個左陪集與其對應，即 \(\varphi\) 是一個從 \(G(x)\) 到左陪集的映射

  • 又顯然 \(\varphi\) 有逆映射，因此 \(\varphi\) 是一個雙射

    Burnside 引理的證明

\[ \begin{align} \sum_{g\in G}|X^g|&=|\{(g,x)|(g,x)\in G\times X,g(x)=x\}|\\ &=\sum_{x\in X}|G^x|\\ &=\sum_{x\in X}\frac{|G|}{|G(x)|}\quad\quad\quad（軌道穩定子定理）\\ &=|G|\sum_{x\in X}\frac{1}{|G(x)|}\\ &=|G|\sum_{Y\in X/G}\sum_{x\in Y}\frac{1}{|G(x)|}\\ &=|G|\sum_{Y\in X/G}\sum_{x\in Y}\frac{1}{|Y|}\\ &=|G|\sum_{Y\in X/G}1\\ &=|G||X/G| \end{align} \]

所以有

\[ |X/G|=\frac{1}{|G|}\sum_{g\in G}|X^g| \]

Pólya 定理

定義

在與 Burnside 引理相同的前置條件下， 若 \(X\) 為 所有 從 \(A\) 到 \(B\) 的映射，內容修改為

\[ |X/G|=\frac{1}{|G|}\sum_{g\in G}|B|^{c(g)} \]

其中 \(c(g)\) 表示置換 \(g\) 能拆分成的不相交的循環置換的數量。

解釋

依然考慮立方體染色問題。分析剛才提到的以相對稜的中點連線為軸的 \(180^\circ\) 旋轉，如果將前、後、上、下、左、右 6 個面依次編號為 1 到 6，則該置換可以表示為（翻轉後原來編號為 1 的面的位置變為了編號為 3 的面，以此類推）

\[ \begin{pmatrix}1,3,2,4,5,6\\ 3,1,4,2,6,5\end{pmatrix}=(1,3)\circ(2,4)\circ(5,6) \]

因此 \(c(g)=3,|B|^{c(g)}=3^3\)，與剛才在 Burnside 引理中分析的結果相同。

證明

在 Burnside 引理中，顯然 \(g(x)=x\) 的充要條件是 \(x\) 將 \(g\) 中每個循環置換的元素都映射到了 \(B\) 中的同一元素，所以 \(|X^g|=|B|^{c(g)}\)，即可得 Pólya 定理。

本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：Wajov
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用