给定一个集合和集合上的二元运算,满足

  1. 封闭性:
  2. 结合律:
  3. 单位元:
  4. 逆元:,记

在运算下是一个群。如整数加法群。

置换

排列。

个元素之间的一个置换

表示取代,可以表示为

置换群

置换是集合的元素,运算的置换的连接。对于两个置换,他们的连接可以理解为

Burnside 引理

下面我们介绍 Pólya 计数法所要用到的一个引理——Burnside 定理

所谓置换群,指的是我们将某个方案作用置换群的任意置换后的方案是等价的,问本质不同的方案数。

表示在置换作用下不变的方案的个数。表示本质不同的方案数。表示置换群的个数,即置换群的大小。

SGU294 He’s Circles

有一个长度为 N 的环,上面写着XE,问本质不同的环有多少种。

显然,这道题的环指

构成的置换群。(0 当成 n)。把置换理解为若干个环的话,你发现这个置换的环数恰好为。如果方案中一个环上的颜色相同的话,那么作用这个置换后方案是不会变的。而总共有两种颜色,于是。这样就可以统计了。

由此我们引出 Polya 计数原理。

Polya 计数法

设 G 是 p 个对象的一个置换群,用 m 种颜色涂染 p 个对象,则不同染色方案为:

其中为置换的环数。

BZOJ1004 HNOI2008 Cards

考虑 Burnside 引理。对于一个置换不变的方案显然在它的一个环是同色的。因对于一个置换处理出环长后,我们做一个三维背包求方案数即可。

注意,题目给的并不是一个完整的置换群,它少了一个恒等置换。

代码

BZOJ1478 Isomorphism

给定一个 N 个结点的无向完全图( 任意两个结点之间有一条边), 现在你可以用 M 种颜色对这个图的每条边进行染色,每条边必须染一种颜色。 若两个已染色的图,其中一个图可以通过结点重新编号而与另一个图完全相同, 就称这两个染色方案相同。现在问你有多少种本质不同的染色方法,输出结果 mod P。P 是一个大于 N 的质数。

考虑 Polya 计算法,则我们要求的就是边的置换的环数。考虑将边的置换分类。

这题的置换群对点而言是一个全排列,但对于边而言就不是了。对于两个点,他们的置换为,则边的置换为

考虑将点的置换分类,那么每个置换可以由个大小分别为的环表示。

对于两个点,如果他们分别在长度为的环上,那么考虑边的置换的环数。这样的边总共有个,而每个环的长度为,则环的个数为

如果这两个点都在长度为的同一个环上,那么这样的边总共有个。

  1. 如果是奇数,则每个环长度为,则环的个数为
  2. 如果是偶数,那么当时环长为,其他时候环长为。则环的个数为

综上,形如的点置换对应的边置换的环数为

然后我们要求的就是形如的点置换的个数,我们规定

首先考虑多项式定理,则把个点分到大小分别为的集合的方案数是。而每个集合内的元素构成一个环,方案数是(圆排列),于是乘上一个。再考虑到,长度相同的环我们是不计他们之间的顺序的,因此设长度为的环有个,则还得除掉一个表示长度本质不同的环的个数。整理一下得到

根据 Polya 原理,这部分的贡献为

最后,我们怎么枚举形如的置换?置换的数量是的拆分数,时大概是级别的,因此直接 DFS 枚举即可。

代码

联赛特训 7B

对一个长度为的项链黑白染色,并且规定旋转、翻转、反色等操作后的方案等价。问本质不同方案数。

答案对取模。

这道题集合了许多 Burnside 题的技巧和难点。题目本身也有很多理解方式。

一个基础的知识点是旋转和翻转构成的置换群大小是。我们把反色也可以当成一种置换。容易发现这种特殊的置换是满足群的性质的。这样反色、翻转、旋转置换群大小是的。考虑 Burnside 定理。

  1. 旋转不反色。显然贡献是
  2. 翻转不反色。这时要分奇偶考虑。是偶数,则贡献为;否则是奇数,则贡献为
  3. 旋转并强制反色,则我们环上是交替填色的,环长是偶数。因此贡献是
  4. 翻转并强制反色。则环长必须是偶数(2),则是偶数时才有贡献:

于是总的贡献是

这里使用了的一个小技巧。由于置换群的大小是,因此答案为

最后计算的时候要注意的情况。这时在模意义下就没有逆元了。我们把平方,然后在模意义下求出分子。由于在非模意义下分子是的倍数,而。因此在模意义下分子是的倍数。于是我们直接分子分母模数同时除以变回)。由于,因此。则现在分母就有逆元了,可以直接算了。

参考文献

[1] 陈瑜希,Pólya 计数法的应用