先回忆两个基本知识点。

  • 母函数:就像是二项式展开,(x+y)^n,可以表示n个物品(分先后)用两种颜色染色,方案数是多少。
  • Polya定理:本质上是Burnside引理的进一步延伸,其中color^c(g),c(g)表示循环节个数,求的就是不动点的个数,可以理解为在同一个循环节中所有的元素必须染成相同颜色。

那么将两者结合在一起,考虑一个置换g。

  1. 对于其中的一个长度为i的循环,染色方法用母函数表示出来就是(r^i+g^i+b^i),原因是这i个元素必须用同一种颜色染色,因此不是(r+g+b)^i!
  2. 然后考虑若干个不相交的置换,那么直接将他们母函数相乘。
  3. 最后对所有置换求母函数的乘积,就可以得到答案。

例题解释。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

完美解决。