2020-2021:teams:hotpot:burnside引理和polya定理
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:hotpot:burnside引理和polya定理 [2020/07/05 12:28] 喝西北风 |
2020-2021:teams:hotpot:burnside引理和polya定理 [2020/07/05 16:46] (当前版本) 喝西北风 |
||
|---|---|---|---|
| 行 48: | 行 48: | ||
| 对一种同种染色置换$g（g\in G）$和每一种染色方案k（$1\le k\le N$），g(k)也是一个1~N的整数,表示另一种染色方案，即将染色方案k按照g进行置换。从k到g(k)的映射称为g对k的作用。特别注意，g(k)可能等于k（如k表示将所有点染成红色，则无论怎么旋转，显然染色方案不变），也可能不等于k。但无论g(k)与k是否相等，g(k)与k都是本质相同的染色（因为是同种染色置换得到的，在最终答案中只考虑一次）。 | 对一种同种染色置换$g（g\in G）$和每一种染色方案k（$1\le k\le N$），g(k)也是一个1~N的整数,表示另一种染色方案，即将染色方案k按照g进行置换。从k到g(k)的映射称为g对k的作用。特别注意，g(k)可能等于k（如k表示将所有点染成红色，则无论怎么旋转，显然染色方案不变），也可能不等于k。但无论g(k)与k是否相等，g(k)与k都是本质相同的染色（因为是同种染色置换得到的，在最终答案中只考虑一次）。 | ||
| - | 介绍了这么多，终于可以阐述Burnside引理的内容了。首先，构造一个函数$\forall g\in G，x\in \{1,2,...,N\}，f(g,x)=[g(x)=x]$。这是一个典型的用于计数的函数。设$c(g_i)=\sum^N_{k=1}f(g_i,k)$，即满足$g_i(k)=k$的染色方案个数。那么最终答案$ans=\frac 1s\sum^s_{i=1}c(g_i)$，其中$s=|G|$ | + | 介绍了这么多，终于可以阐述Burnside引理的内容了。首先，构造一个函数$\forall g\in G，x\in \{1,2,...,N\}，f(g,x)=[g(x)=x]$。这是一个典型的用于计数的函数。设$h(g_i)=\sum^N_{k=1}f(g_i,k)$，即满足$g_i(k)=k$的染色方案个数。那么最终答案$ans=\frac 1s\sum^s_{i=1}h(g_i)$，其中$s=|G|$ |
| ====Burnside引理证明==== | ====Burnside引理证明==== | ||
| 行 94: | 行 94: | ||
| ===结论3（Burnside引理）=== | ===结论3（Burnside引理）=== | ||
| - | $f(g,x)$和$c(g_i)$的定义见Burnside引理。接下来将开启一波愉快的推式子。 | + | $f(g,x)$和$h(g_i)$的定义见Burnside引理。接下来将开启一波愉快的推式子。 |
| - | $\sum^s_{i=1}c(g_i)=\sum^s_{i=1}\sum^N_{x=1}f(g_i,x)=\sum^N_{x=1}\sum^s_{i=1}f(g_i,x)=\sum^N_{x=1}|Z_x|$ | + | $\sum^s_{i=1}h(g_i)=\sum^s_{i=1}\sum^N_{x=1}f(g_i,x)=\sum^N_{x=1}\sum^s_{i=1}f(g_i,x)=\sum^N_{x=1}|Z_x|$ |
| 这道题求的答案$ans$是等价类个数。 | 这道题求的答案$ans$是等价类个数。 | ||
| - | 由结论2，$\sum^N_{x=1}|Z_x|=ans\cdot |G|$。所以$ans=\frac 1s\sum^s_{i=1}c(g_i)$，其中$s=|G|$ | + | 由结论2，$\sum^N_{x=1}|Z_x|=ans\cdot |G|$。所以$ans=\frac 1s\sum^s_{i=1}h(g_i)$，其中$s=|G|$ |
| ====问题最终解决==== | ====问题最终解决==== | ||
| 行 116: | 行 116: | ||
| =====Burnside引理升级版——Polya定理===== | =====Burnside引理升级版——Polya定理===== | ||
| - | ====“循环法”表示==== | + | 所谓升级版，其实是Burnside引理的简化版。学习Polya定理之前要先了解另一种置换的表示法。 |
| - | 对于一个置换，除了用“两行法”，“一行法”表示，还有一种“循环法”。比如一个置换$(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)$。 | + | ====定义7（循环）==== |
| + | |||
| + | 形如$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)表示其循环数。 | ||
| + | |||
| + | ====结论4==== | ||
| + | |||
| + | 假设所求问题为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)}$ | ||
| - | 用循环法表示一个置换使用的括号数，为该置换的循环数。如$(1,2)(3,4)(5)$的循环数为3，$(1,5,4)(3,2)$的循环数为2，$(5,1,2,3,4)$的循环数为1 | + | ====结论5（Polya定理）==== |
| - | 可以证明，任何一个置换均可用“循环法”唯一地表示。这里的唯一是指，循环数唯一，且每个循环确定。 | + | 将结论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定理.1593923334.txt.gz · 最后更改: 2020/07/05 12:28 由 喝西北风
