这是用户在 2025-1-1 19:53 为 https://app.immersivetranslate.com/pdf-pro/70946982-2f41-4e37-9cd4-002770ad2804 保存的双语快照页面，由 沉浸式翻译 提供双语支持。了解如何保存？


伯恩赛德-波利亚计数法


作者：乔纳森：乔纳森-L-格罗斯，哥伦比亚大学计算机科学系。

先决条件本章的先决条件是集合上的组合、等价关系和双射。参见《离散数学及其应用》第 2.3、5.3 和 8.5 节。

  导言


如果一个井字游戏玩到所有空格都被填满，那么得到的网格将有 5 个十字和 4 个九（也称为 "哦"）。通过计算组合数，可以得出有 5 个叉和 4 个划的 3 × 3 3 × 3 3xx33 \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 xx x x xx x x xx
0 x x xx x x xx
0 0 0
x x x 0 x x 0 0 0| $x$ | $x$ | $x$ | | :---: | :---: | :---: | | 0 | $x$ | $x$ | | 0 | 0 | 0 |
(A)
x x xx x x xx 0
x x xx x x xx 0
x x xx 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 xx x x xx
x x xx x x xx x x xx
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 CCCPC C C P 问题。遗憾的是，事情并非如此简单，现在就来说明一下。

例 1 计算与图 2 中的配置 (D)、(E) 和 (F) 等价的配置数。
x x xx 0 x x xx
0 x x xx 0
x x xx 0 x x xx
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 CCCPC 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| 1 | 2 | 3 | | :--- | :--- | :--- | | 4 | 5 | 6 | | 7 | 8 | 9 |

图 3.用整数标记井字方格。

然后逆时针旋转四分之一圈，方格 1 变为方格 7，方格 2 变为方格 4，方格 3 变为方格 1，依此类推。井字棋盘上每个位置的变化都可以记录在一个 2 × 9 2 × 9 2xx92 \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 nn 的有限集合上的任何排列都可以用这样一个 2 × n 2 × n 2xx n2 \times n 矩阵来完全描述。

集合 { 1 , 2 … , 9 } { 1 , 2 … , 9 } {1,2dots,9}\{1,2 \ldots, 9\} 上的所有 9 种排列都可以用 2 × 9 2 × 9 2xx92 \times 9 矩阵来描述，但其中只有四种排列表示井字棋盘上的旋转，另外四种排列表示反射。为简化起见，我们暂且以 2 × 2 2 × 2 2xx22 \times 2 井字棋为例，其方格的标记如图 4 所示。
1 2
3 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 2xx42 \times 4 矩阵来描述。其中表示旋转和反射的 8 个矩阵如下：
  轮换：
90 ∘ 180 ∘ 90 ∘ 180 ∘ 90^(@)180^(@)90^{\circ} 180^{\circ} c c c c c c cccc 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@fg \circ f 时，可以方便地考虑其他排序。要进行此操作，请将 g g gg 的 2 × n 2 × n 2xx n2 \times n 矩阵表示写在 f f ff 的 2 × n 2 × n 2xx n2 \times n 矩阵表示的下方。 f f ff 的列应像往常一样排序、
1 , 2 , … , n 1 , 2 , … , n 1,2,dots,n1,2, \ldots, n

g g gg 的列应按顺序排列，以便顶行按以下顺序排列
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 ff 矩阵的底行相匹配。然后， g g gg 的矩阵底行将按以下顺序出现
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@fg \circ f 的 2 × n 2 × n 2xx n2 \times n 矩阵是通过将 g g gg 矩阵的最下面一行紧接着 f f ff 矩阵的最上面一行依次写入而形成的。

