Polya计数

引入

给定一串个珠子组成的环链，每个珠子可以被染成黑白两色，求本质不同的染色方案的个数？

群，置换和置换群

群的不严谨定义

如果我们对于一个集合定义一种运算 ，该运算满足以下性质：

1. 封闭性：
2. 结合律：
3. 单位元：
4. 逆元：

则称一起构成了一个群。

置换的概念

我们抽象并拓展“变换”这个概念，定义集合的一个双射为一个置换，举个例子：

这个置换表示将将集合中的变成，变成，变成，变成。

置换群

稍微想一想可知，置换是可以成群的，称为置换群，对于这个置换群我们定义的运算就是置换的复合，对于这个运算我们考察其是否满足群的性质：

1. 封闭性：大部分情况下应该是成立的
2. 结合律：显然
3. 单位元：
4. 逆元：置换是集合到集合的双射，显然

置换群的引入允许我们使用群论来处理一开始的问题，说抽象了我们刚才的问题就是：求一个序列的集合，在一个置换群作用下本质不同的元素个数。

Burnside引理

序列集合在置换群的作用下不同的序列数等于不动点的平均数：

其中表示在置换作用下不动点的集合，何为不动点呢？

例如对于置换而言，序列就是它的一个不动点，因为它在置换后还是原来的样子。

我们接下来考察对于给定置换如何数出不动点的数目，从例子入手，比如说我们要求的是置换,的不动点数目，我们挨个考虑这样的序列拥有什么样的性质：

1. 第一位与第四位相同
2. 第二位与第三位相同
3. 第三位与第二位相同
4. 第四位与第一位相同

显然我们最后得到了一个集合，其中的每一个集合中的元素必须相等，考虑染色问题，对于每一组“相等”，我们可以把它整个染成两种颜色，因此这个置换共有个不动点。

由于等号的传递性，如果我们逐位查看一个置换，把上下的两位并入同一个“相等集合”，那么最后我们一定会得到若干个这样的相等集合，每个“相等集合”都可以被独立地染成不同的颜色，由乘法定理，我们就得到了——

Polya定理

其中是颜色个数，是置换形成的“循环数”，一个“循环”是指某一位经过不断地置换之后最后回到自身。可以看到Polya定理其实就是我们上面的推论，不需要更多解释。

循环同构序列计数

终于进入了我们的正题，循环同构序列计数，到这一步我们终于可以解答一开始的问题了：

Polya定理的精髓就在于求出一个置换的循环数，而朴素的枚举显然是不够的，我们考察所谓“循环同构”背后依赖的哪些置换，比如说对于一个长度为的序列，以下置换后它与自身是循环同构的：

我们发现一个循环同构的置换就是把它的后面全部移到前面来，前面几位补到后面去。

为了接下来的推导方便我们让位数起始于。

那么，对于一个偏移了的置换，第位被置换之后就到了的位置，其中为序列长度，而对于一个长度为的完整循环来说，它必须满足：

显然当的时候有最小值。由于每一位都偏移了位，因此置换中每个循环的长度都是相等的，而因为每个循环都cover了个元素，因此循环的个数为：

这个发现让我们免于枚举每个循环置换，相反，我们枚举的每一个取值，即的因数，统计出的所有的个数，依Polya定理统一累加到答案上。

那怎么统计呢？枚举？

我们发现等价于，即小于的与互质的数个数，这显然等于。

因此最后的答案就是：