伯恩赛德引理

琉璃幻

设$G$是个$n$阶群有元素$g_1,g_2,g_3,\cdots g_n$, 且$G$作用于集合$S$
\[G(s)=\{g\circ s|\, s\in S,\forall g\in G \}\]
\[r=\left|\{{t\, |\, G(t_i)\cap G(t_j)=\varnothing}\}\right|\]
\[X(g)=\{s\,|\, g\circ s=s,\, s\in S\}\]


则
\[rn=\sum_{i=1}^{n}\left|X(g_{i})\right|\]

琉璃幻

没人鸟我！@kuing

kuing

@我也没用啊，我连题都看不懂……

琉璃幻

回复 3# kuing


    至少给个赞什么的吧! (装b中...

Tesla35

回复 4# 琉璃幻
赞个jb赞

hbghlyj

Tesla35 发表于 2014-10-16 11:14
回复 4# 琉璃幻
赞个jb赞

Burnside 引理

对于群 $G$ 在集合 $X$ 上的作用，轨道的个数等于群中每个元素对应置换的不动点的平均个数，即
$$
|X/G| = \frac{1}{|G|}\sum_{g\in G}|X^g|.
$$
这里，$X^g=\{x\in X:gx=x\}$ 是元素 $g\in G$ 对应置换的不动点集合。

证明

这一定理的证明十分简明。注意到，轨道个数可以写作
$$
|X/G|=\sum_{o\in X/G}1=\sum_{x\in X}\frac{1}{|Gx|}=\frac1{|G|}\sum_{x\in X}|G_x|.
$$
最后一个等号就是上面的推论；而右式和所要求证的只差一个 Fubini 定理，因为它们中的求和式都是对集合 $\{(g,x)\in G\times X:gx=x\}$ 的计数，只不过右式先对 $g$ 求和，而所求证的式子先对 $x$ 求和。

这一定理在组合数学中有很多用处，可以用于统计「本质不同」的对象的数目。更多例子和讨论可以参考Pólya 计数。

hbghlyj

考虑简单的例子。

项链染色
现在有一串共四个珠子的项链，每个珠子可以是红色或者蓝色，计算共有几种本质不同的珠子。（如果两种染色的结果可以通过旋转项链重合，就认为是相同的。)

解答和分析
这个问题足够简单，可以通过枚举的方式加以解答。珠子共计 $4$ 个，每个珠子可以染 $2$ 种颜色，所以，项链所有可能的染色方案共计 $2^4=16$ 种。将可以通过旋转相互得到的分到一组，共计 $6$ 组，如下图所示。（其中，单个染色方案的编码表示了自左下角的珠子开始顺时针染的颜色，$B$ 表示蓝色，$R$ 表示红色；分到同一组的染色方案的编码有着相同的背景颜色。）

从这个例子中可以看到，要计算本质不同的染色的种类数，关键其实是知道每种本质相同的染色对应几种不同的染色方案。也就是说，要搞清楚上图中每个分组的大小。

能够分到同一个组中的染色方案，就是指它们之间能够通过旋转操作互相转化的染色方案。总共有 $4$ 种旋转的方式，即
$$
G=\{r_0,r_1,r_2,r_3\},
$$
分别表示旋转 $0,1,2,3$ 次。旋转 $0$ 次就是原地不动。

首先看染色方案 $RRBB$ 所在的分组。对它施加这四种操作，将分别得到
$$
RRBB, RBBR, BBRR, BRRB.
$$
四种染色方案互不相同，因此这个组就有 $4$ 个元素。

再看染色方案 $BRBR$ 所在的分组。对它同样施加这四种操作，将分别得到
$$
BRBR, RBRB, BRBR, RBRB.
$$
此时，旋转两次的结果和不旋转的结果是一致的，旋转三次和旋转一次的结果是一致的。所以，这个组就有 $2$ 个元素。

如果看染色方案 $BBBB$ 和 $RRRR$ 所在的分组。对它们施加四种操作得到的结果都是它们自身。因而，每个组就只有 $1$ 个元素。

如果用 $x$ 表示染色方案，$Gx$ 表示对染色方案 $x$ 操作后能够得到的颜色编码的集合，那么从上面的例子可以总结出一个规律，那就是 $G$ 的操作对于 $x$ 的影响存在某种「周期性」。

