Pólya定理学习笔记

定义

置换群

置换群的元素是置换,运算是置换的连接。
置换群是置换的一个集合。
置换一般形式是

(a1b1a2b2a3b3a4b4)\left(\begin{array}{c}a_1\\ b_1\end{array} \begin{array}{c}a_2\\ b_2\end{array} \begin{array}{c}a_3\\ b_3\end{array} \begin{array}{c}a_4\\ b_4\end{array} \right)

其中aabb分别是1n1\to n的一个排列。

每一列表示位置为aia_i的元素移动到bib_i
例如:

(13213244)(14233241)=(13213244)(14233241)=(12243341)\left(\begin{array}{c}1\\ 3\end{array} \begin{array}{c}2\\ 1\end{array} \begin{array}{c}3\\ 2\end{array} \begin{array}{c}4\\ 4\end{array} \right) \left(\begin{array}{c}1\\ 4\end{array} \begin{array}{c}2\\ 3\end{array} \begin{array}{c}3\\ 2\end{array} \begin{array}{c}4\\ 1\end{array} \right)= \left(\begin{array}{c}1\\ 3\end{array} \begin{array}{c}2\\ 1\end{array} \begin{array}{c}3\\ 2\end{array} \begin{array}{c}4\\ 4\end{array} \right) \left(\begin{array}{c}1\\ 4\end{array} \begin{array}{c}2\\ 3\end{array} \begin{array}{c}3\\ 2\end{array} \begin{array}{c}4\\ 1\end{array} \right) =\left(\begin{array}{c}1\\ 2\end{array} \begin{array}{c}2\\ 4\end{array} \begin{array}{c}3\\ 3\end{array} \begin{array}{c}4\\ 1\end{array} \right)

Burnside引理

例题

将一个正方形分成44格,每个格子可以染成黑色或者白色,有多少种方案?经过旋转得到相同的图像算一种。

内容

BurnsidBurnsid引理是群论中的一个结论,在组合数学中可用于计算等价类的个数,常用于PolyaPolya计数。
BurnsidBurnsid引理:用D(aj)D(a_j)表示在置换aja_j下不变的元素的个数。LL表示本质不同的方案数。

L=1Gj=1nD(aj)L=\frac{1}{|G|}\sum_{j=1}^nD(a_j)

其中置换群G={G=\{9090^\circ,转180180^\circ,转270270^\circ }\}
把正方形的格子编号为

1423\begin{array}{c}1\\ 4\end{array}\begin{array}{c}2\\ 3\end{array}

00度: