伯恩赛德-波利亚计数法
作者:乔纳森:乔纳森-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) ,等于 126 个。
在玩井字游戏时,如果可以通过旋转或反射棋盘从另一个配置中获得另一个配置,那么自然可以将这两个配置视为等价配置。例如,在图 1 中,配置(B)可以通过逆时针旋转配置(A)
90
∘
90
∘
90^(@) 90^{\circ} 来获得,而 © 可以通过水平反射配置(A)来获得。如果我们认为这些配置是 "相同 "的,那么有多少种 "真正不同 "的配置呢?
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 有五个十字和四个九宫格的配置正好有 23 个不同的同余类。一个很好的练习是不使用伯恩赛德-波利亚理论,通过系统地应用特别方法来推导出这个数字。这种尝试很容易出错。伯恩赛德-波利亚理论有两个优点:它减少了特别方法固有的出错几率,而且适用于其他涉及大到特别计数不可行的万有引力的计算。
排列组合
井字棋盘上的旋转或反射是从有限集合到自身的双射(即一一对应函数)的一种特例,通常称为置换。如果我们在井字棋盘的九个方格上标注 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\} 上的所有 9 种排列都可以用
2
×
9
2
×
9
2xx9 2 \times 9 矩阵来描述,但其中只有四种排列表示井字棋盘上的旋转,另外四种排列表示反射。为简化起见,我们暂且以
2
×
2
2
×
2
2xx2 2 \times 2 井字棋为例,其方格的标记如图 4 所示。
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\} 上的所有 4 种排列都可以用
2
×
4
2
×
4
2xx4 2 \times 4 矩阵来描述。其中表示旋转和反射的 8 个矩阵如下: 轮换:
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 和 6 的内容在另一个长度为四的封闭循环中移动。我们还注意到,排列固定了位置 5 的内容,即棋盘的中心。我们可以将其视为长度为一的循环。两个长度为四的循环加上长度为一的循环构成了棋盘上所有九个位置的内容。
通过这种分析,我们可以将排列组合表示为
(
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 矩阵表示。我们可以将有两个 4 循环和一个 1 循环这一事实编码为多元单项式
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 的不相交循环形式的 1 循环中出现的对象集合。
例 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)