例如，对于 2 × 2 2 × 2 2xx22 \times 2 板，假设逆时针转动四分之一圈为 f f ff ，水平反射为 g g gg 。那么这个过程如下：
( 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 n2 \times n 矩阵表示的组成规则或几何推理，可以证明 2 × 2 2 × 2 2xx22 \times 2 井字棋盘的下列性质：

(1) 两个旋转的组合就是一个旋转。

(2) 两个反射的组合就是旋转。

(3) 旋转与反射或反射与旋转的组合就是反射。

结合这三个论断，我们可以立即推断出以下定理。

定理 1 2 × 2 2 × 2 2xx22 \times 2 井字棋盘的旋转或反射与另一个旋转或反射的组合是旋转或反射。

如果一个有限集合上的排列集合中的任意两个排列组成时，所产生的排列也在该集合中，则该集合在组成下是封闭的。

例 2 证明 2 × 2 2 × 2 2xx22 \times 2 井字棋盘上的旋转和反射集合在组成下是封闭的。

解：我们已经通过定理 1 确定了这一点。

例 3 证明 2 × 2 2 × 2 2xx22 \times 2 井字棋盘上所有四个旋转的集合在组成下是封闭的。

解决方案：这一点从几何图形中显而易见。

例 4 证明仅由 360 ∘ 360 ∘ 360^(@)360^{\circ} 旋转组成的 2 × 2 2 × 2 2xx22 \times 2 井字棋盘上的排列集合在组成下是封闭的。

解决方案：它与自身的构成就是自身。

例 5 证明 2 × 2 2 × 2 2xx22 \times 2 井字棋盘上所有四个反射的集合在组成下不是封闭的。

解：由定理 1 的性质 (2) 得出。

由于置换 π π pi\pi 是一个从集合到自身的双射函数，因此它有一个逆函数，表示为 inv ( π ) inv ( π ) inv(pi)\operatorname{inv}(\pi) 或 π − 1 π − 1 pi^(-1)\pi^{-1} ，它也是一个从集合到自身的双射函数。换句话说，任意集合上的置换的逆就是同一集合上的置换。要根据 2 × n 2 × n 2xx n2 \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 2xx22 \times 2 井字棋盘的这两个附加属性都是由几何推理直接得出的：

(4) 旋转的倒数就是旋转。

(5) 反射的倒数也是同样的反射。

结合这两个性质，我们可以立即推断出以下定理。

定理 2 2 × 2 2 × 2 2xx22 \times 2 井字棋盘的旋转或反射的逆也是旋转或反射。

如果一个有限集合上的排列集合中的每个排列的逆也在这个集合中，那么这个集合就被称为反转下的封闭集合。

有一个特殊的名称来表示在组合和反转下都是封闭的排列集合。它被称为置换群。

例 6 证明 2 × 2 2 × 2 2xx22 \times 2 井字棋盘上所有旋转和反射的集合构成一个置换群。

解：从定理 1 和 2 可以得出结论。

例 7 证明 3 × 3 3 × 3 3xx33 \times 3 井字棋盘上所有旋转和反射的集合构成一个置换群。

解决方案：在 3 × 3 3 × 3 3xx33 \times 3 电路板上应用与 2 × 2 2 × 2 2xx22 \times 2 电路板相同的方法，就可以解决这个问题。

例 8 证明有限集合上所有排列的集合构成一个排列群。

解：由于任意两个排列的组合是一个排列，并且任意排列的逆也是一个排列，因此立即得出结论。

例 9 证明只包含标识置换（它固定每个元素，就像集合上的其他标识函数一样）的单子集合是一个置换群。

解法：同一性与自身的组成就是同一性，同一性的逆就是同一性，所以集合在组成和反转下都是封闭的。

在本节的最后，我们将井字棋盘的全等类概念放到一个更广阔的背景中，以适应伯恩赛德-波利亚计数理论。

当一个置换群 G G GG 作用于一个集合 Y Y YY 时，我们通常称该集合的元素为对象。特别是，当置换群是 3 × 3 3 × 3 3xx33 \times 3 井字棋盘上旋转和反射的集合时，具有五个十字和四个九宫格的井字棋配置就是对象。

如果 y y yy 是集合 Y Y YY 中的任一对象，那么对于每一次置换 π ∈ G π ∈ G pi in G\pi \in G 来说，对象 π ( y ) π ( y ) pi(y)\pi(y) 都被认为与 y y yy 相关。如果 y y yy 和 y ′ y ′ y^(')y^{\prime} 以这种方式相关，我们将其写为 y R y ′ y R y ′ yRy^(')y R y^{\prime} ，并且我们说 R R RR 是 G G GG 作用所诱导的关系。

定理 3 由置换群 P P PP 作用于对象集合 Y Y YY 所引起的关系 R R RR 是等价关系。

证明给定任何对象 y y yy ，让 I I II 表示同一置换。则有 y R I ( y ) y R I ( y ) yRI(y)y R I(y) 。换句话说，每个对象 y y yy 都与自身相关，由此推导出关系 R R RR 是反向的。

接下来，给定任意两个对象 y y yy 和 y ′ y ′ y^(')y^{\prime} ，假设 y R y ′ y R y ′ yRy^(')y R y^{\prime} ，这意味着在 G G GG 群中存在一个置换 π π 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^(')Ryy^{\prime} R y 。这样，我们就确定了关系 R R RR 是对称的。

最后，如果 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 GG 中存在 π π 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 GG 在组合下是封闭的，所以显然 μ ∘ π ∈ 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 RR 是传递的。

在确定了关系 R R RR 的反身性、对称性和传递性后，我们得出结论：这是一个等价关系。

置换群对一组对象的作用所引起的等价类通常称为轨道。

例 10 旋转和反射群对井字棋盘的构型的作用所引起的轨道是什么？

解决方案：它们就是同余类。

例 11 当所有可能的排列组合作用于一组物体时，会形成多少个轨道？

解：只有一个轨道，它包含了集合的所有元素。

引入这些代数概念后，我们就能把伯恩赛德-波利亚枚举理论的目标最清晰地表述为一种计算作用于有限集合的置换群轨道的方法。实际上，弗罗贝尼乌斯发明了计算轨道的方法，但它出现在伯恩赛德的经典小册子[1]中，因此被称为 "伯恩赛德定理"。

Pólya* [3] 用一种为轨道分配 "权重 "的方法增强了这一理论

并将轨道总数分解为每个权重等级的轨道数之和。实际上，波利亚重新发现了雷德菲尔德（Redfield）[4] 早已知道的方法，而雷德菲尔德的论文却没有引起大多数人的注意。哈拉里（F. Harary）（见 [2]）将伯恩赛德-波利亚枚举理论用于图形枚举，吸引了许多数学家进一步应用它。我们将通过伯恩赛德-波利亚理论的详细应用，展示如何计算引言中提到的 23 个构型的全等类，从而求解 C C C P C C C P CCCPC C C P 。在此过程中，我们还将努力实现一个中间目标，即计算出 2 × 2 2 × 2 2xx22 \times 2 九宫格和十字格中没有空格的井字格配置的全等类。

由于四个方格中每个方格的填充都涉及二元选择，因此共有 16 个这样的配置。单凭伯恩赛德的方法，我们就能确定有六种轨道，而波利亚的扩充方法则提供了将这六种轨道分为以下子类的 "清单"：

1 个轨道上有 4 个十字和 0 个下划线

1 个轨道，3 个十字，1 个无

2 个有两个十字和两个九的轨道

1 个带 1 个十字和 3 个诺的轨道

1 个轨道，0 个十字和 4 个九宫格。

图 5 为这六个轨道各提供了一个配置示例。你可以很容易地证明，16 种构型中的每一种都可以旋转或反射成所示 6 个示例中的一种。

图 5.在旋转和反射组下， 2 × 2 2 × 2 2xx22 \times 2 井字棋的六个轨道各有一个构型。


排列组合的循环结构


现在我们回到 2 × 9 2 × 9 2xx92 \times 9 在 3 × 3 3 × 3 3xx33 \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,31,7,9,3 四个位置的内容在一个封闭的循环中移动。

同样，我们注意到位置 2 , 4 , 8 2 , 4 , 8 2,4,82,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 n2 \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 2xx22 \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 GG 中所有排列的循环结构相加并除以该组的万有引力时，得到的多项式称为 G G GG 的循环指数，记为 Z ( G ) Z ( G ) Z(G)Z(G) 。

例 12 在 2 × 2 2 × 2 2xx22 \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 3xx33 \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 2xx22 \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 GG 成为作用于对象集合 Y Y YY 的置换群。对象 y y yy 的稳定子表示 Stab ( y ) Stab ( y ) Stab(y)\operatorname{Stab}(y) ，我们指的是 G G GG 中将 y y yy 映射到自身的排列集合。

显然，固定 y y yy 的两个排列的组合也是固定 y y yy 的排列。同样明显的是，固定 y y yy 的排列的逆排列也是固定 y y yy 的排列。因此， Stab ( y ) Stab ( y ) Stab(y)\operatorname{Stab}(y) 也是一个置换群。由于它完全包含在 G G GG 群中，我们称 Stab ( y ) Stab ( y ) Stab(y)\operatorname{Stab}(y) 为 G G GG 的子群。

例 14 在 1 号和 4 号位置上画十字，在 2 号和 3 号位置上画九宫格， 2 × 2 2 × 2 2xx22 \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 yy 的排列集合 Stab ( y ) Stab ( y ) Stab(y)\operatorname{Stab}(y) 与每个对象 y y yy 联系起来一样，我们将固定 π π pi\pi 的对象集合与每个排列联系起来。这个集合称为 π π pi\pi 的定点集合，记为 Fix ( π ) Fix ( π ) Fix(pi)\operatorname{Fix}(\pi) ，它包括在 π π pi\pi 的不相交循环形式的 1 循环中出现的对象集合。

例 15 有哪些 2 × 2 2 × 2 2xx22 \times 2 井字形配置是由排列 ( 1 ) ( 2 ) ( 3 ) ( 4 ) ( 1 ) ( 2 ) ( 3 ) ( 4 ) (1)(2)(3)(4)(1)(2)(3)(4) 固定的？

解决方案：它可以修复所有 16 个完全填满的 2 × 2 2 × 2 2xx22 \times 2 井字游戏配置。

例 16 有哪些 2 × 2 2 × 2 2xx22 \times 2 井字形配置是由排列 ( 14 ) ( 2 3 ) ( 14 ) ( 2 3 ) (14)(2quad3)(14)(2 \quad 3) 固定的？

解：当排列组合 (14)(23) 作用于 2 × 2 2 × 2 2xx22 \times 2 井字符号配置时，它会调换位置 1 和位置 4 的标记，并调换位置 2 和位置 3 的标记。因此，当且仅当位置 1 和位置 4 的内容相同，以及位置 2 和位置 3 的内容相同时，它才会固定井字配置。由于四个位置中的每个位置都要填上一个十字或一个空格，因此位置 1 和位置 4 的标记类型有两种选择，位置 2 和位置 3 的标记类型也有两种选择。因此， ( 14 ) ( 2 3 ) ( 14 ) 2 3 (14)([2,3])(14)\left(\begin{array}{ll}2 & 3\end{array}\right) 固定了四种井字符号配置。

例 17 通过排列 (1 4)(2)(3) 可以固定哪些 2 × 2 2 × 2 2xx22 \times 2 井字形配置？

解决方案：通过对例 16 同样的分析，我们可以看到 ( 14 ) ( 2 ) ( 3 ) ( 14 ) ( 2 ) ( 3 ) (14)(2)(3)(14)(2)(3) 固定了一个配置，当且仅当位置 1 和位置 4 填入相同的标记；位置 2 和位置 3 的标记都是任意的。因此，我们有三种二进制标记选择：位置 1 和位置 4 的标记、位置 2 的标记和位置 3 的标记。由此可见，排列 ( 14 ) ( 2 ) ( 3 ) ( 14 ) ( 2 ) ( 3 ) (14)(2)(3)(14)(2)(3) 固定了八个（即 2 3 ) 2 3 {:2^(3))\left.2^{3}\right) 配置）。

