伯恩赛德-波利亚计数法 作者：乔纳森：乔纳森-L-格罗斯，哥伦比亚大学计算机科学系。
先决条件本章的先决条件是集合上的组合、等价关系和双射。参见《离散数学及其应用》第 2.3、5.3 和 8.5 节。
导言 如果一个井字游戏玩到所有空格都被填满，那么得到的网格将有 5 个十字和 4 个九（也称为 "哦"）。通过计算组合数，可以得出有 5 个叉和 4 个划的
3
×
3
3
×
3
3xx3 3 \times 3
C
(
9
,
5
)
C
(
9
,
5
)
C(9,5) C(9,5) 在玩井字游戏时，如果可以通过旋转或反射棋盘从另一个配置中获得另一个配置，那么自然可以将这两个配置视为等价配置。例如，在图 1 中，配置（B）可以通过逆时针旋转配置（A）
90
∘
90
∘
90^(@) 90^{\circ}
x
x
x x
x
x
x x
x
x
x x
0
x
x
x x
x
x
x x
0
0
0
x x x
0 x x
0 0 0 | $x$ | $x$ | $x$ |
| :---: | :---: | :---: |
| 0 | $x$ | $x$ |
| 0 | 0 | 0 |
(A)
x
x
x x
x
x
x x 0
x
x
x x
x
x
x x 0
x
x
x x 0
0
x x 0
x x 0
x 0 0 | $x$ | $x$ | 0 |
| :---: | :---: | :---: |
| $x$ | $x$ | 0 |
| $x$ | 0 | 0 |
(B)
0
0
0
0
x
x
x x
x
x
x x
x
x
x x
x
x
x x
x
x
x x
0 0 0
0 x x
x x x | 0 | 0 | 0 |
| :---: | :---: | :---: |
| 0 | $x$ | $x$ |
| $x$ | $x$ | $x$ |
©
图 1.三种相等的井字形配置。 我们可以把这个直观的 "相同 "概念形式化，即如果两个井字棋盘配置中的一个可以通过旋转或反射从另一个得到，则称这两个配置为全等。在通常意义上，全等是一种等价关系，它将井字棋盘的所有配置集合划分成的等价类称为全等类。因此，我们要寻求以下问题的解决方案：
同类计数问题（CCCP）：数出有五个十字和四个九宫格的配置中不同同类的数量。
如果所有同余类的大小相同，那么我们就可以通过将统一的同余类大小除以
C
(
9
,
5
)
C
(
9
,
5
)
C(9,5) C(9,5)
C
C
C
P
C
C
C
P
CCCP C C C P 例 1 计算与图 2 中的配置 (D)、(E) 和 (F) 等价的配置数。
x
x
x x 0
x
x
x x
0
x
x
x x 0
x
x
x x 0
x
x
x x
x 0 x
0 x 0
x 0 x | $x$ | 0 | $x$ |
| :---: | :---: | :---: |
| 0 | $x$ | 0 |
| $x$ | 0 | $x$ |
(D)
(E)
(F)
图 2.具有不同大小等价类的配置。
解法：配置（D）的每次旋转和反射总是得到（D）本身，因此其全等类的卡方数等于 1。每一个与（E）全等的构型都是其两条对角线中的一条布满了十字，中间一行或中间一列布满了十字的图案。反之，每个这样的图案都与 ( E ) 全等。由于有四个这样的图案，因此 ( E ) 的全等类的心数等于四。
井字棋盘自转和反射的总次数为 8 次，即有 4 次自转和 4 次反射。四种不同的旋转分别对应井字棋盘的 0、1、2 或 3 个四分之一圈。我们可以通过棋盘的中间一行水平反射棋盘、 垂直穿过中间一列、穿过从左上方到右下方的 "主要 "对角线行，或穿过从右上方到左下方的 "次要 "对角线行。将这八种旋转和反射分别应用到构型（F）上，就会得到不同的构型。
正如我们刚才对构型 (F) 所用的方法所示，我们可以很容易地计算出任何给定构型的全等类的大小。也就是说，我们只需将所有八种旋转应用于给定的构型，就能得出有多少种不同的旋转。
我们计算全等类的方法，即伯恩赛德-波利亚枚举理论，也涉及这些旋转和反射。这是一种极其重要的计数技术，因为它还可以用来计数图同构类（见《离散数学及其应用》第 7.3 节）、图着色的等价类（见第 9.8 节）、有限状态自动机的等价类（见第 12.2 节）以及其他许多涉及结构对称性的等价类。
我们最终将通过计算得出
C
C
C
P
C
C
C
P
CCCP C C C P 排列组合 井字棋盘上的旋转或反射是从有限集合到自身的双射（即一一对应函数）的一种特例，通常称为置换。如果我们在井字棋盘的九个方格上标注 1 到 9 的整数，这种关系就会变得很明显，如图 3 所示。
1 2 3
4 5 6
7 8 9 | 1 | 2 | 3 |
| :--- | :--- | :--- |
| 4 | 5 | 6 |
| 7 | 8 | 9 |
图 3.用整数标记井字方格。 然后逆时针旋转四分之一圈，方格 1 变为方格 7，方格 2 变为方格 4，方格 3 变为方格 1，依此类推。井字棋盘上每个位置的变化都可以记录在一个
2
×
9
2
×
9
2xx9 2 \times 9
(
1
2
3
4
5
6
7
8
9
7
4
1
8
5
2
9
6
3
)
1
2
3
4
5
6
7
8
9
7
4
1
8
5
2
9
6
3
([1,2,3,4,5,6,7,8,9],[7,4,1,8,5,2,9,6,3]) \left(\begin{array}{lllllllll}
1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\
7 & 4 & 1 & 8 & 5 & 2 & 9 & 6 & 3
\end{array}\right) 在九列中的每一列中，顶行的条目都被映射到紧接其下的条目。一般来说，心数为
n
n
n n
2
×
n
2
×
n
2xx n 2 \times n 集合
{
1
,
2
…
,
9
}
{
1
,
2
…
,
9
}
{1,2dots,9} \{1,2 \ldots, 9\}
2
×
9
2
×
9
2xx9 2 \times 9
2
×
2
2
×
2
2xx2 2 \times 2
1 2
3 4 | 1 | 2 |
| :--- | :--- |
| 3 | 4 |
图 4.
2
x
2
2
x
2
2x2 \mathbf{2 x} \mathbf{2} 集合
{
1
,
2
,
3
,
4
}
{
1
,
2
,
3
,
4
}
{1,2,3,4} \{1,2,3,4\}
2
×
4
2
×
4
2xx4 2 \times 4 轮换：
90
∘
180
∘
90
∘
180
∘
90^(@)180^(@) 90^{\circ} 180^{\circ}
c
c
c
c
c
c
ccc c c c
(
1
2
3
4
3
1
4
2
)
1
2
3
4
3
1
4
2
([1,2,3,4],[3,1,4,2]) \left(\begin{array}{llll}1 & 2 & 3 & 4 \\ 3 & 1 & 4 & 2\end{array}\right)
90^(@)180^(@) ccc
([1,2,3,4],[3,1,4,2]) | $90^{\circ} 180^{\circ}$ | | $c c c$ |
| :---: | :---: | :---: | :---: |
| $\left(\begin{array}{llll}1 & 2 & 3 & 4 \\ 3 & 1 & 4 & 2\end{array}\right)$ | | | (left(\begin{array}{llll}1 & 2 & 3 & 4
4 & 3 & 2 & 1 （end{array}\right） （quad\left(\right) （quad\left(\right)) 反思：
horizontal
vertical
main diagonal
minor diagonal
(
1
2
3
4
3
4
1
2
)
1
2
3
4
2
1
4
3
)
1
2
3
4
1
3
2
4
)
(
1
2
3
4
4
2
3
1
)
horizontal
vertical
main diagonal
minor diagonal
1
2
3
4
3
4
1
2
1
2
3
4
2
1
4
3
1
2
3
4
1
3
2
4
1
2
3
4
4
2
3
1
{:[" horizontal "," vertical "," main diagonal "," minor diagonal "],[([1,2,3,4],[3,4,1,2])][1,2,3,4],[2,1,4,3])quad[1,2,3,4],[1,3,2,4])quad([1,2,3,4],[4,2,3,1]) \left.\left.\begin{array}{cccc}\text { horizontal } & \text { vertical } & \text { main diagonal } & \text { minor diagonal } \\ \left(\begin{array}{llll}1 & 2 & 3 & 4 \\ 3 & 4 & 1 & 2\end{array}\right)\end{array} \begin{array}{cccc}1 & 2 & 3 & 4 \\ 2 & 1 & 4 & 3\end{array}\right) \quad \begin{array}{llll}1 & 2 & 3 & 4 \\ 1 & 3 & 2 & 4\end{array}\right) \quad\left(\begin{array}{llll}1 & 2 & 3 & 4 \\ 4 & 2 & 3 & 1\end{array}\right) 如果被置换集合上的元素是整数（或任何其他有序集合），那么很自然的做法是排列矩阵的列，使第一行的元素按升序排列。不过，任何列的排序都能很好地表达置换对每个元素的作用。
在计算两个排列的组合
g
∘
f
g
∘
f
g@f g \circ f
g
g
g g
2
×
n
2
×
n
2xx n 2 \times n
f
f
f f
2
×
n
2
×
n
2xx n 2 \times n
f
f
f f
1
,
2
,
…
,
n
1
,
2
,
…
,
n
1,2,dots,n 1,2, \ldots, n
g
g
g g
f
(
1
)
,
f
(
2
)
,
…
,
f
(
n
)
f
(
1
)
,
f
(
2
)
,
…
,
f
(
n
)
f(1),f(2),dots,f(n) f(1), f(2), \ldots, f(n) 与
f
f
f f
g
g
g g
g
(
f
(
1
)
)
,
g
(
f
(
2
)
)
,
…
,
g
(
f
(
n
)
)
g
(
f
(
1
)
)
,
g
(
f
(
2
)
)
,
…
,
g
(
f
(
n
)
)
g(f(1)),g(f(2)),dots,g(f(n)) g(f(1)), g(f(2)), \ldots, g(f(n)) 由此可见，代表成分
g
∘
f
g
∘
f
g@f g \circ f
2
×
n
2
×
n
2xx n 2 \times n
g
g
g g
f
f
f f 例如，对于
2
×
2
2
×
2
2xx2 2 \times 2
f
f
f f
g
g
g g
(
1
2
3
4
3
1
4
2
)
(
3
1
4
2
1
3
2
4
)
=
(
1
2
3
4
3
4
1
2
)
horizontal reflection
1
2
3
4
3
1
4
2
3
1
4
2
1
3
2
4
=
1
2
3
4
3
4
1
2
horizontal reflection
{:[([1,2,3,4],[3,1,4,2])],[([3,1,4,2],[1,3,2,4]),=([1,2,3,4],[3,4,1,2])," horizontal reflection "]:} \begin{array}{lll}
\left(\begin{array}{llll}
1 & 2 & 3 & 4 \\
3 & 1 & 4 & 2
\end{array}\right) \\
\left(\begin{array}{llll}
3 & 1 & 4 & 2 \\
1 & 3 & 2 & 4
\end{array}\right) & =\left(\begin{array}{llll}
1 & 2 & 3 & 4 \\
3 & 4 & 1 & 2
\end{array}\right) & \text { horizontal reflection }
\end{array}
(
1
2
3
4
1
3
2
4
)
1
2
3
4
1
3
2
4
([1,2,3,4],[1,3,2,4])quad \left(\begin{array}{llll}1 & 2 & 3 & 4 \\ 1 & 3 & 2 & 4\end{array}\right) \quad 除了复习左侧计算组合体矩阵表示的力学过程外，还应将自己的空间感知运用到右侧组合体的相应描述中，从几何角度进行观察。
通过应用
2
×
n
2
×
n
2xx n 2 \times n
2
×
2
2
×
2
2xx2 2 \times 2 (1) 两个旋转的组合就是一个旋转。 (2) 两个反射的组合就是旋转。 (3) 旋转与反射或反射与旋转的组合就是反射。 结合这三个论断，我们可以立即推断出以下定理。 定理 1
2
×
2
2
×
2
2xx2 2 \times 2 如果一个有限集合上的排列集合中的任意两个排列组成时，所产生的排列也在该集合中，则该集合在组成下是封闭的。
例 2 证明
2
×
2
2
×
2
2xx2 2 \times 2 解：我们已经通过定理 1 确定了这一点。 例 3 证明
2
×
2
2
×
2
2xx2 2 \times 2 解决方案：这一点从几何图形中显而易见。
例 4 证明仅由
360
∘
360
∘
360^(@) 360^{\circ}
2
×
2
2
×
2
2xx2 2 \times 2 解决方案：它与自身的构成就是自身。
例 5 证明
2
×
2
2
×
2
2xx2 2 \times 2 解：由定理 1 的性质 (2) 得出。
由于置换
π
π
pi \pi
inv
(
π
)
inv
(
π
)
inv(pi) \operatorname{inv}(\pi)
π
−
1
π
−
1
pi^(-1) \pi^{-1}
2
×
n
2
×
n
2xx n 2 \times n 例如，根据几何推理可知，逆时针转动四分之一圈的倒数是逆时针转动四分之三圈。下面是我们的计算法则在这个例子中的应用。
inv
(
1
2
3
4
3
1
4
2
)
=
(
3
1
4
2
1
2
3
4
)
=
(
1
2
3
4
2
4
1
3
)
.
inv
1
2
3
4
3
1
4
2
=
3
1
4
2
1
2
3
4
=
1
2
3
4
2
4
1
3
.
{:[inv([1,2,3,4],[3,1,4,2])=([3,1,4,2],[1,2,3,4])],[=([1,2,3,4],[2,4,1,3]).]:} \begin{aligned}
\operatorname{inv}\left(\begin{array}{llll}
1 & 2 & 3 & 4 \\
3 & 1 & 4 & 2
\end{array}\right) & =\left(\begin{array}{llll}
3 & 1 & 4 & 2 \\
1 & 2 & 3 & 4
\end{array}\right) \\
& =\left(\begin{array}{llll}
1 & 2 & 3 & 4 \\
2 & 4 & 1 & 3
\end{array}\right) .
\end{aligned}
2
×
2
2
×
2
2xx2 2 \times 2 (4) 旋转的倒数就是旋转。 (5) 反射的倒数也是同样的反射。 结合这两个性质，我们可以立即推断出以下定理。
定理 2
2
×
2
2
×
2
2xx2 2 \times 2 如果一个有限集合上的排列集合中的每个排列的逆也在这个集合中，那么这个集合就被称为反转下的封闭集合。
有一个特殊的名称来表示在组合和反转下都是封闭的排列集合。它被称为置换群。
例 6 证明
2
×
2
2
×
2
2xx2 2 \times 2 解：从定理 1 和 2 可以得出结论。
例 7 证明
3
×
3
3
×
3
3xx3 3 \times 3 解决方案：在
3
×
3
3
×
3
3xx3 3 \times 3
2
×
2
2
×
2
2xx2 2 \times 2 例 8 证明有限集合上所有排列的集合构成一个排列群。
解：由于任意两个排列的组合是一个排列，并且任意排列的逆也是一个排列，因此立即得出结论。
例 9 证明只包含标识置换（它固定每个元素，就像集合上的其他标识函数一样）的单子集合是一个置换群。
解法：同一性与自身的组成就是同一性，同一性的逆就是同一性，所以集合在组成和反转下都是封闭的。
在本节的最后，我们将井字棋盘的全等类概念放到一个更广阔的背景中，以适应伯恩赛德-波利亚计数理论。
当一个置换群
G
G
G G
Y
Y
Y Y
3
×
3
3
×
3
3xx3 3 \times 3 如果
y
y
y y
Y
Y
Y Y
π
∈
G
π
∈
G
pi in G \pi \in G
π
(
y
)
π
(
y
)
pi(y) \pi(y)
y
y
y y
y
y
y y
y
′
y
′
y^(') y^{\prime}
y
R
y
′
y
R
y
′
yRy^(') y R y^{\prime}
R
R
R R
G
G
G G 定理 3 由置换群
P
P
P P
Y
Y
Y Y
R
R
R R 证明给定任何对象
y
y
y y
I
I
I I
y
R
I
(
y
)
y
R
I
(
y
)
yRI(y) y R I(y)
y
y
y y
R
R
R R 接下来，给定任意两个对象
y
y
y y
y
′
y
′
y^(') y^{\prime}
y
R
y
′
y
R
y
′
yRy^(') y R y^{\prime}
G
G
G G
π
π
pi \pi
π
(
y
)
=
y
′
π
(
y
)
=
y
′
pi(y)=y^(') \pi(y)=y^{\prime}
π
−
1
∈
G
π
−
1
∈
G
pi^(-1)in G \pi^{-1} \in G
π
−
1
(
y
′
)
=
y
π
−
1
y
′
=
y
pi^(-1)(y^('))=y \pi^{-1}\left(y^{\prime}\right)=y
y
′
R
y
y
′
R
y
y^(')Ry y^{\prime} R y
R
R
R R 最后，如果
y
R
y
′
y
R
y
′
yRy^(') y R y^{\prime}
y
′
R
y
′
′
y
′
R
y
′
′
y^(')Ry^('') y^{\prime} R y^{\prime \prime}
G
G
G G
π
π
pi \pi
μ
μ
mu \mu
π
(
y
)
=
y
′
π
(
y
)
=
y
′
pi(y)=y^(') \pi(y)=y^{\prime}
μ
(
y
′
)
=
y
′
′
μ
y
′
=
y
′
′
mu(y^('))=y^('') \mu\left(y^{\prime}\right)=y^{\prime \prime}
μ
∘
π
(
y
)
=
y
′
′
μ
∘
π
(
y
)
=
y
′
′
mu@pi(y)=y^('') \mu \circ \pi(y)=y^{\prime \prime}
G
G
G G
μ
∘
π
∈
G
μ
∘
π
∈
G
mu@pi in G \mu \circ \pi \in G
y
R
y
′
′
y
R
y
′
′
yRy^('') y R y^{\prime \prime}
R
R
R R 在确定了关系
R
R
R R 置换群对一组对象的作用所引起的等价类通常称为轨道。
例 10 旋转和反射群对井字棋盘的构型的作用所引起的轨道是什么？
解决方案：它们就是同余类。
例 11 当所有可能的排列组合作用于一组物体时，会形成多少个轨道？
解：只有一个轨道，它包含了集合的所有元素。
引入这些代数概念后，我们就能把伯恩赛德-波利亚枚举理论的目标最清晰地表述为一种计算作用于有限集合的置换群轨道的方法。实际上，弗罗贝尼乌斯发明了计算轨道的方法，但它出现在伯恩赛德的经典小册子[1]中，因此被称为 "伯恩赛德定理"。
Pólya* [3] 用一种为轨道分配 "权重 "的方法增强了这一理论
并将轨道总数分解为每个权重等级的轨道数之和。实际上，波利亚重新发现了雷德菲尔德（Redfield）[4] 早已知道的方法，而雷德菲尔德的论文却没有引起大多数人的注意。哈拉里（F. Harary）（见 [2]）将伯恩赛德-波利亚枚举理论用于图形枚举，吸引了许多数学家进一步应用它。我们将通过伯恩赛德-波利亚理论的详细应用，展示如何计算引言中提到的 23 个构型的全等类，从而求解
C
C
C
P
C
C
C
P
CCCP C C C P
2
×
2
2
×
2
2xx2 2 \times 2 由于四个方格中每个方格的填充都涉及二元选择，因此共有 16 个这样的配置。单凭伯恩赛德的方法，我们就能确定有六种轨道，而波利亚的扩充方法则提供了将这六种轨道分为以下子类的 "清单"：
1 个轨道上有 4 个十字和 0 个下划线 1 个轨道，3 个十字，1 个无 2 个有两个十字和两个九的轨道 1 个带 1 个十字和 3 个诺的轨道 1 个轨道，0 个十字和 4 个九宫格。 图 5 为这六个轨道各提供了一个配置示例。你可以很容易地证明，16 种构型中的每一种都可以旋转或反射成所示 6 个示例中的一种。 图 5.在旋转和反射组下，
2
×
2
2
×
2
2xx2 2 \times 2 排列组合的循环结构 现在我们回到
2
×
9
2
×
9
2xx9 2 \times 9
3
×
3
3
×
3
3xx3 3 \times 3
(
1
2
3
4
5
6
7
8
9
7
4
1
8
5
2
9
6
3
)
1
2
3
4
5
6
7
8
9
7
4
1
8
5
2
9
6
3
([1,2,3,4,5,6,7,8,9],[7,4,1,8,5,2,9,6,3]) \left(\begin{array}{lllllllll}
1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\
7 & 4 & 1 & 8 & 5 & 2 & 9 & 6 & 3
\end{array}\right) 当我们应用这种排列时，位置 1 的内容（交叉或无交叉）将移动到位置 7，正如我们从第 1 列看到的那样。第 7 列表示位置 7 的内容移动到位置 9。第 9 列表示位置 9 的内容移动到位置 3。我们还注意到，第 3 栏表示 位置 3 移动到位置 1。换句话说，
1
,
7
,
9
,
3
1
,
7
,
9
,
3
1,7,9,3 1,7,9,3 同样，我们注意到位置
2
,
4
,
8
2
,
4
,
8
2,4,8 2,4,8 通过这种分析，我们可以将排列组合表示为
(
1
7
9
3
)
(
248
l
l
)
(
5
)
1
7
9
3
(
248
l
l
)
(
5
)
([1,7,9,3])(248 ll)(5) \left(\begin{array}{lllllll}
1 & 7 & 9 & 3
\end{array}\right)(248 l l)(5) 我们可以很容易地从中重建
2
×
n
2
×
n
2xx n 2 \times n
t
1
t
4
2
t
1
t
4
2
t_(1)t_(4)^(2) t_{1} t_{4}^{2}
t
1
t
1
t_(1) t_{1}
t
4
t
4
t_(4) t_{4} 我们注意到，任何一个循环中的对象都与其他循环中的对象不相交。一般来说，任何排列都可以表示为不相交循环的组合，我们称这种表示为排列的不相交循环形式。表 1 列出了
2
×
2
2
×
2
2xx2 2 \times 2 从表中我们可以看出，有一个排列的循环结构为
t
1
4
t
1
4
t_(1)^(4) t_{1}^{4}
t
1
2
t
2
t
1
2
t
2
t_(1)^(2)t_(2) t_{1}^{2} t_{2}
t
2
2
t
2
2
t_(2)^(2) t_{2}^{2}
t
4
t
4
t_(4) t_{4}
G
G
G G
G
G
G G
Z
(
G
)
Z
(
G
)
Z(G) Z(G) 例 12 在
2
×
2
2
×
2
2xx2 2 \times 2 解决方案：
1
8
(
t
1
4
+
2
t
1
2
t
2
+
3
t
2
2
+
2
t
4
)
1
8
t
1
4
+
2
t
1
2
t
2
+
3
t
2
2
+
2
t
4
quad(1)/(8)(t_(1)^(4)+2t_(1)^(2)t_(2)+3t_(2)^(2)+2t_(4)) \quad \frac{1}{8}\left(t_{1}^{4}+2 t_{1}^{2} t_{2}+3 t_{2}^{2}+2 t_{4}\right) 例 13 计算
3
×
3
3
×
3
3xx3 3 \times 3 解决方案：周期指数为
1
8
(
t
1
9
+
4
t
1
3
t
2
3
+
t
1
t
2
4
+
2
t
1
t
4
2
)
1
8
t
1
9
+
4
t
1
3
t
2
3
+
t
1
t
2
4
+
2
t
1
t
4
2
(1)/(8)(t_(1)^(9)+4t_(1)^(3)t_(2)^(3)+t_(1)t_(2)^(4)+2t_(1)t_(4)^(2)) \frac{1}{8}\left(t_{1}^{9}+4 t_{1}^{3} t_{2}^{3}+t_{1} t_{2}^{4}+2 t_{1} t_{4}^{2}\right) 它的第一项与空旋转（即
360
∘
360
∘
360^(@) 360^{\circ}
180
∘
180
∘
180^(@) 180^{\circ}
轮换 周期表 周期结构
(
1
2
3
4
3
1
4
2
)
1
2
3
4
3
1
4
2
([1,2,3,4],[3,1,4,2]) \left(\begin{array}{llll}1 & 2 & 3 & 4 \\ 3 & 1 & 4 & 2\end{array}\right)
(
1
3
4
2
)
1
3
4
2
([1,3,4,2]) \left(\begin{array}{llll}1 & 3 & 4 & 2\end{array}\right)
t
4
t
4
t_(4) t_{4}
(
1
2
3
4
4
3
2
1
)
1
2
3
4
4
3
2
1
([1,2,3,4],[4,3,2,1]) \left(\begin{array}{llll}1 & 2 & 3 & 4 \\ 4 & 3 & 2 & 1\end{array}\right)
(
1
4
)
(
23
)
1
4
(
23
)
([1,4])(23) \left(\begin{array}{lll}1 & 4\end{array}\right)(23)
t
2
2
t
2
2
t_(2)^(2) t_{2}^{2}
(
1
2
3
4
2
4
1
3
)
1
2
3
4
2
4
1
3
([1,2,3,4],[2,4,1,3]) \left(\begin{array}{llll}1 & 2 & 3 & 4 \\ 2 & 4 & 1 & 3\end{array}\right)
(
1
2
4
3
)
1
2
4
3
([1,2,4,3]) \left(\begin{array}{llll}1 & 2 & 4 & 3\end{array}\right)
t
4
t
4
t_(4) t_{4}
(
1
2
3
4
1
2
3
4
)
1
2
3
4
1
2
3
4
([1,2,3,4],[1,2,3,4]) \left(\begin{array}{llll}1 & 2 & 3 & 4 \\ 1 & 2 & 3 & 4\end{array}\right)
(
1
)
(
2
)
(
3
)
(
4
)
(
1
)
(
2
)
(
3
)
(
4
)
(1)(2)(3)(4) (1)(2)(3)(4)
t
1
4
t
1
4
t_(1)^(4) t_{1}^{4}
思考
(
1
2
3
4
3
4
1
2
)
1
2
3
4
3
4
1
2
([1,2,3,4],[3,4,1,2]) \left(\begin{array}{llll}1 & 2 & 3 & 4 \\ 3 & 4 & 1 & 2\end{array}\right)
(
1
3
)
(
24
)
1
3
(
24
)
([1,3])(24) \left(\begin{array}{lll}1 & 3\end{array}\right)(24)
t
2
2
t
2
2
t_(2)^(2) t_{2}^{2}
(
1
2
3
4
2
1
4
3
)
1
2
3
4
2
1
4
3
([1,2,3,4],[2,1,4,3]) \left(\begin{array}{llll}1 & 2 & 3 & 4 \\ 2 & 1 & 4 & 3\end{array}\right)
(
1
2
)
(
3
4
)
1
2
(
3
4
)
([1,2])(3quad4) \left(\begin{array}{lll}1 & 2\end{array}\right)(3 \quad 4)
t
2
2
t
2
2
t_(2)^(2) t_{2}^{2}
(
1
2
3
4
1
3
2
4
)
1
2
3
4
1
3
2
4
([1,2,3,4],[1,3,2,4]) \left(\begin{array}{llll}1 & 2 & 3 & 4 \\ 1 & 3 & 2 & 4\end{array}\right)
(
1
)
(
23
)
(
4
)
(
1
)
(
23
)
(
4
)
(1)(23)(4) (1)(23)(4)
t
1
2
t
2
t
1
2
t
2
t_(1)^(2)t_(2) t_{1}^{2} t_{2}
(
1
2
3
4
4
2
3
1
)
1
2
3
4
4
2
3
1
([1,2,3,4],[4,2,3,1]) \left(\begin{array}{llll}1 & 2 & 3 & 4 \\ 4 & 2 & 3 & 1\end{array}\right)
(
14
)
(
2
)
(
3
)
(
14
)
(
2
)
(
3
)
(14)(2)(3) (14)(2)(3)
t
1
2
t
2
t
1
2
t
2
t_(1)^(2)t_(2) t_{1}^{2} t_{2}
rotations cycle form cycle structure
([1,2,3,4],[3,1,4,2]) ([1,3,4,2]) t_(4)
([1,2,3,4],[4,3,2,1]) ([1,4])(23) t_(2)^(2)
([1,2,3,4],[2,4,1,3]) ([1,2,4,3]) t_(4)
([1,2,3,4],[1,2,3,4]) (1)(2)(3)(4) t_(1)^(4)
reflections
([1,2,3,4],[3,4,1,2]) ([1,3])(24) t_(2)^(2)
([1,2,3,4],[2,1,4,3]) ([1,2])(3quad4) t_(2)^(2)
([1,2,3,4],[1,3,2,4]) (1)(23)(4) t_(1)^(2)t_(2)
([1,2,3,4],[4,2,3,1]) (14)(2)(3) t_(1)^(2)t_(2). | rotations | cycle form | cycle structure |
| :---: | :---: | :---: |
| $\left(\begin{array}{llll}1 & 2 & 3 & 4 \\ 3 & 1 & 4 & 2\end{array}\right)$ | $\left(\begin{array}{llll}1 & 3 & 4 & 2\end{array}\right)$ | $t_{4}$ |
| $\left(\begin{array}{llll}1 & 2 & 3 & 4 \\ 4 & 3 & 2 & 1\end{array}\right)$ | $\left(\begin{array}{lll}1 & 4\end{array}\right)(23)$ | $t_{2}^{2}$ |
| $\left(\begin{array}{llll}1 & 2 & 3 & 4 \\ 2 & 4 & 1 & 3\end{array}\right)$ | $\left(\begin{array}{llll}1 & 2 & 4 & 3\end{array}\right)$ | $t_{4}$ |
| $\left(\begin{array}{llll}1 & 2 & 3 & 4 \\ 1 & 2 & 3 & 4\end{array}\right)$ | $(1)(2)(3)(4)$ | $t_{1}^{4}$ |
| reflections | | |
| $\left(\begin{array}{llll}1 & 2 & 3 & 4 \\ 3 & 4 & 1 & 2\end{array}\right)$ | $\left(\begin{array}{lll}1 & 3\end{array}\right)(24)$ | $t_{2}^{2}$ |
| $\left(\begin{array}{llll}1 & 2 & 3 & 4 \\ 2 & 1 & 4 & 3\end{array}\right)$ | $\left(\begin{array}{lll}1 & 2\end{array}\right)(3 \quad 4)$ | $t_{2}^{2}$ |
| $\left(\begin{array}{llll}1 & 2 & 3 & 4 \\ 1 & 3 & 2 & 4\end{array}\right)$ | $(1)(23)(4)$ | $t_{1}^{2} t_{2}$ |
| $\left(\begin{array}{llll}1 & 2 & 3 & 4 \\ 4 & 2 & 3 & 1\end{array}\right)$ | $(14)(2)(3)$ | $t_{1}^{2} t_{2}$. |
表 1.
2
×
2
2
×
2
2xx2 2 \times 2 伯恩赛德定理 伯恩赛德-波利亚计数法的基础是对循环指数的替换。用数字 2 代替循环指数中的每个变量，可以简单说明这种方法的原理
1
8
(
t
1
4
+
2
t
1
2
t
2
+
3
t
2
2
+
2
t
4
)
1
8
t
1
4
+
2
t
1
2
t
2
+
3
t
2
2
+
2
t
4
(1)/(8)(t_(1)^(4)+2t_(1)^(2)t_(2)+3t_(2)^(2)+2t_(4)) \frac{1}{8}\left(t_{1}^{4}+2 t_{1}^{2} t_{2}+3 t_{2}^{2}+2 t_{4}\right) 替换的结果是算术表达式
1
8
(
2
4
+
2
⋅
2
2
2
+
3
⋅
2
2
+
2
⋅
2
)
1
8
2
4
+
2
⋅
2
2
2
+
3
⋅
2
2
+
2
⋅
2
(1)/(8)(2^(4)+2*2^(2)2+3*2^(2)+2*2) \frac{1}{8}\left(2^{4}+2 \cdot 2^{2} 2+3 \cdot 2^{2}+2 \cdot 2\right) 简化为
1
8
(
16
+
16
+
12
+
4
)
=
6
1
8
(
16
+
16
+
12
+
4
)
=
6
(1)/(8)(16+16+12+4)=6 \frac{1}{8}(16+16+12+4)=6 正好是图 5 中出现的配置数量。
这个过程总能得出轨道总数的数学结果被称为伯恩赛德定理（Burnside's Lemma）。在此，我们将借助三个辅助定理来证明这一结果。
让
G
G
G G
Y
Y
Y Y
y
y
y y
Stab
(
y
)
Stab
(
y
)
Stab(y) \operatorname{Stab}(y)
G
G
G G
y
y
y y 显然，固定
y
y
y y
y
y
y y
y
y
y y
y
y
y y
Stab
(
y
)
Stab
(
y
)
Stab(y) \operatorname{Stab}(y)
G
G
G G
Stab
(
y
)
Stab
(
y
)
Stab(y) \operatorname{Stab}(y)
G
G
G G 例 14 在 1 号和 4 号位置上画十字，在 2 号和 3 号位置上画九宫格，
2
×
2
2
×
2
2xx2 2 \times 2 解：它的稳定子是由这四种排列组合组成的子群
(
1
)
(
2
)
(
3
)
(
4
)
(
1
4
)
(
2
3
)
(
1
4
)
(
2
)
(
3
)
(
1
)
(
2
)
3
)
(
4
)
.
(
1
)
(
2
)
(
3
)
(
4
)
1
4
)
(
2
3
1
4
(
2
)
(
3
)
(
1
)
(
2
)
3
(
4
)
.
{:(1)(2)(3)(4)quad([1,4)(2,3])quad([1,4])(2)(3)quad(1)(2)3)(4). \left.(1)(2)(3)(4) \quad\left(\begin{array}{lll}
1 & 4)(2 & 3
\end{array}\right) \quad\left(\begin{array}{ll}
1 & 4
\end{array}\right)(2)(3) \quad(1)(2) 3\right)(4) . 固定该配置的排列组合的必要条件和充分条件是，每个周期内出现的所有位置的标记都相同，即都是 "叉 "或都是 "划"。
正如我们将固定
y
y
y y
Stab
(
y
)
Stab
(
y
)
Stab(y) \operatorname{Stab}(y)
y
y
y y
π
π
pi \pi
π
π
pi \pi
Fix
(
π
)
Fix
(
π
)
Fix(pi) \operatorname{Fix}(\pi)
π
π
pi \pi 例 15 有哪些
2
×
2
2
×
2
2xx2 2 \times 2
(
1
)
(
2
)
(
3
)
(
4
)
(
1
)
(
2
)
(
3
)
(
4
)
(1)(2)(3)(4) (1)(2)(3)(4) 
