动机
一排有颜色的位置有明确的起点和终点。项链忽略起始位置,手链还进一步忽略阅读方向。这些改变会把若干个字等同为同一个对象,但被等同的字的个数并不是常数:单色字的对称性远多于一般的字。
正确的计数方法,是对所有允许的对称变换取固定构形个数的平均。我们要证明这个平均为什么恰好把每个轨道只计一次。旋转的循环结构使固定字易于计数,反射的循环结构处理手链,而最小周期则分离出那些旋转轨道确实达到完整长度的字。
必要的有限群记号会在需要时给出定义。
定义
定义 2.10.1
(群作用、轨道与稳定子)
有限群 具有结合的运算、单位元,且每个元素都有逆元。群 在有限集 上的一个作用,是给每个群元素指定一个置换 ,使得单位元的作用为恒等变换,并且 。
的轨道是 。它的稳定子是 ,而 的不动点集是 。轨道就是在允许指定对称变换时所得的等价类。
长度为 的字,是给以模 为指标的每个位置指定 种颜色之一,其中 , 为非负整数。项链是在 个旋转作用下的一个轨道。对于 ,手链是在由旋转和一个反射生成的 个置换作用下的一个轨道。固定字在位置置换的每个循环上都取常值。
使一个字保持不变的最小正旋转位移称为它的最小周期 。它整除 ,而且该字是长度为 的块的重复。本原字是最小周期为 的字。令 为长度为 的本原字的个数,其中各位置仍然是可区分的。令 表示在 到 中与 互素的剩余类的个数,并规定 。
定理/命题
定理 2.10.2
(由不动点集平均值进行轨道计数)
对于有限群作用,,并且轨道的个数为
无需假设所有轨道大小相等。除以群的阶,针对的是不动点对的总和,而不是单单针对构形的个数。
定理 2.10.3
(项链与手链公式)
长度为 的 色项链的个数为
对于 ,手链的个数为
其中
各种颜色的名称仍然保持可区分;这里没有对颜色作置换后再取商。
定理 2.10.4
(本原周期有莫比乌斯计数)
对每个正整数 ,
这里 是前面已经建立的整除意义下的莫比乌斯(Möbius)函数。每个本原旋转轨道恰有 个字,所以本原项链的个数为 。所有项链(包括由重复块构成的项链)满足 。
证明思路或证明
证明
(轨道—稳定子与不动点对的双重计数)
轨道关系由单位元得自反性,由逆元得对称性,由乘法得传递性。固定一点 ,考虑从 到其轨道的映射,把 送到 。若 ,则 当且仅当 固定 。因此 上方的纤维是 ,大小为 。各纤维大小相等,便得到轨道—稳定子恒等式。
数一数满足 的对 。先对 求和,得到不动点集之和;先对 求和,得到 。在同一个轨道上,由稳定子恒等式,每个点的稳定子大小都等于 除以该轨道的大小,所以这个轨道恰好贡献 。因此,把对的个数除以 ,就得到轨道的个数。
证明透视
先数对称变换—构形对,再作除法
证明以两种次序计算同一个有限集,即不动点对,而全部内容都在第二种次序里。群结构在那里通过轨道—稳定子进入:从 到 的映射,其纤维是稳定子的陪集,所以大小全部相同。因此轨道上每一点的稳定子大小都是群的阶除以轨道大小,不论轨道多大,整个轨道的贡献都是群的阶。对称性很高的字位于较小的轨道,却被更多元素固定;两种效应恰好抵消。这种抵消是吸收轨道大小不等的唯一地方。把字的原始个数直接除以对称变换的个数,就跳过了这一步,所以会失效。
这个论证也说明了,为什么不同的对称变换可以有大小悬殊的不动点集,却不会使平均公式失效。
旋转的循环结构决定固定字
证明
(旋转与反射的循环个数)
旋转 个位置的置换有 个循环。事实上,一个位置的轨道是不断加 (模 ),在 步之后第一次回到原处。这些长度相等的循环把所有位置划分开来。固定字对每个循环独立地选取一种颜色,因此有 个固定字。
把旋转位移按 分组。这样的位移形如 ,其中 取模 且与 互素。这样的选择有 个;当 时包括恒等位移。固定字的个数为 。求和并应用轨道计数定理,就证明了项链公式,而完全不必枚举轨道本身。
对于反射,位置以模 为指标。每个反射都形如 ,其中 取 个值之一。它的不动位置是模 下 的解;其余位置构成相互交换的位置对。
若 为奇数,则乘以二在模 下可逆,所以恰有一个不动位置。每个反射有 个位置循环。若 为偶数且 为偶数,则有两个不动位置,因而有 个循环。若 为奇数,则没有不动位置,因而有 个循环。两种类型各占反射的一半。由此得到的固定字总数恰为 。加上旋转的贡献,再除以群的阶 ,便证明了手链公式。
最小周期为本原划分提供依据
证明
(最小周期、本原块与莫比乌斯反演)
固定某个字的位移集合,在模 下对加法和取负封闭。改把它们看作整数,并包括位移 。设 是其中最小的正元素,把任何其他固定位移除以 。由封闭性,余数仍是固定位移;由最小性,余数只能是零。特别地, 整除 ,并且固定位移恰为 在模 下的倍数。
该字由其前 个位置决定,并重复这些位置,因为位移 固定它。这个块在长度 下是本原的:若块有更小的周期,它就会固定整个字,与最小性矛盾。反之,把任一长度为 的约数 的本原块重复,就得到最小周期恰为 的长度为 的字。若有更小的位移固定这个重复字,它在块上的剩余类作用就会给出块的更小周期。
按这个唯一的约数 对长度为 的所有字分类。对每个这样的约数,块的选择有 个,所以它们的总和为 。应用前面已证明的整除意义下的莫比乌斯反演,便得到本原公式。长度为 的本原字的旋转稳定子是平凡的,所以它的轨道大小为 。更一般地,最小周期为 的字,其轨道大小为 ,这解释了最后一个关于所有项链的求和式。
限制条件必须施加在固定构形上
如果规定每种颜色必须出现的位置个数,同样的轨道计数定理仍然适用,因为旋转保持这些个数。然而,长度为 的置换循环现在会使其所选颜色出现 次。它不加约束时的选择个数,不能脱离总数而独立地沿用。
一个精确的办法,是给颜色 一个变量 。长度为 的位置循环贡献多项式 。把各个循环的因子相乘,再提取所需颜色总数对应的系数。这个系数恰好数出满足限制条件的固定字。然后像前面一样,对群取这些系数的平均。这是有限的多项式计算,不涉及形式收敛问题,也说明了为什么固定内容的项链往往不能简单地把不同的调色板大小代入无限制公式。
例题详解
例题 2.10.5
(长度为四的六条二元项链,轨道大小各不相同)
旋转的固定字个数为:恒等变换十六个,旋转一步两个,旋转两步四个,旋转三步两个。它们的平均值为六。代表元为 。
它们的轨道大小依次为一、一、四、四、四、二,总共十六个字。把十六除以四会得到四,漏掉了对称构形的补偿。对于这个长度的手链,反射的贡献是 ,所以手链的个数同样是六。
例题 2.10.6
(在长度为六时,反转使一对项链合并)
对于长度为六的二元字,旋转之和为 ,得到十四条项链。反射的贡献合计为 ,得到十三条手链。
以 和 为代表的项链是不同的旋转轨道,但它们经反转和一次旋转而相互联系。因此它们成为同一条手链。总数表明,恰有一对这样的项链轨道被合并;所有其他项链轨道在手链中仍各自保持为单独的轨道。
把旋转后的单词反向读取,只会得到原单词反向读取后的另一个旋转。因此反向在项链等价类上有良好定义,且做两次回到原类。它只会固定一个类或交换两个类,所以十四个项链类变为十三个手链类时,恰好合并了一对。
例题 2.10.7
(本原二元字与重复项链可以清楚分开)
对于长度为六,莫比乌斯反演给出 。除以六,得到九条本原项链。其余的项链,最小周期为一、二或三。
在这些长度下,本原字的个数分别为二、二和六。它们对项链的贡献分别为二、一和二,合计五。把这五条重复项链与九条本原项链相加,便还原出十四。若把长度为六的所有字都除以六,恰恰会在这些较短的轨道上出错。
概念视角组合
对称性改变等价关系,而周期衡量其稳定子
字、项链和手链有相同的底层有色位置,但对“相等”的理解不同。最小周期控制旋转轨道的大小,而反射可以把两个不同的旋转轨道合并。在商的计数有确定含义之前,必须先指明所用的群以及允许的颜色限制。
常见错误
反例模式
构形的个数不一定能被对称群的阶整除
长度为六的二元字有六十四个,而手链的群有十二个元素。它们的商甚至不是整数,而正确的手链个数是十三。这个群并非自由作用:对称的字具有非平凡的稳定子。只有证明了作用是自由的,才可以把原始构形个数除以整个群的阶。
反射公式只对长度至少为三的情形陈述,这样通常的多边形对称变换才恰好给出所述的群。
常见错误
(本原字不是本原项链)
计数的是位置有区别的字;每条本原项链恰好包含其中 个。二元长度六时有 个本原字,但只有 条本原项链。把 当作项链个数,或把非本原的个数除以 ,都混淆了两个层次。
常见错误
(没有颜色作用却等同颜色名称)
这些公式保留颜色名称的区别: 与 是不同的二元项链。把它们视为相同是另一个问题,需要再加一个置换颜色的作用,并另行计算轨道。
总结
轨道—稳定子计数使平均不动点集公式即使在轨道大小不一时也是精确的。旋转与反射的循环结构给出项链与手链的个数。最小周期整除长度,并给出本原字的莫比乌斯反演;而固定内容的限制,则在取平均之前通过循环权重的系数来施加。
练习
快速检查
(计算长度为三的三色项链与手链的个数,并计算本原项链的个数。)
使用三个旋转和三个反射,并保持各颜色名称可区分。
解答
旋转之和为 ,所以有十一条项链。每个反射有两个位置循环,固定九个字;加上它们的贡献,得到手链个数 。
在素数长度三下,只有常值字的周期更短。因此 ,本原项链的个数为八。其余三条项链是单色的项链。
快速检查
(计算长度为四、且每种颜色恰好出现在两个位置上的二元项链的个数。请计算固定字的个数,而不要使用无限制调色板的公式。)
考察半圈旋转,并注意哪些旋转能保持所要求的总数。
解答
恒等变换固定所有 个允许的字。旋转一步或三步只固定常值字,而常值字中没有一个满足每种颜色各占两个位置。半圈旋转有两个含两个位置的循环;给它们指定不同的颜色,得到两个固定字。平均值为 。
代表元为 和 。前者的轨道大小为四,后者为二,合起来恰好包含全部六个字。内容限制既作用于颜色的选择,也作用于循环的长度。
快速检查
(对于素数长度 和非负整数 ,用组合方法证明 整除 。)
把常值字与本原字分开,并利用它们的轨道大小。
解答 · 答案
最小周期整除素数长度 ,所以它要么是一,要么是 。周期为一的字恰为 个常值字。其余每个字都是本原的,属于大小为 的旋转轨道。因此 是 的倍数。当颜色数为零或一时,同样的结论成立,只是相应的集合为空或全是常值字;证明中没有用到除以零的构形个数。