引入
给定一串 \(n\) 个珠子组成的环链，每个珠子可以被染成黑白两色，求本质不同的染色方案的个数？
群，置换和置换群
群的不严谨定义
如果我们对于一个集合 \(G\) 定义一种运算 \(\cdot\) ，该运算满足以下性质：
- 封闭性：\(\forall a, b \in G, a \cdot b \in G\)
- 结合律：\(\forall a, b, c \in G, (a \cdot b) \cdot c = a \cdot (b \cdot c)\)
- 单位元：\(\exists e \in G, \forall a \in G, e \cdot a = a\)
- 逆元：\(\forall a \in G, \exists a^{-1} \in G, a \cdot a^{-1} = e\)
则称 \((G, \cdot)\) 一起构成了一个群。
置换的概念
我们抽象并拓展 “变换” 这个概念，定义集合 \(G \to G\) 的一个双射为一个置换，举个例子： \[ \left(\begin{matrix} 1 &2 &3 &4 \\ 2 &3 &4 &1 \end{matrix}\right) \] 这个置换表示将将集合中的 \(1\) 变成 \(2\)，\(2\) 变成 \(3\)，\(3\) 变成 \(4\)，\(4\) 变成 \(1\)。
置换群
稍微想一想可知，置换是可以成群的，称为置换群，对于这个置换群我们定义的运算就是置换的复合，对于这个运算我们考察其是否满足群的性质：
- 封闭性：大部分情况下应该是成立的
- 结合律：显然
- 单位元：\(\left(\begin{matrix} 1 &2 &3 &\cdots \\ 1 &2 &3 & \cdots \end{matrix}\right)\)
- 逆元：置换是集合到集合的双射，显然
置换群的引入允许我们使用群论来处理一开始的问题，说抽象了我们刚才的问题就是：求一个序列的集合 \(X\)，在一个置换群 \(G\) 作用下本质不同的元素个数。
Burnside 引理
序列集合 \(X\) 在置换群 \(G\) 的作用下不同的序列数等于不动点的平均数： \[ |X \setminus G| = \frac{1}{|G|} \sum_{g \in G} |X^g| \] 其中 \(X^g = \{ x \in X | g(x) = x\}\) 表示在置换 \(g\) 作用下不动点的集合，何为不动点呢？
例如对于置换 \(\left(\begin{matrix} 1 &2 &3 &4 \\ 3 &4 &1 & 2 \end{matrix}\right)\) 而言，序列 \((1, 2, 1, 2)\) 就是它的一个不动点，因为它在置换后还是原来的样子。
我们接下来考察对于给定置换如何数出不动点的数目，从例子入手，比如说我们要求的是置换，\(\left(\begin{matrix} 1 &2 &3 &4 \\ 4 &3 &2 & 1 \end{matrix}\right)\) 的不动点数目，我们挨个考虑这样的序列拥有什么样的性质：
- 第一位与第四位相同
- 第二位与第三位相同
- 第三位与第二位相同
- 第四位与第一位相同
显然我们最后得到了一个集合 \(\{ \{1, 4\}, \{2, 3\} \}\)，其中的每一个集合中的元素必须相等，考虑染色问题，对于每一组 “相等”，我们可以把它整个染成两种颜色，因此这个置换共有 \(2^2 = 4\) 个不动点。
由于等号的传递性，如果我们逐位查看一个置换，把上下的两位并入同一个 “相等集合”，那么最后我们一定会得到若干个这样的相等集合，每个 “相等集合” 都可以被独立地染成不同的颜色，由乘法定理，我们就得到了 ——
Polya 定理
\[ |X \backslash G| = \frac{1}{|G|} \sum_{g \in G} m^{c(g)} \]
其中 \(m\) 是颜色个数，\(c(g)\) 是置换 \(g\) 形成的 “循环数”，一个 “循环” 是指某一位经过不断地置换之后最后回到自身。可以看到 Polya 定理其实就是我们上面的推论，不需要更多解释。
循环同构序列计数
终于进入了我们的正题，循环同构序列计数，到这一步我们终于可以解答一开始的问题了：
Polya 定理的精髓就在于求出一个置换的循环数，而朴素的枚举显然是不够的，我们考察所谓 “循环同构” 背后依赖的哪些置换，比如说对于一个长度为 \(4\) 的序列，以下置换后它与自身是循环同构的： \[ \left(\begin{matrix} 1 &2 &3 &4 \\ 2 &3 &4 &1 \end{matrix}\right), \left(\begin{matrix} 1 &2 &3 &4 \\ 3 &4 &1 &2 \end{matrix}\right), \left(\begin{matrix} 1 &2 &3 &4 \\ 4 &1 &2 &3 \end{matrix}\right), \left(\begin{matrix} 1 &2 &3 &4 \\ 1 &2 &3 &4 \end{matrix}\right) \] 我们发现一个循环同构的置换就是把它的后面全部移到前面来，前面几位补到后面去。
为了接下来的推导方便我们让位数起始于 \(0\)。
那么，对于一个偏移了 \(k\) 的置换，第 \(a\) 位被置换之后就到了 \((a + k) \bmod n\) 的位置，其中 \(n\) 为序列长度，而对于一个长度为 \(l\) 的完整循环来说，它必须满足：
\[ \begin{aligned} a + kl &\equiv a &\pmod{n} \\ kl &\equiv 0 &\pmod{n} \end{aligned} \] 显然当 \(kl = \operatorname{lcm}(k, n)\) 的时候 \(l\) 有最小值 \(\frac{\operatorname{lcm}(k, n)}{k}\)。由于每一位都偏移了 \(k\) 位，因此置换中每个循环的长度都是相等的，而因为每个循环都 cover 了 \(l\) 个元素，因此循环的个数为： \[ \begin{aligned} \frac{n}{l} &= \frac{n}{\frac{\operatorname{lcm}(k, n)}{k}} \\ &= \frac{kn}{\operatorname{lcm}(k, n)} \\ &= \gcd(k, n) \end{aligned} \] 这个发现让我们免于枚举每个循环置换，相反，我们枚举 \(\gcd(k, n)\) 的每一个取值 \(d\)，即 \(n\) 的因数，统计出 \(\gcd(k, n) = d\) 的所有 \(k\) 的个数，依 Polya 定理统一累加到答案上。
那怎么统计呢？枚举？
我们发现 \(\gcd(k, n) = d\) 等价于 \(\gcd({k \over d}, {n \over d}) = 1\)，即小于 \(n \over d\) 的与 \(n \over d\) 互质的数个数，这显然等于 \(\varphi({n \over d})\)。
因此最后的答案就是：
\[ \sum_{d|n} \varphi\left(\frac{n}{d}\right)m^d \]