伯恩赛德引理是群论和组合数学中用于计算对称意义下不同对象数量的定理。它指出,有限群作用于有限集时,轨道数等于各群元素在该集合中的不动点数的平均值。借助这个引理,原本可能很难完成的对称等价类划分问题,可以转化为一系列不动点计数问题。
定理表述
设有限群 G 作用于有限集 X。对每个 g∈G,定义其不动点集为
FixX(g)={x∈X:g⋅x=x}.
元素 x∈X 的轨道为
G⋅x={g⋅x:g∈G}.
若存在某个群元素将一个元素变为另一个元素,就称这两个元素等价;轨道正是这一关系下的等价类。用 X/G 表示轨道的集合,用竖线表示有限集的基数。
伯恩赛德引理断言:
∣X/G∣=∣G∣1g∈G∑∣FixX(g)∣.
因此,尽管不同群元素的不动点数可能相差很大,其平均值却总是一个非负整数。
在计数问题中,X 通常是带标号构型的集合,而 G 由计数时不予区分的对称变换组成。此时,每条轨道就代表一个“在对称意义下相同”的构型类别。
双重计数证明
考虑集合
S={(g,x)∈G×X:g⋅x=x}.
先按群元素这一坐标对这些有序对计数,得到
∣S∣=g∈G∑∣FixX(g)∣.
对每个 x∈X,其稳定子是子群
Gx={g∈G:g⋅x=x}.
再按集合元素这一坐标对同一批有序对计数,得到
∣S∣=x∈X∑∣Gx∣.
根据轨道稳定子定理,
∣G⋅x∣∣Gx∣=∣G∣.
因此,对任意轨道 O,每个 x∈O 的稳定子大小均为 ∣G∣/∣O∣,从而
x∈O∑∣Gx∣=∣O∣∣O∣∣G∣=∣G∣.
所以,每条轨道对总和的贡献恰好都是 ∣G∣。于是
g∈G∑∣FixX(g)∣=∣G∣∣X/G∣,
公式得证。
这一论证也解释了为什么直接用 ∣X∣ 除以 ∣G∣ 通常行不通:对象具有的对称性不同,所在轨道的大小也就可能不同。
示例:正方形顶点染色
设正方形的每个顶点都染成黑色或白色。在尚未将对称的染色视为相同之前,共有 24=16 种染色。
只考虑旋转
取 G 为正方形的四个旋转变换组成的群。
| 旋转角度 |
染色保持不变的条件 |
不变染色数 |
| 0∘ |
无限制 |
16 |
| 90∘ |
四个顶点颜色相同 |
2 |
| 180∘ |
相对顶点颜色相同 |
4 |
| 270∘ |
四个顶点颜色相同 |
2 |
由伯恩赛德引理,不计旋转差异时的染色数为
416+2+4+2=6
这六类的代表分别是:全白、全黑、只有一个黑色顶点、只有一个白色顶点、两个相邻顶点为黑色,以及两个相对顶点为黑色。
同时考虑旋转与反射
若还将互为镜像的染色视为相同,则作用群为正方形的二面体群,其阶为八。
此时增加了四个对称变换:
- 沿两条对角线的反射,共两个。每个反射固定两个顶点,并交换另外两个顶点,因此各自保持 23=8 种染色不变。
- 沿两条对边中点连线的反射,共两个。每个反射交换两对顶点,因此各自保持 22=4 种染色不变。
等价类数变为
816+2+4+2+2(8)+2(4)=6.
这一结果与只考虑旋转时相同,是本例的特殊性质:正方形的任意二色染色经过反射后,总能通过旋转回到原来的染色。若可用的颜色有三种,则只考虑旋转时有 24 类,同时考虑旋转与反射时有 21 类。
利用置换的循环计算染色数
一种常见应用是从有限位置集 P 及其上的群 G 的作用出发。使用 q 种可区分颜色的染色是一个函数
f:P⟶{1,…,q}.
群在染色上的作用定义为
(g⋅f)(p)=f(g−1⋅p).
每个群元素都在 P 上诱导一个置换。若该置换有 c(g) 个循环,其中也计入长度为一的循环,那么一种染色保持不变,当且仅当每个循环内的颜色相同。每个循环都可以独立选用 q 种颜色中的任意一种,因此
∣Fix(g)∣=qc(g).
于是
number of coloring classes=∣G∣1g∈G∑qc(g).
例如,考虑沿圆周排列的 n 个位置,将可通过旋转重合的染色视为相同,但不将仅通过反射重合的染色视为相同。旋转 k 个位置所对应的置换有 gcd(n,k) 个循环,其中 gcd 表示最大公约数。因此,这类项链的数量为
N(n,q)=n1k=0∑n−1qgcd(n,k),
其中 gcd(n,0)=n。
这一计数包含所有项链,也包括颜色图案的重复周期小于 n 的项链。
与波利亚计数的关系
伯恩赛德引理是波利亚计数定理的基础,后者能够记录更详细的染色信息。
若 ai(g) 表示 g 诱导的置换中长度为 i 的循环个数,则该作用的循环指标是如下多项式:
ZG(s1,s2,…)=∣G∣1g∈G∑i≥1∏siai(g).
当位置集有限时,乘积中只有有限多个非平凡因子。
对每个 i 代入 si=q,即可得到通常的染色计数。采用包含更多信息的代入方式,则可得到记录每种颜色所占位置数的生成函数。若用变量 x1,…,xq 表示各颜色,作代入
si=x1i+⋯+xqi
后,所得多项式的系数便给出各颜色出现次数指定时的对称等价类数。
概率与线性代数解释
若从 G 中均匀随机选取 g,则伯恩赛德引理可用期望值写成
∣X/G∣=E[∣FixX(g)∣].
这里取平均的对象是群元素,而不是集合中的对象或轨道。
它也有表示论上的解释。构造以 {ex:x∈X} 为基的实向量空间。每个群元素通过置换矩阵 ρ(g) 作用,其矩阵的迹为
trρ(g)=∣FixX(g)∣.
平均算子
P=∣G∣1g∈G∑ρ(g)
是到不变向量子空间的投影。将每条轨道对应的基向量相加,就得到该子空间的一组基,其中每条轨道对应一个基向量。因此,该子空间的维数,也就是 P 的迹,等于 ∣X/G∣。两边取迹便得到伯恩赛德公式。
应用与局限
该引理可用于计数项链、手链、多边形和多面体上的排列、无标号结构,以及描述中含有冗余标号的其他构型。例如,在图论中,顶点集上的对称群通过重新标记顶点作用于带标号图,其轨道就是图的同构类。
正确应用这一引理,需要明确规定计数对象及允许的对称变换:
- 旋转与反射对应不同的等价关系。 只有当计数问题确实将某种变换联系起来的构型视为相同时,才应将该变换纳入考虑。
- 置换位置并不自动意味着置换颜色。 若还要将颜色名称的差异忽略,就需要引入额外的作用。
- 群作用必须保持约束条件。 若只允许满足某种限制的构型,则所选群必须将合法构型映为合法构型。
- 主要计算工作仍是不动点计数。 求平均很简单,但确定某个对称变换保持哪些对象不变,可能相当困难。
若群作用是自由的,即只有单位元能够固定集合中的元素,则公式化为
∣X/G∣=∣G∣∣X∣.
在其他情形中,非平凡稳定子的存在使这一直接相除的规则失效,而一般形式的引理则将这些稳定子纳入了计算。
标准的数值公式假定 G 和 X 都是有限的。对于无限群或无限集上的作用,需要附加条件或采用其他表述;不能原封不动地套用通常的有限平均公式。
历史归属
该引理以威廉·伯恩赛德命名,他在1897年出版的《有限阶群论》中收录了这一结果。不过,这一结果早于该书问世,已见于奥古斯丁-路易·柯西和费迪南德·格奥尔格·弗罗贝尼乌斯的研究。别名柯西–弗罗贝尼乌斯引理反映了这段更早的历史,而轨道计数引理则描述了它的数学内容。