设 $|G|$ 表示操作的总个数，这种影响的「周期性」意味着，如果有 $m$ 个不同的 $G$ 中的操作将染色方案 $x$ 变换到它自身，那么 $x$ 在这些操作下的结果就会重复出现 $m$ 次。因而，染色方案 $x$ 在这些操作下共计有 $|G|/m$ 种不同的结果，这也就是 $x$ 所在分组的大小。

这个例子中，因为只有旋转零次 $r_0$ 才能够将 $RRBB$ 变换到它自身，所以，它所在分组的大小等于 $4/1=4$；而旋转零次 $r_0$ 和两次 $r_2$ 都能将 $BRBR$ 变换到它自身，所以，它所在分组的大小等于 $4/2=2$；无论旋转几次都能将 $BBBB$ 变换到它自身，所以，它所在分组的大小就是 $4/4=1$。

在下面的叙述中，用 $G_x$ 表示能够将 $x$ 变换到它自身的操作的数目，所以，$|G_x|$ 就是上面的 $m$。此时，$X$ 所在分组大小是 $|G|/|G_x|$。要计算染色方案的分组的数目，只需要穷举所有可能的染色方案 $x\in X$，对所在分组大小为 $|Gx|$ 的染色方案 $x$ 赋以权重 $1/|Gx|$，就能够将分组的数目表达为
$$
|X/G|=\sum_{x\in X}\frac{1}{|Gx|}=\sum_{x\in X}\frac{|G_x|}{|G|}.
$$
现在这个式子的形式并不便于应用。记 $gx$ 是对染色方案 $x\in X$ 应用操作 $g\in G$ 的结果，那么上面描述的集合 $G_x$ 就是 $\{g\in G:gx=x\}$，所以交换求和顺序就有
$$
\begin{aligned}
\sum_{x\in X}|G_x|
&=\sum_{x\in X}|\{g\in G:gx=x\}|\\
&=\sum_{x\in X}\sum_{g\in G}[gx=x]\\
&=\sum_{g\in G}\sum_{x\in X}[gx=x]\\
&=\sum_{g\in G}|\{x\in X:gx=x\}|\\
&=\sum_{g\in G}|X^g|.
\end{aligned}
$$
这里，$[\cdot]$ 称为 Iverson 括号，只有当命题 $P$ 为真时 $[P]$ 取值为 $1$，否则取 $0$。交换求和记号的结果中，$X^g=\{x\in X:gx=x\}$ 是指在操作 $g$ 下保持不变的染色方案 $x$ 的集合。简言之，它是操作 $g$ 的不动点。

在这些讨论之后，现在可以将分组的个数写作
$$
|X/G|=\frac{1}{|G|}\sum_{g\in G}|X^g|.
$$
也就是说，分组的个数是各种旋转操作的不动点的平均个数。

作为这个结果的应用，再次计算项链染色的个数。这些旋转操作的不动点可以列举如下。

操作	不动点
$$r_0$$	$$X$$
$$r_1$$	$$\{BBBB,RRRR\}$$
$$r_2$$	$$\{BBBB,BRBR,RBRB,RRRR\}$$
$$r_3$$	$$\{BBBB,RRRR\}$$

因而，分组的个数就等于
$$
\frac{16+2+4+2}{4} = 6.
$$
这样就得到了前面的结果。

hbghlyj

Burnside 引理介绍详见此帖八楼附件, 亦包括项链数目计数公式.

考虑下列计数问题： $n$ 颗柱子串成一圈项链，每颗可选 $r$ 种颜色，若视翻转与旋转后相同的两条项链为同类的，试问一共可生成几类项链？

设 $n=6 、 r=4$ ，项链类数减一即卤代苯（氟氯溴碘代苯，不考虑存在性及非常规的异构现象）的种数。
自然的想法是将同类的所有项链视为等价类。将 $n$ 颗珠子串成的项链视为正 $n$ 边型，我们自然地引入集正 $n$ 边型所有旋转和翻转的变换的群 $D_{n}$ :