证明伯恩赛德定理所需的三个公理中，第一个公理涉及交换指数对双重求和的影响。其证明涉及艾弗森真值函数 true ( p ) true ( p ) true(p)\operatorname{true}(p) 的使用，如果 p p pp 是真语句，则其值为 1，否则为 0。

定理 1 稳定器的心数之和，取自包络集 Y Y YY 的所有对象，等于定点集的心数之和，取自作用于 Y Y YY 的群 G G GG 中的所有包络。也就是说
∑ y ∈ Y | Stab ( y ) | = ∑ π ∈ G | Fix ( π ) | . ∑ y ∈ Y   | Stab ( y ) | = ∑ π ∈ G   | Fix ( π ) | . sum_(y in Y)|Stab(y)|=sum_(pi in G)|Fix(pi)|.\sum_{y \in Y}|\operatorname{Stab}(y)|=\sum_{\pi \in G}|\operatorname{Fix}(\pi)| .

证明 quad\quad 因为 Stab ( y ) = { π : π ( y ) = y } Stab ( y ) = { π : π ( y ) = y } Stab(y)={pi:pi(y)=y}\operatorname{Stab}(y)=\{\pi: \pi(y)=y\} ，所以
| Stab ( y ) | = ∑ π ∈ G true ( π ( y ) = y ) . | Stab ( y ) | = ∑ π ∈ G   true ( π ( y ) = y ) . |Stab(y)|=sum_(pi in G)true(pi(y)=y).|\operatorname{Stab}(y)|=\sum_{\pi \in G} \operatorname{true}(\pi(y)=y) .
  因此
∑ y ∈ Y | Stab ( y ) | = ∑ y ∈ Y ∑ π ∈ G true ( π ( y ) = y ) = ∑ π ∈ G ∑ y ∈ Y true ( π ( y ) = y ) = ∑ π ∈ G | Fix ( π ) | . ( because interchanging indices of summation) ∑ y ∈ Y true ( π ( y ) = y ) = | Fix ( π ) | ) ∑ y ∈ Y   | Stab ( y ) | = ∑ y ∈ Y   ∑ π ∈ G   true ( π ( y ) = y ) = ∑ π ∈ G   ∑ y ∈ Y   true ( π ( y ) = y ) = ∑ π ∈ G   | Fix ( π ) | .  because interchanging indices of summation)  ∑ y ∈ Y   true ( π ( y ) = y ) = | Fix ( π ) | {:[sum_(y in Y)|Stab(y)|=sum_(y in Y)sum_(pi in G)true(pi(y)=y)],[=sum_(pi in G)sum_(y in Y)true(pi(y)=y)],[=sum_(pi in G)|Fix(pi)|.],[quad(" because interchanging indices of summation) "sum_(y in Y)true(pi(y)=y)=|Fix(pi)|)]:}\begin{aligned} & \sum_{y \in Y}|\operatorname{Stab}(y)|=\sum_{y \in Y} \sum_{\pi \in G} \operatorname{true}(\pi(y)=y) \\ &=\sum_{\pi \in G} \sum_{y \in Y} \operatorname{true}(\pi(y)=y) \\ &=\sum_{\pi \in G}|\operatorname{Fix}(\pi)| . \\ & \quad\left(\text { because interchanging indices of summation) } \sum_{y \in Y} \operatorname{true}(\pi(y)=y)=|\operatorname{Fix}(\pi)|\right) \end{aligned}

定理 2 对于在置换群 G G GG 作用下的置换对象集合 Y Y YY 中的任何对象 y y yy 、
| Stab ( y ) | = | G | | orbit ( y ) | | Stab ( y ) | = | G | | orbit ( y ) | |Stab(y)|=(|G|)/(|orbit(y)|)|\operatorname{Stab}(y)|=\frac{|G|}{|\operatorname{orbit}(y)|}

证明假设 orbit ( y ) = { y 1 , y 2 , … , y n } orbit ( y ) = y 1 , y 2 , … , y n orbit(y)={y_(1),y_(2),dots,y_(n)}\operatorname{orbit}(y)=\left\{y_{1}, y_{2}, \ldots, y_{n}\right\} ，其中 y = y 1 y = y 1 y=y_(1)y=y_{1} 。那么对于 j = 1 , 2 , … , n j = 1 , 2 , … , n j=1,2,dots,nj=1,2, \ldots, n ，我们定义
G j = { π ∈ G : π ( y ) = y j } G j = π ∈ G : π ( y ) = y j G_(j)={pi in G:pi(y)=y_(j)}G_{j}=\left\{\pi \in G: \pi(y)=y_{j}\right\}

