ACM – 置换

点击量:27

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

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

置换

置换就是把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)}$的平均数。

发表评论

电子邮件地址不会被公开。 必填项已用*标注