Polya

Polya的总结

Step1 - Polya-定理

设 G 是 n 个对象的一个置换群, 用m种颜色染图这 n 个对象，则不同的染色方案数为：

其中 G = {P1, P2, P3,…, Pg}, C(Pk) 表示 Pk 的循环节。

Step2 - Polya-定理的引入与简单理解

参考博客：https://blog.csdn.net/lyc1635566ty/article/details/52545355

参考视频：学堂在线-组合数学

一、前置知识：

1.置换：

其实就是集合 G 到 G 的一个双射，例如：

也就是说每次变换，1 –> a1，2 –> a2，…，n –> an。

2.置换的乘法：

例如定义 P1, P2两个置换。

定义置换乘法：

表示先作 P1 的置换，再作 P2 的置换。

3.Burnside引理:

设G={a1,a2,…ag}是目标集[1,n]上的置换群。每个置换都写成不相交循环的乘积。 是在置换ak的作用下不动点的个数，也就是长度为1的循环的个数。通过上述置换的变换操作后可以相等的元素属于同一个等价类。若G将[1,n]划分成l个等价类，则等价类个数为：

二、Polya定理的引出：

设 G 是 n 个对象的一个置换群, 用m种颜色染图这 n 个对象，则不同的染色方案数为：

其中 G = {P1, P2, P3,…, Pg}, C(Pk) 表示 Pk 的循环节。

Step3 - Polya-定理的使用

1. 确定置换的个数（旋转角度，翻转）
2. 确定循环节个数（旋转角度时考虑 gcd，翻转时特殊考虑）
3. 套用 Polya 公式

Step4 - Polya定理-例题&&模板（POJ 1286）

题目大意：

给你一个长度为 n 的项链（环），着 3 种颜色，问有多少种

解题思路：

1. 确定置换个数：旋转 (k * 360 / n)° n 种， 对称反转 n 种， 共 2 * n 种
2. 确定循环节个数，旋转角度 (k * 360 / n)° 循环节为 gcd(n, k)，对称反转分奇数和偶数。
3. 套用 Polya 公式求解

代码+模板：

#include <cstdio>