2020-2021:teams:hotpot:burnside引理和polya定理
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:hotpot:burnside引理和polya定理 [2020/06/08 11:31] 喝西北风 |
2020-2021:teams:hotpot:burnside引理和polya定理 [2020/07/05 16:46] (当前版本) 喝西北风 |
||
|---|---|---|---|
| 行 36: | 行 36: | ||
| 其中，$i_1,i_2,\ldots ,i_n$为1到n的排列 | 其中，$i_1,i_2,\ldots ,i_n$为1到n的排列 | ||
| - | 意思是，把第$i_1$个点换到1号位置，第$i_2$个点换到2号位置，……，第$i_n$个点换到n号位置。 | + | 意思是，把第$i_1$个点换到1号位置，第$i_2$个点换到2号位置，……，第$i_n$个点换到n号位置。这个记录方法被称为“两行法”（我自己命名的）。 |
| + | 因为第一行通常为按顺序的1-n，所以经常省略第一行，用$(i_1,i_2,...,i_n)$表示一个n元置换。这个表示方法被称为“一行法”。 | ||
| ===定义2（同种染色置换，同种染色置换群）=== | ===定义2（同种染色置换，同种染色置换群）=== | ||
| 行 47: | 行 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引理证明==== | ||
| 行 68: | 行 69: | ||
| 对将G中的s个元素分别作用于k，得到k的等价类，用符号$E_k$表示。$E_k=\{g_1(k),g_2(k),...,g_s(k)\}$包含全部本质上和k相同的朴素染色方案。特别注意，$g_1(k),g_2(k),...,g_s(k)$中存在一些相同的数，应当剔除重复的结果，得到$E_k$。 | 对将G中的s个元素分别作用于k，得到k的等价类，用符号$E_k$表示。$E_k=\{g_1(k),g_2(k),...,g_s(k)\}$包含全部本质上和k相同的朴素染色方案。特别注意，$g_1(k),g_2(k),...,g_s(k)$中存在一些相同的数，应当剔除重复的结果，得到$E_k$。 | ||
| + | |||
| + | 设$E=\{k_1,k_2,...,k_m\}$，显然有$E=E_{k_1}=E_{k_2}=...=E_{k_m}$ | ||
| 我们最终要计算有多少种本质不同的染色方案，其实就是要计算一共有多少个等价类。 | 我们最终要计算有多少种本质不同的染色方案，其实就是要计算一共有多少个等价类。 | ||
| 行 81: | 行 84: | ||
| 显然有$H\subseteq G$，下证$G\subseteq H$。 | 显然有$H\subseteq G$，下证$G\subseteq H$。 | ||
| - | 对G中任意元素g,有$g(k)\in E_k$，设$g(k)=g_{j_y}(k)$。则有$g_{j_y}^{-1}(g(k))=k$，即$g*g_{j_y}^{-1}\in Z_k$。则有$g_{i_x}=g*g_{j_y}^{-1}$则$g=g_{i_x}*g_{j_y}\in H$。所以$G\subseteq H$。 | + | 对G中任意元素g,有$g(k)\in E_k$，设$g(k)=g_{j_y}(k)$。则有$g_{j_y}^{-1}(g(k))=k$，即$g*g_{j_y}^{-1}\in Z_k$。则有$g_{i_x}=g*g_{j_y}^{-1}$，$g=g_{i_x}*g_{j_y}\in H$。所以$G\subseteq H$。 |
| 所以有$G=H$。 | 所以有$G=H$。 | ||
| 因为$|H|=pq=|E_k|\cdot |Z_k|$，所以$|G|=|E_k|\cdot |Z_k|$ | 因为$|H|=pq=|E_k|\cdot |Z_k|$，所以$|G|=|E_k|\cdot |Z_k|$ | ||
| + | |||
| + | 这个结论证明了，对一个等价类$E=\{k_1,k_2,...,k_m\}$，有$\sum^m_{i=1}|Z_{k_i}|=|G|$ | ||
| ===结论3（Burnside引理）=== | ===结论3（Burnside引理）=== | ||
| + | |||
| + | $f(g,x)$和$h(g_i)$的定义见Burnside引理。接下来将开启一波愉快的推式子。 | ||
| + | |||
| + | $\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$是等价类个数。 | ||
| + | |||
| + | 由结论2，$\sum^N_{x=1}|Z_x|=ans\cdot |G|$。所以$ans=\frac 1s\sum^s_{i=1}h(g_i)$，其中$s=|G|$ | ||
| + | |||
| + | ====问题最终解决==== | ||
| + | |||
| + | 希望大家没有忘记原先的问题。如果忘了，可以回到最上面看一下。 | ||
| + | |||
| + | 在这个问题当中，我们最重要的就是求出$c(g_i)$。我们不妨先从简单的情况想起。我们设$g_i$表示顺势针转i次的置换。显然有，$c(g_0)=N=n^n$，也就是说，对$\forall k,g_0(k)=k$。 | ||
| + | |||
| + | 同样的，显然有$c(g_1)=n$，只有所有点颜色都相同的朴素染色方案，才有顺势针旋转1次后，结果不变。 | ||
| + | |||
| + | 对于旋转i次，要求第1个点，第1+i个点，第1+2i个点,...,第ki%n+1个点颜色必须相同。所有形如(ki+1)%n+1的点颜色必须相同；形如(ki+2)%n+1的点必须相同......由裴蜀定理一共有$gcd(n,i)$组点，每组点的颜色必须相同。因此，$c(g_i)=n^{gcd(n,i)}$ | ||
| + | |||
| + | 所以，这个问题的答案$ans=\frac1n \sum^n_{i=1} n^{gcd(n,i)}$ | ||
| + | |||
| + | =====Burnside引理升级版——Polya定理===== | ||
| + | |||
| + | 所谓升级版，其实是Burnside引理的简化版。学习Polya定理之前要先了解另一种置换的表示法。 | ||
| + | |||
| + | ====定义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)$。 | ||
| + | |||
| + | 可以证明，任何一个置换均可用“循环法”唯一地表示。这里的唯一是指，每个循环都确定。 | ||
| + | |||
| + | ====定义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)}$ | ||
| + | |||
| + | ====结论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定理.1591587062.txt.gz · 最后更改: 2020/06/08 11:31 由 喝西北风