换句话说， G j G j G_(j)G_{j} 是将 y y yy 映射到 y j y j y_(j)y_{j} 的 G G GG 中排列的子集。显然， { G 1 , G 2 , … , G n } G 1 , G 2 , … , G n {G_(1),G_(2),dots,G_(n)}\left\{G_{1}, G_{2}, \ldots, G_{n}\right\} 是组中排列的一个分区，而 G 1 = G 1 = G_(1)=G_{1}= Stab ( y ) Stab ( y ) Stab(y)\operatorname{Stab}(y) .

对于 j = 1 , 2 , … , n j = 1 , 2 , … , n j=1,2,dots,nj=1,2, \ldots, n ，让 π j π j pi_(j)\pi_{j} 成为任意排列，使得 π j ( y ) = y j π j ( y ) = y j pi_(j)(y)=y_(j)\pi_{j}(y)=y_{j} 。那么，与 π j π j pi_(j)\pi_{j} 的组合将 G 1 G 1 G_(1)G_{1} 中的每个排列映射到 G j G j G_(j)G_{j} 中的一个排列，而与 π j − 1 π j − 1 pi_(j)^(-1)\pi_{j}^{-1} 的组合将 G j G j G_(j)G_{j} 中的每个排列映射到 G 1 G 1 G_(1)G_{1} 中的一个排列。由此可知，与 π j π j pi_(j)\pi_{j} 组成是从 G 1 G 1 G_(1)G_{1} 到 G j G j G_(j)G_{j} 的双射，这意味着 | G j | = | G 1 | = | Stab ( y ) | G j = G 1 = | Stab ( y ) | |G_(j)|=|G_(1)|=|Stab(y)|\left|G_{j}\right|=\left|G_{1}\right|=|\operatorname{Stab}(y)| 。

由于 { G 1 , G 2 , … , G n } G 1 , G 2 , … , G n {G_(1),G_(2),dots,G_(n)}\left\{G_{1}, G_{2}, \ldots, G_{n}\right\} 是将 G G GG 分割成大小为 | Stab ( y ) | | Stab ( y ) | |Stab(y)||\operatorname{Stab}(y)| 的子集，因此 | Stab ( y ) | | Stab ( y ) | |Stab(y)||\operatorname{Stab}(y)| 与子集数 n = | orbit ( y ) | n = | orbit ( y ) | n=|orbit(y)|n=|\operatorname{orbit}(y)| 的乘积等于 | G | | G | |G||G| 。等价地， | Stab ( y ) | = | G | / | orbit ( y ) | | Stab ( y ) | = | G | / | orbit ( y ) | |Stab(y)|=|G|//|orbit(y)||\operatorname{Stab}(y)|=|G| /|\operatorname{orbit}(y)| 。

重温例 14。我们回顾一下，主对角线上有十字（即位置 1 和 4）、小对角线上有九角（即位置 2 和 3）的配置的稳定子中有四个元素。由于其轨道中唯一的其他配置是小对角线上有十字，主对角线上有九角的配置，因此其轨道的奇数为 2。由于作用于配置集的置换群中有八个旋转和反射，因此方程
4 = 8 / 2 4 = 8 / 2 4=8//24=8 / 2

作为推理 2 正确性的经验证据。

定理 3 假设 G G GG 是作用于对象集合 Y Y YY 的置换群。那么
∑ y ∈ Y 1 | orbit ( y ) | = # orbits ∑ y ∈ Y   1 | orbit ( y ) | = #  orbits  sum_(y in Y)(1)/(|orbit(y)|)=#" orbits "\sum_{y \in Y} \frac{1}{|\operatorname{orbit}(y)|}=\# \text { orbits }

证明： quad\quad 假设 # # #\# 的轨道是 = k = k =k=k ，并且 Y 1 , Y 2 , … , Y k Y 1 , Y 2 , … , Y k Y_(1),Y_(2),dots,Y_(k)Y_{1}, Y_{2}, \ldots, Y_{k} 是轨道。那么
∑ y ∈ Y 1 | orbit ( y ) | = ∑ j = 1 k ∑ y ∈ Y j 1 | orbit ( y ) | = ∑ j = 1 k ∑ y ∈ Y j 1 | Y j | = ∑ j = 1 k 1 | Y j | ∑ y ∈ Y j 1 ∑ y ∈ Y   1 | orbit ( y ) | = ∑ j = 1 k   ∑ y ∈ Y j   1 | orbit ( y ) | = ∑ j = 1 k   ∑ y ∈ Y j   1 Y j = ∑ j = 1 k   1 Y j ∑ y ∈ Y j   1 {:[sum_(y in Y)(1)/(|orbit(y)|)=sum_(j=1)^(k)sum_(y inY_(j))(1)/(|orbit(y)|)],[=sum_(j=1)^(k)sum_(y inY_(j))(1)/(|Y_(j)|)],[=sum_(j=1)^(k)(1)/(|Y_(j)|)sum_(y inY_(j))1]:}\begin{aligned} \sum_{y \in Y} \frac{1}{|\operatorname{orbit}(y)|} & =\sum_{j=1}^{k} \sum_{y \in Y_{j}} \frac{1}{|\operatorname{orbit}(y)|} \\ & =\sum_{j=1}^{k} \sum_{y \in Y_{j}} \frac{1}{\left|Y_{j}\right|} \\ & =\sum_{j=1}^{k} \frac{1}{\left|Y_{j}\right|} \sum_{y \in Y_{j}} 1 \end{aligned}
= ∑ j = 1 k 1 | Y j | | Y j | = ∑ j = 1 k 1 = k = # orbits. = ∑ j = 1 k   1 Y j Y j = ∑ j = 1 k   1 = k = #  orbits.  {:[=sum_(j=1)^(k)(1)/(|Y_(j)|)|Y_(j)|],[=sum_(j=1)^(k)1],[=k],[=#" orbits. "]:}\begin{aligned} & =\sum_{j=1}^{k} \frac{1}{\left|Y_{j}\right|}\left|Y_{j}\right| \\ & =\sum_{j=1}^{k} 1 \\ & =k \\ & =\# \text { orbits. } \end{aligned}

