2020-2021:teams:hotpot:burnside引理和polya定理
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:hotpot:burnside引理和polya定理 [2020/07/05 12:37] 喝西北风 |
2020-2021:teams:hotpot:burnside引理和polya定理 [2020/07/05 16:46] (当前版本) 喝西北风 |
||
|---|---|---|---|
| 行 118: | 行 118: | ||
| 所谓升级版，其实是Burnside引理的简化版。学习Polya定理之前要先了解另一种置换的表示法。 | 所谓升级版，其实是Burnside引理的简化版。学习Polya定理之前要先了解另一种置换的表示法。 | ||
| - | ====“循环法”表示==== | + | ====定义7（循环）==== |
| - | 对于一个置换，除了用“两行法”，“一行法”表示，还有一种“循环法”。比如一个置换$(5,1,2,3,4)$，表示$5\rightarrow 1\rightarrow 2\rightarrow 3\rightarrow 4\rightarrow 5$，即5换到1的位置、1换到2的位置、2换到3的位置、3换到4的位置、4换到5的位置，5个元素构成了一个循环。再比如$(5,3,2,1,4)$，表示$5\rightarrow 1\rightarrow 4\rightarrow 5$，$3\rightarrow 2\rightarrow 3$，这两个循环。因此，$(5,3,2,1,4)可以记作(5,1,4)(3,2)$，这种表示置换的方法被称为循环法。$(5,1,2,3,4)$用“循环法”表示仍是$(5,1,2,3,4)$。 | + | 形如$5\rightarrow 1\rightarrow 2\rightarrow 3\rightarrow 4\rightarrow 5$的（首尾相同，中间无重复）链，称为一个循环。这个循环表示将5换到1的位置、1换到2的位置、2换到3的位置、3换到4的位置、4换到5的位置，记作$(5,1,2,3,4)$，称为5元循环。 |
| + | |||
| + | 一个循环中所包含的数，称为这个循环的元素。 | ||
| + | |||
| + | ====定义8（“循环法”表示）==== | ||
| + | |||
| + | 对于一个置换，除了用“两行法”，“一行法”表示，还有一种“循环法”。“循环法”描述一个置换所包含的全部循环。比如“一行法”表示的置换$(5,1,2,3,4)$，包含一个循环$5\rightarrow 1\rightarrow 2\rightarrow 3\rightarrow 4\rightarrow 5$，可以用一个括号，里面描述这个循环。“一行法”表示的$(5,1,2,3,4)$用“循环法”表示仍是$(5,1,2,3,4)$。再比如$(5,3,2,1,4)$，包含$5\rightarrow 1\rightarrow 4\rightarrow 5$和$3\rightarrow 2\rightarrow 3$，这两个循环。因此，$(5,3,2,1,4)用“循环法”可以记作(5,1,4)(3,2)$。 | ||
| 值得注意的是，仅改变括号顺序，并不改变置换。如$(1,2)(3,4)(5)$和$(3,4)(5)(1,2)$均表示$(2,1,4,3,5)$。每个括号内数字的轮换也不改变置换，如“循环法”表示的$(5,1,2,3,4)，(2,3,4,5,1)，(1,2,3,4,5)$均表示“一行法”下的$(5,1,2,3,4)$。但交换一个括号内的两个数，可能会改变置换。如$(5,1,4)(3,2)$表示$(5,3,2,1,4)$，而$(1,5,4)(3,2)$表示$(4,3,2,5,1)$。 | 值得注意的是，仅改变括号顺序，并不改变置换。如$(1,2)(3,4)(5)$和$(3,4)(5)(1,2)$均表示$(2,1,4,3,5)$。每个括号内数字的轮换也不改变置换，如“循环法”表示的$(5,1,2,3,4)，(2,3,4,5,1)，(1,2,3,4,5)$均表示“一行法”下的$(5,1,2,3,4)$。但交换一个括号内的两个数，可能会改变置换。如$(5,1,4)(3,2)$表示$(5,3,2,1,4)$，而$(1,5,4)(3,2)$表示$(4,3,2,5,1)$。 | ||
| - | ====定义（循环数）==== | + | 可以证明，任何一个置换均可用“循环法”唯一地表示。这里的唯一是指，每个循环都确定。 |
| + | |||
| + | ====定义9（循环数）==== | ||
| + | |||
| + | 一个置换所包含的循环的个数，为该置换的循环数。如$(1,2)(3,4)(5)$的循环数为3，$(1,5,4)(3,2)$的循环数为2，$(5,1,2,3,4)$的循环数为1 | ||
| + | |||
| + | 对于任意置换g，设c(g)表示其循环数。 | ||
| - | 用循环法表示一个置换使用的括号数，为该置换的循环数。如$(1,2)(3,4)(5)$的循环数为3，$(1,5,4)(3,2)$的循环数为2，$(5,1,2,3,4)$的循环数为1 | + | ====结论4==== |
| - | 对于任意置换g，设c(g)表示其循环个数。 | + | 假设所求问题为n个点染m种颜色。对于任意置换$g_i$，有$h(g_i)=m^{c(g_i)}$，其中$h(g_i)$为置换$g_i$的不动点数，$c(g_i)$为置换$g_i$的循环数。 |
| - | 可以证明，任何一个置换均可用“循环法”唯一地表示。这里的唯一是指，循环数唯一，且每个循环确定。 | + | 对任意染色方案k，$g_i(k)=k$当且仅当$g_i$的每个循环中所有元素颜色均相同。如k满足$g_i=(1,5,4)(3,2)$，$g_i(k)=k$当且仅当第1,4,5个点颜色相同，第2,3个点颜色相同。因此有$h(g_i)=m^{c(g_i)}$ |
| - | ====Polya定理==== | + | ====结论5（Polya定理）==== |
| - | Polya定理与Burnside引理一样，解决的都是类似n个点染m种颜色的问题。事实上，对于任意置换$g_i$，有$h(g_i)=m^{c(g_i)}$ | + | 将结论4带入Burnside引理，得$ans=\frac 1s\sum^s_{i=1}h(g_i)=\frac 1s\sum^s_{i=1}m^{c(g_i)}$ |
2020-2021/teams/hotpot/burnside引理和polya定理.1593923877.txt.gz · 最后更改: 2020/07/05 12:37 由 喝西北风