上图的多边形的不变变换包括：旋转 $2 \pi / n$ 的变换，记变换为 $a$ ；沿 $x$ 轴翻转，记变换为 $b$ 。则所有变换可由 $a$ 与 $b$ 生成，易知变换构成群。记变换群 $D_{n}:=\langle a, b\rangle$ 。
$D_{n}$ 中元素满足： $a^{n}=\mathrm{e}, b^{2}=e,(a b)^{2}=e$ 。这里 $e$ 是单位元。可用半直积对群结构做更清晰的阐述，即
$$
D_{n} \cong \mathbb{Z}_{n} \rtimes_{\varphi} \mathbb{Z}_{2}
$$
形式上， $D_{n}$ 元素为 $\mathbb{Z}_{n}$ 与 $\mathbb{Z}_{2}$ 的笛卡尔积，前者同构于旋转变换而后者同构于翻转。乘积上， $\forall(g, h),\left(g^{\prime}, h^{\prime}\right) \in \mathbb{Z}_{n} \times \mathbb{Z}_{2}$
$$
(g, h)\left(g^{\prime}, h^{\prime}\right):=\left(g \varphi_{h}\left(g^{\prime}\right), h h^{\prime}\right)
$$
这里设 $\mathbb{Z}_{2}=\left\{0_{2}, 1_{2}\right\}$ ，则 $\varphi_{1_{2}}: g \mapsto-g, \varphi_{0_{2}}: g \mapsto g$ 。容易验证半直积构成的群于其上的乘法是良定义的。


回到项链，视 $\Omega$ 为同类合并前的所有项链种数，将变换 $D_{n}$ 作用在 $\Omega$ 的所有元素上即为合并操作，记 $D_{n} \curvearrowright \Omega$ 为群 $D_{n}$ 在 $\Omega$ 上的作用。合并后的项链类数是集合
$$
\left\{D_{n} \omega: \omega \in \Omega\right\}
$$
中的元素个数。一般称 $D_{n} \omega$ 为 $\omega$ 的 $D_{n}$-轨道，我们只需求所有轨道条数。
Burnside引理是指：设群 $G$ 作用在集合 $\Omega$ 上，记 $F(g)$ 为 $\Omega$ 中 $g$ 的不动点个数，即 $|\{\omega: g \omega=\omega\}|$ 。设 $t$ 为轨道的数量，则
$$
t=\frac{1}{|G|} \sum_{g \in G} F(g)
$$
证明比较容易，我们只需通过两种方式计算 $(G, \Omega)$ 中不动点对的数量 $\Gamma$ ，即所有满足 $g \omega=\omega$ 的 $(g, \omega)$ 组数：
1. 若固定 $\Omega$ ，考虑每个 $g \in G$ ，则 $\Gamma=\sum_{g \in G} F(g)$ 。
2. 若固定 $G$, 考虑每个 $\omega \in \Omega$, 我们记 $G_{\omega}:=\{g \in G: g \omega=\omega\}$ 。有如下引理：对任意 $x, y \in \Omega, G x \neq G y \Leftrightarrow G x \cap G y=\emptyset$ 。只证明必要性：不然，设 $z \in G x \cap G y$ ，则 $\exists g_{0} \in G$ 使得 $g_{0} z=x$, 故 $G x=G y$ 矛盾。因此 $\Omega$ 可看作若干 $G \omega_{i}$ 的无交并, $1 \leq i \leq t$。
考虑映射
$$
\pi: G x \rightarrow G / G_{x}, g x \mapsto g G_{x}
$$
易知 $\pi$ 是双射，因此 $|G x|=|G| /\left|G_{x}\right|$ 。
$$
\Gamma=\sum_{\omega \in \Omega}\left|G_{\omega}\right|=\sum_{\omega \in \Omega} \frac{|G|}{|G \omega|}=\sum_{i=1}^{t} \sum_{\omega \in G \omega_{i}} \frac{|G|}{\left|G \omega_{i}\right|}=t|G|
$$
综上，Burnside引理： $t=\frac{1}{|G|} \sum_{g \in G} F(g)$ 得证。Burnside引理的核心内涵已在证明中体现，即通过两种不同的方式等价地计算不动点对的组数。