(这个 Lemma 实际上是一个关于集合分区的事实，与置换群代数无关）。

定理 4（伯恩赛德定理 让 G G GG 是作用于对象集合 Y Y YY 的置换群。那么
# orbits = 1 | G | ∑ π ∈ G | Fix ( π ) | #  orbits  = 1 | G | ∑ π ∈ G   | Fix ( π ) | #" orbits "=(1)/(|G|)sum_(pi in G)|Fix(pi)|\# \text { orbits }=\frac{1}{|G|} \sum_{\pi \in G}|\operatorname{Fix}(\pi)|

证明：我们已经证明了推理 1、2 和 3，因此可以通过一系列替换来证明伯恩赛德推理。
1 | G | ∑ π ∈ G | Fix ( π ) | = 1 | G | ∑ y ∈ Y | Stab ( y ) | by Lemma 1 = 1 | G | ∑ y ∈ Y | G | | orbit ( y ) | by Lemma 2 = 1 | G | | G | ∑ y ∈ Y 1 | orbit ( y ) | = ∑ y ∈ Y 1 | orbit ( y ) | = # orbits. by Lemma 3 1 | G | ∑ π ∈ G   | Fix ( π ) | = 1 | G | ∑ y ∈ Y   | Stab ( y ) |  by Lemma 1  = 1 | G | ∑ y ∈ Y   | G | | orbit ( y ) |  by Lemma 2  = 1 | G | | G | ∑ y ∈ Y   1 | orbit ( y ) | = ∑ y ∈ Y   1 | orbit ( y ) | = #  orbits.   by Lemma 3  {:[(1)/(|G|)sum_(pi in G)|Fix(pi)|=(1)/(|G|)sum_(y in Y)|Stab(y)|" by Lemma 1 "],[=(1)/(|G|)sum_(y in Y)(|G|)/(|orbit(y)|)" by Lemma 2 "],[=(1)/(|G|)|G|sum_(y in Y)(1)/(|orbit(y)|)],[=sum_(y in Y)(1)/(|orbit(y)|)],[=#" orbits. "" by Lemma 3 "]:}\begin{aligned} \frac{1}{|G|} \sum_{\pi \in G}|\operatorname{Fix}(\pi)| & =\frac{1}{|G|} \sum_{y \in Y}|\operatorname{Stab}(y)| & & \text { by Lemma 1 } \\ & =\frac{1}{|G|} \sum_{y \in Y} \frac{|G|}{|\operatorname{orbit}(y)|} & & \text { by Lemma 2 } \\ & =\frac{1}{|G|}|G| \sum_{y \in Y} \frac{1}{|\operatorname{orbit}(y)|} & & \\ & =\sum_{y \in Y} \frac{1}{|\operatorname{orbit}(y)|} & & \\ & =\# \text { orbits. } & & \text { by Lemma 3 } \end{aligned}

为了直接应用伯恩赛德定理，我们将 G G GG 群中所有排列 π π pi\pi 的 | Fix ( π ) | | Fix ( π ) | |Fix(pi)||\operatorname{Fix}(\pi)| 值（即固定对象的个数）相加，然后用它们的和除以 | G | | G | |G||G| （即群的元素个数）。定理 5 将例 14、15 和 16 的分析推广为计算 | Fix ( π ) | | Fix ( π ) | |Fix(pi)||\operatorname{Fix}(\pi)| 值的方法，推论 1 利用定理 5 的结果确定了如何计算配置的全等类的数量。

定理 5 假设 π π pi\pi 是 2 × 2 2 × 2 2xx22 \times 2 井字棋盘的完全填充配置的排列组合，假设 π π pi\pi 在其不相交的循环形式中恰好有 r r rr 个循环。那么 | Fix ( π ) | = 2 r | Fix ( π ) | = 2 r |Fix(pi)|=2^(r)|\operatorname{Fix}(\pi)|=2^{r} .

证明当且仅当 π π pi\pi 的不相交循环形式中的每个循环的所有位置都被标记为相同时，置换才会固定一个配置。

推论 1 完全填充的 2 × 2 2 × 2 2xx22 \times 2 井字构型的全等类数目等于将数字 2 代入旋转和反射群作用的循环指数所得到的算术表达式的值。

证明：定理 5 表明，这正是将伯恩赛德定理应用于这一计数问题的方法。

例 18 在本节开头，我们进行了这一计算，并确认结果为 6，正好是图 5 中出现的配置数。我们可以提出一个相关的问题：如果 2 × 2 2 × 2 2xx22 \times 2 棋盘上的某些位置仍未填满，那么有多少种全等类的配置？

解答：与例 14、例 15 和例 16 以及推论 1 类似的分析表明，只要用数字 3 代替循环指数 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 ( 3 4 + 2 ⋅ 3 2 3 + 3 ⋅ 3 2 + 2 ⋅ 3 ) = 1 8 ( 81 + 54 + 27 + 6 ) = 1 8 ( 168 ) = 21 1 8 3 4 + 2 ⋅ 3 2 3 + 3 ⋅ 3 2 + 2 ⋅ 3 = 1 8 ( 81 + 54 + 27 + 6 ) = 1 8 ( 168 ) = 21 {:[(1)/(8)(3^(4)+2*3^(2)3+3*3^(2)+2*3)=(1)/(8)(81+54+27+6)],[=(1)/(8)(168)],[=21]:}\begin{aligned} \frac{1}{8}\left(3^{4}+2 \cdot 3^{2} 3+3 \cdot 3^{2}+2 \cdot 3\right) & =\frac{1}{8}(81+54+27+6) \\ & =\frac{1}{8}(168) \\ & =21 \end{aligned}

要确认这一结果的正确性，一种方法是在 21 个同位类中的每个类中绘制有代表性的构型，然后确认绘制的列表是完整且不重复的。不过，如果我们把 "空 "看作井字棋盘上的另一种标记，还有一种更简单的方法，那就是仍然使用图 5。

首先，只有一个同余类构型恰好使用一个标记。因为有三个可能的标记，所以我们有三个轨道正好使用一个标记。图 5 显示了四个同余类，它们恰好有两种不同的标记。由于我们可以从集合{交叉、无、空}中选择两种标记，因此有 12 个轨道（即 3 ⋅ 4 3 ⋅ 4 3*43 \cdot 4 ）正好使用两种标记。这样就有 15 个轨道，剩下的就是计算有三种不同标记的轨道了。

假设我们打算使用两个十字架，一个无，一个空。有两种不同的可能轨道，一种是两个十字架位于

一个是水平或垂直相邻的轨道，另一个是两个十字对角并列的轨道。由于同样的分析也适用于计算有两个空、一个十字和一个空的轨道，或有两个空、一个十字和一个空的轨道，因此有六个（即 3-2）轨道有三个不同的标记。由于 15 + 6 = 21 15 + 6 = 21 15+6=2115+6=21 ，我们又一次从经验上验证了伯恩赛德定理的有效性，以及我们将其应用于构型计数问题的方法的有效性。


波利亚盘存法


波利亚对伯恩赛德定理的扩充包括为每个构型分配一个单项式权重，这样在同一轨道上的任何两个构型都会被分配相同的权重。将加权多项式代入循环指数后，得到的多项式就能根据权重枚举出轨道。

首先，我们继续分析 2 × 2 2 × 2 2xx22 \times 2 井字图案，以说明如何使用 Pólya 方法以及该方法提供的清单信息。一个包含 r r rr 个十字和 4 − r 4 − r 4-r4-r 个九宫格的配置所分配的权重是单项式 x r x r x^(r)x^{r} 。请仔细观察我们是如何将其代入多元循环指数的
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) .

