先回忆两个基本知识点。
- 母函数：就像是二项式展开，(x+y)^n，可以表示n个物品（分先后）用两种颜色染色，方案数是多少。
- Polya定理：本质上是Burnside引理的进一步延伸，其中color^c(g)，c(g)表示循环节个数，求的就是不动点的个数，可以理解为在同一个循环节中所有的元素必须染成相同颜色。
那么将两者结合在一起，考虑一个置换g。
- 对于其中的一个长度为i的循环，染色方法用母函数表示出来就是(r^i+g^i+b^i)，原因是这i个元素必须用同一种颜色染色，因此不是(r+g+b)^i！
- 然后考虑若干个不相交的置换，那么直接将他们母函数相乘。
- 最后对所有置换求母函数的乘积，就可以得到答案。
例题解释。9颗珠子一个环，两种颜色染色，问6黑3白的染色方法数是多少。
- 循环：(x + y)^9 + (x^3 + y^3)^3*2 + (x^9 + y^9)*6
- 翻折：1个单元素，4个双元素，(x + y)*(x^2 + y^2)^4*9
- 最终答案：x^9 + x^8 y + 4 x^7 y^2 + 7 x^6 y^3 + 10 x^5 y^4 + 10 x^4 y^5 + 7 x^3 y^6 + 4 x^2 y^7 + x y^8 + y^9
完美解决。