旋转和翻转，以及这两个变换的运算构成一个群

传送门

【题意】

给定 \(n\) 个空位待填的圆环，每个空位可以填入红、蓝、绿任一颜色的珠子。问不同构的方案数为多少？

题目认为旋转、沿坐标轴翻转后相同的两个方案是同构的。

\(n

【分析】

旋转和翻转，以及这两个变换的运算构成一个群

比较裸的 Polya 定理

旋转和翻转，以及这两个变换的运算构成一个群 \(G\) 。

而原本的翻转只能沿坐标轴翻转，但我们考虑先将圆环旋转 \(-\theta\) 度的变换 \(rot_{-\theta}\)，再沿 \(x\) 轴翻转 \(sym_0\) ，最后再旋转 \(\theta\) 度 \(rot_{\theta}\) ，则等价于圆环沿 \(\theta\) 的这条极径进行了翻转 \(sym_{\theta}\)。即 \(sym_{\theta}=rot_{\theta}\circ sym_{0}\circ sym_{-\theta}\) 。

由于 \(rot_{\theta}, sym_{0}, rot_{-\theta}\in G\)，根据运算的封闭性，\(sym_{\theta}\in G\) 。即群内包括了任意角度的旋转，和任意角度的翻转。

现考虑到旋转角度只有 \(k\cdot {2\pi\over n}, k\in\{0, 1, 2, \cdots, n-1\}\) 时才有意义，翻转角度只有 \(k\cdot {\pi\over n}, k\in\{0, 1, 2, \cdots, n-1\}\) 时才有意义

当旋转角度为 \(k\cdot {2\pi\over n}\) 时，构成置换 \(\left(\begin{matrix}1&2&3&\cdots &n-k&n-k+1&\cdots &n\\\\ k+1&k+2&k+3&\cdots&n&1&\cdots &k\end{matrix}\right)\)，可拆解成 \(\gcd(k, n)\) 个不可拆解的置换

当 \(n\) 为奇数时，翻转角度 \(k\cdot {\pi\over n}\) 使得除了直线上一点，其余每个点与关于直线的对称点构成一个置换，故可拆解成 \(\lceil{n\over 2}\rceil={n+1\over 2}\) 个不可拆解的置换

当 \(n\) 为偶数时，若 \(k\) 为奇数，则翻转角度 \(k\cdot {\pi\over n}\) 使得每个点与关于直线的对称点构成一个置换，可分解为 \({n\over 2}\) 个不可拆解的置换

当 \(n\) 为偶数时，若 \(k\) 为偶数，则翻转角度 \(k\cdot {\pi\over n}\) 使得除线上的两个点，每个点与关于直线的对称点构成一个置换，可分解为 \(({n\over 2}+1)\) 个不可拆解的置换

故根据 Polya 定理：

当 \(n\) 为奇数时，方案数为 \(\displaystyle {1\over 2n}(\sum_{i=0}^{n-1} 3^{\gcd(i, n)} + \sum_{i=0}^{n-1} 3^{n+1\over 2})={1\over 2n}(\sum_{i=0}^{n-1} 3^{\gcd(i, n)} + n\cdot 3^{n+1\over 2})\)

当 \(n\) 为偶数时，方案数为 \(\displaystyle {1\over 2n}(\sum_{i=0}^{n-1} 3^{\gcd(i, n)} + \sum_{i=0}^{n-1}3^{n\over 2}+\sum_{i=0}^{n-1}3^{{n\over 2}+1})={1\over 2n}(\sum_{i=0}^{n-1} 3^{\gcd(i, n)} + 2n\cdot 3^{n\over 2})\)

到这一步已经可以出答案了，不过本人顺着莫比乌斯反演推了推：

\(\displaystyle \sum_{i=0}^{n-1} 3^{\gcd(i, n)}=\sum_{i=1}^n 3^{\gcd(i, n)}=\sum_{d\mid n}3^d\sum_{i=1}^n

旋转和翻转，以及这两个变换的运算构成一个群