对于 r = 1 , 2 , 3 , 4 r = 1 , 2 , 3 , 4 r=1,2,3,4r=1,2,3,4 ，二项式 1 + x r 1 + x r 1+x^(r)1+x^{r} 被替换为变量 t r t r t_(r)t_{r} 的每个实例。得到的表达式为
1 8 ( ( 1 + x ) 4 + 2 ( 1 + x ) 2 ( 1 + x 2 ) + 3 ( 1 + x 2 ) 2 + 2 ( 1 + x 4 ) ) , 1 8 ( 1 + x ) 4 + 2 ( 1 + x ) 2 1 + x 2 + 3 1 + x 2 2 + 2 1 + x 4 , (1)/(8)((1+x)^(4)+2(1+x)^(2)(1+x^(2))+3(1+x^(2))^(2)+2(1+x^(4))),\frac{1}{8}\left((1+x)^{4}+2(1+x)^{2}\left(1+x^{2}\right)+3\left(1+x^{2}\right)^{2}+2\left(1+x^{4}\right)\right),

我们将其扩展为
1 8 ( 1 + 4 x + 6 x 2 + 4 x 3 + x 4 + 2 + 4 x + 4 x 2 + 4 x 3 + 2 x 4 + 3 + 6 x 2 + 3 x 4 + 2 + 2 x 4 ) . 1 8 1 + 4 x + 6 x 2 + 4 x 3 + x 4 + 2 + 4 x + 4 x 2 + 4 x 3 + 2 x 4 + 3 + 6 x 2 + 3 x 4 + 2 + 2 x 4 .  {:(1)/(8)([1+4x+6x^(2),+4x^(3)+x^(4)],[+2+4x+4x^(2),+4x^(3)+2x^(4)],[quad+3+6x^(2),+3x^(4)],[quad+2,],[quad+2x^(4)])". ":}\begin{aligned} & \frac{1}{8}\left(\begin{array}{rr} 1+4 x+6 x^{2} & +4 x^{3}+x^{4} \\ +2+4 x+4 x^{2} & +4 x^{3}+2 x^{4} \\ \quad+3+6 x^{2} & +3 x^{4} \\ \quad+2 & \\ \quad+2 x^{4} \end{array}\right) \text {. } \end{aligned}

通过收集同类项，我们可以得到单变量多项式
1 8 ( 8 + 8 x + 16 x 2 + 8 x 3 + 8 x 4 ) 1 8 8 + 8 x + 16 x 2 + 8 x 3 + 8 x 4 (1)/(8)(quad8+8x+16x^(2)+8x^(3)+8x^(4))\frac{1}{8}\left(\quad 8+8 x+16 x^{2}+8 x^{3}+8 x^{4}\right)
  简化为
1 + x + 2 x 2 + x 3 + x 4 . 1 + x + 2 x 2 + x 3 + x 4 . 1+x+2x^(2)+x^(3)+x^(4).1+x+2 x^{2}+x^{3}+x^{4} .

我们对这个简化的单变量多项式的解释是，有一个轨道没有交叉，一个轨道有一个交叉，两个轨道有两个交叉、

一个轨道有三个交叉点，一个轨道有四个交叉点，这与我们在图 5 中看到的完全一致。也就是说，度数为 r r rr 的项的系数就是权重为 x r x r x^(r)x^{r} 的轨道数，我们设计的权重等于具有 r r rr 交叉的轨道数。

定理 6 正式确定了这种计数技术。其证明涉及伯恩赛德定理 "加权 "版本的推导。

定理 6 假设 π π pi\pi 是 2 × 2 2 × 2 2xx22 \times 2 井字棋盘完全填充配置的排列，并假设
t 1 e 1 t 2 e 2 t 3 e 3 t 4 e 4 t 1 e 1 t 2 e 2 t 3 e 3 t 4 e 4 t_(1)^(e_(1))t_(2)^(e_(2))t_(3)^(e_(3))t_(4)^(e_(4))t_{1}^{e_{1}} t_{2}^{e_{2}} t_{3}^{e_{3}} t_{4}^{e_{4}}

是 π π pi\pi 的循环结构。对于 r = 1 , 2 , 3 , 4 r = 1 , 2 , 3 , 4 r=1,2,3,4r=1,2,3,4 ，用二项式 1 + x r 1 + x r 1+x^(r)1+x^{r} 代替 t r t r t_(r)t_{r} （并收集度数相同的项）。那么，所得多项式中 r r rr 阶项的系数等于权重 x r x r x^(r)x^{r} 的轨道数。

求解 CCCP 借助定理 6，我们可以求解 CCCP。首先，我们回顾例 13，旋转和反射群作用于 3 × 3 3 × 3 3xx33 \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)

如果我们需要知道从 0 到 9 的每种可能的十字交叉数的同位类数，并且在所有其他网格位置上都是 naughts，那么我们可以用 ( 1 + x r ) 1 + x r (1+x^(r))\left(1+x^{r}\right) 代替上述循环指数中变量 t r t r t_(r)t_{r} 的每个实例，然后按照计算 2 × 2 2 × 2 2xx22 \times 2 配置的方法进行计算。

由于 C C C P C C C P CCCPC C C P 将其关注点限制在计算有五个交叉的配置上，因此我们的任务有所减轻。也就是说，我们只需为循环指数的四个项中的每一个项计算 x 5 x 5 x^(5)x^{5} 的系数，当我们用 ( 1 + x r ) 1 + x r (1+x^(r))\left(1+x^{r}\right) 代替该项中变量 t r t r t_(r)t_{r} 的每个实例时，就能计算出 r = 1 , 2 , … , 9 r = 1 , 2 , … , 9 r=1,2,dots,9r=1,2, \ldots, 9 的系数。 下面是这一步的细节。
  学期   代谢    x 5 x 5 x^(5)\mathbf{x}^{\mathbf{5}} 系数   价值
