ACM – 置换

终于搞明白置换了,可喜可贺。建议不要看屈的离散数学,看白书即可,通俗易懂。

我在这里简单阐述一下,当然也是依据李大大的书。

置换

置换就是把n个元素全排列,置换可以定义乘法。

循环就是置换的移位。例如:

| 1 | 2 | 3 | 4 | 5 | | - | - | - | - | - | | 3 | 5 | 1 | 4 | 2 |

即为(1 3)(2 5)(4)

其中,(1 3)通过这个置换发现形成一个循环,(2 5)通过这个置换形成一个循环,(4)本身构成一个循环。

不动点

对于一个置换f,若一个着色方案s经过置换后不变,则称s为f的不动点,将f的不动点记录为C(f),则可证明等价类数目为所有C(f)的平均值,成为Burnside引理。

Polya定理

一般的,如果f分解成m(f)个循环的乘积,那么每个循环的所有格子的颜色必须相同。(因为这样才是一个不动点)。

假设涂k种颜色,则有

$$C(f) = k^{m(f)}$$

(乘法原理。循环内相同,循环间可以不同)。

代入Burnside引理之后得到Polya定理:等价类的个数等于所有置换f的$k^{m(f)}$的平均数。

Contents

comments powered by Disqus