回归项链问题，我们将题目数学化地阐述：
将 $B=\{1,2, \ldots, n\}$ 视作珠子集合， $C=\left\{c_{1}, c_{2}, \ldots, c_{r}\right\}$ 视作颜色集合。取 $y_{i} \in C$ 为第 $i$ 颗珠子的颜色，将一串项链看作一个 $B$ 到 $C$ 的映射（每颗珠子赋值一种颜色）。记
$\Omega:=C^{B}:\{f: f: B \rightarrow C\}$ 。
回顾前文，我们需要利用二面体群 $D_{n}$ 在 $\Omega$ 上的作用以计数项链的类，首先需要定义 $\alpha \in D_{n}$ 与 $f \in \Omega$ 的乘法。视 $\alpha$ 为置换关系，则
$$
\alpha \times f=\left(\begin{array}{cccc}
1 & 2 & \cdots & n \\
i_{1} & i_{2} & \cdots & i_{n}
\end{array}\right)\left(\begin{array}{cccc}
1 & 2 & \cdots & n \\
y_{1} & y_{2} & \cdots & y_{n}
\end{array}\right)=\left(\begin{array}{cccc}
i_{1} & i_{2} & \cdots & i_{n} \\
y_{1} & y_{2} & \cdots & y_{n}
\end{array}\right)
$$
注意到项链类数即轨道条数，根据Burnside引理，只需求 $\frac{1}{\left|D_{n}\right|} \sum_{\alpha \in D_{n}} F(\alpha)$ 。
$\alpha \times f=f$ 当且仅当将 $\boldsymbol{\alpha}$ 写成轮换形式后，每组轮换因子序标对应的 $y_{i}$ 相同。一条重要的定理是：任意置换写成两两不交轮换的形式是唯一的。我们设 $\alpha$ 的轮换形式种长度为 $i$ 的轮换有 $m_{i}$种，故 $F(\alpha)=r^{m_{1}+m_{2}+\cdots m_{n}}$ 。 $D_{n}$ 中元素一定能写为 $a^{p} b^{q}$ 形式，其中 $0 \leq p \leq n-1$ ， $q=0,1$ 。下计算每个 $a^{p} b^{q}$ 对应的不交轮换形式:
$a^{i}=(12 \cdots n)^{i}$ 。任意元素轮换 $\frac{n}{\operatorname{gcd}(i, n)}$ 次后总能回到原位，故每个轮换包含了 $\frac{n}{\operatorname{gcd}(i, n)}$个元素，共 $\operatorname{gcd}(i, n)$ 个 $\frac{n}{\operatorname{gcd}(i, n)}$-轮换。 $F(\alpha)=\sum_{i=0}^{n-1} r^{\operatorname{gcd}(i, n)}$ 。
$n$ 为奇数时，经变化 $a^{i} b$ 后的正 $n$ 边形有且仅有一个不动点。根据对称性， $\alpha$ 可由 $\frac{n-1}{2}$ 个对换 （ 2 -轮换）和一个不动点（ 1 -轮换）组成。 $F(\alpha)=r^{(n+1) / 2}$ 。
$n$ 为偶数时，当 $i$ 取遍 0 至 $n-1$ ，有一半的变化由 $\frac{n}{2}$ 个对换组成，一半的变化由 $\frac{n}{2}-1$ 个对换和两个不动点组成。 $F(\alpha)$ 分别为 $r^{n / 2}$ 与 $r^{(n+2) / 2}$ 。
综上， $n$ 颗柱子串成一圈项链，每颗可选 $r$ 种颜色，项链类数共计
$$
t=\frac{1}{2 n} \sum_{i=0}^{n-1} r^{\operatorname{gcd}(n, i)}+ \begin{cases}\frac{1}{2} r^{(n+1) / 2} & n \text { 为奇数, } \\ \frac{1}{4}\left(r^{n / 2}+r^{(n+2) / 2}\right) & n \text { 为偶数. }\end{cases}
$$
应用：卤代苯一共有几种？
解：即令 $n=6, r=4$。
$$
t=\frac{1}{12}(4096+4+16+64+16+4)+\frac{1}{4}(64+256)=430
$$
故共有 429 种卤代苯。