t 1 9 t 1 9 t_(1)^(9)t_{1}^{9} ( 1 + x ) 9 ( 1 + x ) 9 (1+x)^(9)(1+x)^{9} C ( 9 , 5 ) C ( 9 , 5 ) C(9,5)C(9,5) 126
4 t 1 3 t 2 3 4 t 1 3 t 2 3 4t_(1)^(3)t_(2)^(3)4 t_{1}^{3} t_{2}^{3} 4 ( 1 + x ) 3 ( 1 + x 2 ) 3 4 ( 1 + x ) 3 1 + x 2 3 4(1+x)^(3)(1+x^(2))^(3)4(1+x)^{3}\left(1+x^{2}\right)^{3} 4 ( C ( 3 , 1 ) C ( 3 , 2 ) + C ( 3 , 3 ) C ( 3 , 1 ) ) 4 ( C ( 3 , 1 ) C ( 3 , 2 ) + C ( 3 , 3 ) C ( 3 , 1 ) ) 4(C(3,1)C(3,2)+C(3,3)C(3,1))4(C(3,1) C(3,2)+C(3,3) C(3,1)) 48
t 1 t 2 4 t 1 t 2 4 t_(1)t_(2)^(4)t_{1} t_{2}^{4} ( 1 + x ) ( 1 + x 2 ) 4 ( 1 + x ) 1 + x 2 4 (1+x)(1+x^(2))^(4)(1+x)\left(1+x^{2}\right)^{4} C ( 1 , 1 ) C ( 4 , 2 ) C ( 1 , 1 ) C ( 4 , 2 ) C(1,1)C(4,2)C(1,1) C(4,2) 6
2 t 1 t 4 2 2 t 1 t 4 2 2t_(1)t_(4)^(2)2 t_{1} t_{4}^{2} 2 ( 1 + x ) ( 1 + x 4 ) 2 2 ( 1 + x ) 1 + x 4 2 2(1+x)(1+x^(4))^(2)2(1+x)\left(1+x^{4}\right)^{2} 2 C ( 1 , 1 ) C ( 2 , 1 ) 2 C ( 1 , 1 ) C ( 2 , 1 ) 2C(1,1)C(2,1)2 C(1,1) C(2,1) 4
  和 = 1 8 4 = 1 8 4 =184=\mathbf{1 8 4}
term substitution coefficient of x^(5) value t_(1)^(9) (1+x)^(9) C(9,5) 126 4t_(1)^(3)t_(2)^(3) 4(1+x)^(3)(1+x^(2))^(3) 4(C(3,1)C(3,2)+C(3,3)C(3,1)) 48 t_(1)t_(2)^(4) (1+x)(1+x^(2))^(4) C(1,1)C(4,2) 6 2t_(1)t_(4)^(2) 2(1+x)(1+x^(4))^(2) 2C(1,1)C(2,1) 4 sum =184 | term | substitution | coefficient of $\mathbf{x}^{\mathbf{5}}$ | value | | :---: | :---: | :---: | ---: | | $t_{1}^{9}$ | $(1+x)^{9}$ | $C(9,5)$ | 126 | | $4 t_{1}^{3} t_{2}^{3}$ | $4(1+x)^{3}\left(1+x^{2}\right)^{3}$ | $4(C(3,1) C(3,2)+C(3,3) C(3,1))$ | 48 | | $t_{1} t_{2}^{4}$ | $(1+x)\left(1+x^{2}\right)^{4}$ | $C(1,1) C(4,2)$ | 6 | | $2 t_{1} t_{4}^{2}$ | $2(1+x)\left(1+x^{4}\right)^{2}$ | $2 C(1,1) C(2,1)$ | 4 | | | | sum $=\mathbf{1 8 4}$ | |

最右边一列的数值之和是 184。除以 8（即置换组的心数），得到 23，也就是有多少个置换组。

图 6 列出了我们之前承诺的 23 个同余类的完整代表。图 6 提供了 23 个同余类的完整代表列表。

