Pólya 定理学习笔记 | ABC428G 题解
用来对在若干置换下本质不同的方案数计数。
（这里会有一些证明，但是先咕掉（（
首先是 Burnside 引理：
结论是，假设群 \(G\) 作用于集合 \(X\) 上。
令 \(O_x\) 表示 \(x\in X\) 的轨道，即 \(\{gx|g\in G\}\)。
令 \(X_g\) 表示 \(g\in G\) 的所有不动点，即 \(\{x|x\in X,gx=x\}\)。
Burnsize 引理指出：
\[|\{O_x|x\in X\}|=\dfrac 1{|G|}\sum_{g\in G}|X_g|
\]
接下来是 Pólya 定理：
假设群 \(G\) 作用于 \(X\) 上，\(Y\) 是一个有限集，令 \(X^Y\) 是全体映射 \(X\rightarrow Y\) 构成的集合。
（可以认为 \(X\) 是元素，\(Y\) 是颜色, \(X^Y\) 表示所有的染色方案。
定义 \(c(g)\) 表示，取与 \(g\) 等价的置换 \(\sigma_g(x)=gx\)，那么 \(c(x)\) 等于 \(\sigma_g\) 分解成的不相交轮换数量。
那么著名的 Pólya 定理断言：
\[|\{O_x|x\in X^Y\}|=\dfrac 1{|G|}\sum_{g\in G} |Y|^{c(g)}
\]
例子：
求 \(n\) 种颜色给长为 \(n\) 的环染色，仅通过旋转重合的方案被认为相同，求本质不同方案数。
定义 \(Y=\{C_1,C_2,\cdots,C_n\}\) 表示所有的颜色。
\(X\) 表示环上的 \(n\) 个点表示的集合。
群 \(G=(\{\) 顺时针旋转 \(i\) 个单位 \(| 0\le i < n\},\)操作复合\()\)。
由 Pólya 定理直接得出答案为：
\[\dfrac 1n \sum_{i=1}^nn^{\gcd(i,n)}=\dfrac 1n\sum_{d|n}n^d\varphi(\dfrac nd)
\]
太厉害了！
还有点例题，后面再补（（