等价类计数(Polya定理/Burnside引理)学习笔记

时间:2024-01-11 15:18:38

  参考:刘汝佳《算法竞赛入门经典训练指南》

  感觉是非常远古的东西了,几乎从来没有看到过需要用这个的题,还是学一发以防翻车。

  置换:排列的一一映射。置换乘法相当于函数复合。满足结合律,不满足交换律。

  置换的循环分解:即将置换看成一张有向图,分解成若干循环。循环的数量称为循环节。

  以置换集合来描述等价关系。如果存在一个置换将一个方案映射到另一个方案,则这两个方案等价。置换集合应当构成置换群。

  不动点:方案s经过置换f不变,则s为f的不动点。

  Burnside引理:等价类数量=所有置换的不动点数量的平均值。

  Polya定理:对于某置换的不动点,显然每个循环内颜色相同,于是不动点数量即为颜色数循环节数。将其代入Burnside引理即得Polya定理。(为什么这是定理上面是引理啊)

  没了。