粗体横线用来将这 23 个同位类组织成子集，便于用特殊方法检查其完整性和非重复性。例如，有 9 个类别的整条边都包含十字。
x x x\mathbf{x} x x x\mathbf{x} x x x\mathbf{x}
x x x\mathbf{x} x 0
0 0 0
x x x x x 0 0 0 0| $\mathbf{x}$ | $\mathbf{x}$ | $\mathbf{x}$ | | :---: | :---: | :---: | | $\mathbf{x}$ | x | 0 | | 0 | 0 | 0 |
x x x\mathbf{x} x x x\mathbf{x} x x x\mathbf{x}
x x x\mathbf{x} 0 x x xx
0 0 0
x x x x 0 x 0 0 0| $\mathbf{x}$ | $\mathbf{x}$ | $\mathbf{x}$ | | :---: | :---: | :---: | | $\mathbf{x}$ | 0 | $x$ | | 0 | 0 | 0 |
x x x\mathbf{x} x x x\mathbf{x} x x x\mathbf{x}
x x x\mathbf{x} 0 0
x x xx 0 0
x x x x 0 0 x 0 0| $\mathbf{x}$ | $\mathbf{x}$ | $\mathbf{x}$ | | :---: | :---: | :---: | | $\mathbf{x}$ | 0 | 0 | | $x$ | 0 | 0 |
x x x\mathbf{x} x x x\mathbf{x} x x x\mathbf{x}
x x x\mathbf{x} 0 0
0 x x xx 0
x x x x 0 0 0 x 0| $\mathbf{x}$ | $\mathbf{x}$ | $\mathbf{x}$ | | :---: | :---: | :---: | | $\mathbf{x}$ | 0 | 0 | | 0 | $x$ | 0 |
x x x\mathbf{x} x x x\mathbf{x} x x x\mathbf{x}
x x x\mathbf{x} 0 0
0 0 x x xx
x x x x 0 0 0 0 x| $\mathbf{x}$ | $\mathbf{x}$ | $\mathbf{x}$ | | :---: | :---: | :---: | | $\mathbf{x}$ | 0 | 0 | | 0 | 0 | $x$ |
x x x\mathbf{x} x x x\mathbf{x} x x x\mathbf{x}
0 x x xx 0
x x xx 0 0
x x x 0 x 0 x 0 0| $\mathbf{x}$ | $\mathbf{x}$ | $\mathbf{x}$ | | :---: | :---: | :---: | | 0 | $x$ | 0 | | $x$ | 0 | 0 |
x x x\mathbf{x} x x x\mathbf{x} x x x\mathbf{x}
0 x x xx 0
0 x x xx 0
x x x 0 x 0 0 x 0| $\mathbf{x}$ | $\mathbf{x}$ | $\mathbf{x}$ | | :---: | :---: | :---: | | 0 | $x$ | 0 | | 0 | $x$ | 0 |
x x x\mathbf{x} x x x\mathbf{x} x x x\mathbf{x}
0 0 0
x x xx x x xx 0
x x x 0 0 0 x x 0| $\mathbf{x}$ | $\mathbf{x}$ | $\mathbf{x}$ | | :--- | :--- | :--- | | 0 | 0 | 0 | | $x$ | $x$ | 0 |
x x x\mathbf{x} x x x\mathbf{x} x x x\mathbf{x}
0 0 0
x x xx 0 x x xx
x x x 0 0 0 x 0 x| $\mathbf{x}$ | $\mathbf{x}$ | $\mathbf{x}$ | | :---: | :---: | :---: | | 0 | 0 | 0 | | $x$ | 0 | $x$ |
x x xx x x xx 0
x x x\mathbf{x} x x x\mathbf{x} x x x\mathbf{x}
0 0 0
x x 0 x x x 0 0 0| $x$ | $x$ | 0 | | :---: | :---: | :---: | | $\mathbf{x}$ | $\mathbf{x}$ | $\mathbf{x}$ | | 0 | 0 | 0 |
x x xx 0 x x xx
x x x\mathbf{x} x x x\mathbf{x} x x x\mathbf{x}
0 0 0
x 0 x x x x 0 0 0| $x$ | 0 | $x$ | | :---: | :---: | :---: | | $\mathbf{x}$ | $\mathbf{x}$ | $\mathbf{x}$ | | 0 | 0 | 0 |
x x xx 0 0
x x x\mathbf{x} x x x\mathbf{x} x x x\mathbf{x}
0 x x xx 0
x 0 0 x x x 0 x 0| $x$ | 0 | 0 | | :---: | :---: | :---: | | $\mathbf{x}$ | $\mathbf{x}$ | $\mathbf{x}$ | | 0 | $x$ | 0 |
x x xx 0 0
x x x\mathbf{x} x x x\mathbf{x} x x x\mathbf{x}
0 0 x x xx
x 0 0 x x x 0 0 x| $x$ | 0 | 0 | | :---: | :---: | :---: | | $\mathbf{x}$ | $\mathbf{x}$ | $\mathbf{x}$ | | 0 | 0 | $x$ |
0 x x xx 0
x x x\mathbf{x} x x x\mathbf{x} x x x\mathbf{x}
0 x x xx 0
0 x 0 x x x 0 x 0| 0 | $x$ | 0 | | :---: | :---: | :---: | | $\mathbf{x}$ | $\mathbf{x}$ | $\mathbf{x}$ | | 0 | $x$ | 0 |
x x x\mathbf{x} x x xx 0
0 x x x\mathbf{x} x x xx
0 0 x x x\mathbf{x}
x x 0 0 x x 0 0 x| $\mathbf{x}$ | $x$ | 0 | | :---: | :---: | :---: | | 0 | $\mathbf{x}$ | $x$ | | 0 | 0 | $\mathbf{x}$ |
x x x\mathbf{x} x x xx 0
x x xx x x x\mathbf{x} 0
0 0 x x x\mathbf{x}
x x 0 x x 0 0 0 x| $\mathbf{x}$ | $x$ | 0 | | :---: | :---: | :---: | | $x$ | $\mathbf{x}$ | 0 | | 0 | 0 | $\mathbf{x}$ |
x x x\mathbf{x} x x x\mathbf{x} 0
0 x x x\mathbf{x} 0
x x xx 0 x x x\mathbf{x}
x x 0 0 x 0 x 0 x| $\mathbf{x}$ | $\mathbf{x}$ | 0 | | :---: | :---: | :---: | | 0 | $\mathbf{x}$ | 0 | | $x$ | 0 | $\mathbf{x}$ |
quad\quad
x x x\mathbf{x} 0 x x xx
0 x x x\mathbf{x} 0
x x x\mathbf{x} 0 x x x\mathbf{x}
x 0 x 0 x 0 x 0 x| $\mathbf{x}$ | 0 | $x$ | | :---: | :---: | :---: | | 0 | $\mathbf{x}$ | 0 | | $\mathbf{x}$ | 0 | $\mathbf{x}$ |
x x x\mathbf{x} 0 x x x\mathbf{x}
0 0 x x xx
x x x\mathbf{x} x x xx 0
x 0 x 0 0 x x x 0| $\mathbf{x}$ | 0 | $\mathbf{x}$ | | :---: | :---: | :---: | | 0 | 0 | $x$ | | $\mathbf{x}$ | $x$ | 0 |
x x x\mathbf{x} x x xx 0
x x xx 0 x x xx
0 x x xx 0
x x 0 x 0 x 0 x 0| $\mathbf{x}$ | $x$ | 0 | | :---: | :---: | :---: | | $x$ | 0 | $x$ | | 0 | $x$ | 0 |

图 6.23 种不同的 3 × 3 3 × 3 3xx33 \times 3 井字游戏配置，其中有 5 个十字和 4 个九宫格。

  建议阅读


  1. W.Burnside, Theory of Groups of Finite Order, Second Edition, Dover Publications, Mineola, N.Y., 2004.

  2. F.哈拉里和 E. 帕尔默：《图形枚举》，学术出版社，纽约和伦敦，1973 年。

  3. G. Pólya, "Kombinatorische Anzahlbestimmungen für Gruppen, Graphen, und chemische Verbindungen", Acta Mathematica, Vol. 68, 1937, pp.

  4. J.Redfield, "The theory of group-reduced distributions", American Journal of Mathematics, Vol. 49, 1927, pp.

  练习


  1. 画出一个有两个十字和七个九宫格的 3 × 3 3 × 3 3xx33 \times 3 井字图案，使得全等类的卡片数等于 2。

  2. 用 2 × 9 2 × 9 2xx92 \times 9 矩阵表示图 3 中 3 × 3 3 × 3 3xx33 \times 3 井字棋盘上的四个旋转。

  3. 用 2 × 9 2 × 9 2xx92 \times 9 矩阵表示图 9 中 3 × 3 3 × 3 3xx33 \times 3 井字棋盘上的四个反射。

  4. 使用排列的 2 × n 2 × n 2xx n2 \times n 矩阵表示的组成规则来证明 90 ∘ 90 ∘ 90^(@)90^{\circ} 旋转和 180 ∘ 180 ∘ 180^(@)180^{\circ} 旋转的 2 × 2 2 × 2 2xx22 \times 2 井字棋盘的组成是 270 ∘ 270 ∘ 270^(@)270^{\circ} 旋转。

  5. 使用 2 × n 2 × n 2xx n2 \times n 矩阵表示法说明 90 ∘ 90 ∘ 90^(@)90^{\circ} 旋转 2 × 2 2 × 2 2xx22 \times 2 井字棋盘的倒数是 270 ∘ 270 ∘ 270^(@)270^{\circ} 旋转。

  6. 计算等边三角形旋转和反射组的循环指数。

  7. 计算正五边形旋转和反射组的循环指数。

  8. 计算正六边形旋转和反射组的循环指数。

  9. 在 3 × 3 3 × 3 3xx33 \times 3 井字棋盘上，除了没有填满的中心点外，到处都是十字和九宫格，那么有多少个全等类？

    • 乔治-波利亚（1887-1985 年）是匈牙利数学家，在布达佩斯大学获得概率论博士学位。他曾在瑞士联邦理工学院和布朗大学任教，1942 年到斯坦福大学任职。他在数学的各个领域发表了 250 多篇文章，并撰写了多本关于解决问题的书籍。