运用置换群解染色模型及代码实现
摘要： 1关键词 1Abstract 1Key words 1引言 21 群及置换群的概念 21.1 群的概念 21.2 置换群相关概念 21.3 其他衍生概念及性质 32 珠子染色模型及相似模型应用 52.1 问题的引入 52.2 问题的一般化及其解 52.3 相似模型讨论 73 模型代码实现及分析 93.1 一般珠子染色问题代码实现 93.2 置换群性质的代码实现 114 解的延拓 135 总结 13致谢 14参考文献： 14附录 A 15附录 B 16运用置换群解染色模型及代码实现摘要：本文主要讨论运用置换群等相关理论解决染色模型的问题，并通过代码进行实现。首先，我们从群论出发，介绍了群中一种特殊的群，置换群。进一步的，我们介绍置换群的性质，主要包括不动点的概念，Burnside引理，Burnside定理，Pólya定理，并给出了一些定理的证明，从而为后续工作做了理论知识的准备。其次，我们引入问题并分析，由浅入深地给出了一般模型及相似模型，由二维到三维，逐渐将模型复杂化，并最终解决问题。最后，本文通过计算机代码实现了模型求解，从而可以借助计算机这一强大的工具解决更多的问题，甚至在群的一些基本运算及性质上，也实现了代码化和机械化。行至文末，对染色模型进行一般化，将其与生活结合，进一步思考这一模型的应用。
目录
引言
引言
群及置换群的概念
群的概念
要了解置换群，首先要知道什么是群。群的常用定义如下。
群的定义[1]：一个非空集合对于一个乘法的代数运算来说构成一个群，如果以下四条成立。
关于这个乘法是闭的；
对于的任意三个元素，，结合律
，
都成立；
对于的任意元素，在中至少存在一个左单位元，使得
；
对于的每一个元素，在中至少存在一个左逆元，使得
。
置换群相关概念
由于置换群是一种特殊的变换群，因此下面先来了解变换群。
变换群的定义[2]：设是一个非空集合。由的若干个变换关于变换的乘法所作成的群，称为的一个变换群。
在对变换群有了初步的了解后。我们逐步引入
*好棒文|www.hbsrm.com +Q: ^351916072*
置换群的定义。首先置换群中的置换定义为有限集合上的一一变换，而一个有限集合的若干个置换形成的一个群叫做一个置换群。数学中置换群的定义为：
次对称群的任意一个子群，都叫做一个次置换群，简称置换群。
这里所说的对称群的定义为：设是一个集合，上的一个双射：（即是置换）。集合上的所有的置换构成的族记为，关于映射的复合运算形成了一个群，当集合为有限集时，称群为次对称群。
对于置换，一般记为如下的形式 ，其中是的一种排列。这个记号表示将换做，将换做，，将换做的这样一种置换。
当置换组成的集合满足[3]
(1) 对中任意两个置换规定一种运算置换的乘积中的置换经过这一运算后，所得的结果仍是中的一个置换；
(2) 这种运算满足结合律；
(3) 中含有恒等置换，它与中任何置换运算的结果仍是此置换；（称为恒等置换，一般记作）；
(4) 中的每一个置换在中必有一逆置换（逆置换即对任一置换有一相应的置换使得显然也可记为）。
满足以上条件就称此集合为一置换群，
以为例，用种置换作用多项式，容易发现部分置换改变了的形式，但也有部分置换并没有改变的形式，我们将所有使不发生变化的置换全部拿出来，共有以下三个：
。
把以上这三个置换组成的集合记为，所以并不是所有的由置换构成的集合一定会是置换群。
其他衍生概念及性质
群对集合作用的定义：
设是一个群，是一个集合(目标集)，若对应上的一个变换满足
。
则称作用于上，称为对的作用。
循环置换定义：
一个置换把变到，变到变到，又让变到，而使得其余的元（如果还有的话）都不变，则称是一个循环置换。这样的置换用符号
，
来表示。
不动点的定义[4]：
设群作用于集合上，，，若，则称是的一个不动点。在上的不动点做成的集合记为。
了解了群及置换群的概念和一些衍生的定义，并不能够很好的应用到实际问题中去，还必须了解群和置换群及其衍生定理的一些性质才能更好的解决问题。
性质1：每一个置换可表示成互不相交的轮换的乘积，而且如果不计次序，分解是唯一的。
证明[2]： 。
1）可以表示成互不相交的对换之积。归纳证明。
2）唯一性。假设，。令。任取，证明使得，从而。同理。
性质2：每一个置换都可以表示成一些对换的乘积。
。
证明[1]：（数学归纳法）时，。
假设当时命题成立，即；
当时，。
综上，命题得证。
性质3：每一个有限群都与一个置换群同构。
性质4[8]：（Burnside引理）设有限群作用于有限集合上，则在的作用下的轨道（此处的轨道即为一种等价关系，并按照这种等价关系对集合的划分）数目为，其中和式是对每一个群元素求和，是的全体不动点的总数。
证明[5]：设，，将作用于上的不动点情况用一张表表示出来，其中表上为的元素，左边为的元素，表中第行第列记为，并令
。
表1：将作用于上的不动点情况
把每一行的元素加起来，其和正好是的不动点数，且把每一列元素相加，其和正好是。于是有
。
由于是有限集，在作用下形成的轨道数也是有限的，故可设在作用下的轨道为。可以把上式左边的和先对同一轨道上的元素所对应的相加，然后再对不同的轨道相加，即
。
由于，，即同一轨道上的稳定子群的阶数相同，所以
。
故
。
综上得证。
性质5[6]：(Burnside定理)设有限群作用于有限加权集合上（的加权是指轨道数目的权重），则在的作用下的轨道的平均权之和为
。
性质6[8]：（Pólya定理）设是个对象的一个置换群，用种颜色去染这个对象，则不同的染色方案数为：
。
其中，为的循环数。
珠子染色模型及相似模型应用
问题的引入
在上一节中我们讨论了群和置换群及其他衍生概念的定义性质，这仅仅是前人研究的理论知识，必须要加以利用，去解决一些问题，比如数学、物理等问题才能让这些研究的结果发光发亮。首先引入珠子染色模型的问题。
引例:现有黑白两种颜色去染两个珠子，可以得到几种不同的项链？
这题的答案很显然，三种。但如果简单的增加珠子数量呢？例如变为黑白去染十个珠子有几种不同染色方法，一样的问题，还能快速的得出答案吗？又或者假设例子中两个珠子固定，这时答案就变成种。而第二个问题也可以很快的得出答案种，但是这样的考虑是不符合实际情况的，项链是一个容易翻转和旋转的模型，不太可能固定珠子的位置不动，这时这类问题就变得复杂起来，思考起来会有不小的阻碍，而通过第一章中置换群的特性就可以帮助我们解决这类问题。
问题的一般化及其解
由引例了解了这个模型的大意后，下面来探讨珠子染色问题的一般情况。
问题：一个包含个珠子的项链，用种颜色染色，求共有多少种染法。
目录
引言
引言
群及置换群的概念
群的概念
要了解置换群，首先要知道什么是群。群的常用定义如下。
群的定义[1]：一个非空集合对于一个乘法的代数运算来说构成一个群，如果以下四条成立。
关于这个乘法是闭的；
对于的任意三个元素，，结合律
，
都成立；
对于的任意元素，在中至少存在一个左单位元，使得
；
对于的每一个元素，在中至少存在一个左逆元，使得
。
置换群相关概念
由于置换群是一种特殊的变换群，因此下面先来了解变换群。
变换群的定义[2]：设是一个非空集合。由的若干个变换关于变换的乘法所作成的群，称为的一个变换群。
在对变换群有了初步的了解后。我们逐步引入
*好棒文|www.hbsrm.com +Q: ^351916072*
置换群的定义。首先置换群中的置换定义为有限集合上的一一变换，而一个有限集合的若干个置换形成的一个群叫做一个置换群。数学中置换群的定义为：
次对称群的任意一个子群，都叫做一个次置换群，简称置换群。
这里所说的对称群的定义为：设是一个集合，上的一个双射：（即是置换）。集合上的所有的置换构成的族记为，关于映射的复合运算形成了一个群，当集合为有限集时，称群为次对称群。
对于置换，一般记为如下的形式 ，其中是的一种排列。这个记号表示将换做，将换做，，将换做的这样一种置换。
当置换组成的集合满足[3]
(1) 对中任意两个置换规定一种运算置换的乘积中的置换经过这一运算后，所得的结果仍是中的一个置换；
(2) 这种运算满足结合律；
(3) 中含有恒等置换，它与中任何置换运算的结果仍是此置换；（称为恒等置换，一般记作）；
(4) 中的每一个置换在中必有一逆置换（逆置换即对任一置换有一相应的置换使得显然也可记为）。
满足以上条件就称此集合为一置换群，
以为例，用种置换作用多项式，容易发现部分置换改变了的形式，但也有部分置换并没有改变的形式，我们将所有使不发生变化的置换全部拿出来，共有以下三个：
。
把以上这三个置换组成的集合记为，所以并不是所有的由置换构成的集合一定会是置换群。
其他衍生概念及性质
群对集合作用的定义：
设是一个群，是一个集合(目标集)，若对应上的一个变换满足
。
则称作用于上，称为对的作用。
循环置换定义：
一个置换把变到，变到变到，又让变到，而使得其余的元（如果还有的话）都不变，则称是一个循环置换。这样的置换用符号
，
来表示。
不动点的定义[4]：
设群作用于集合上，，，若，则称是的一个不动点。在上的不动点做成的集合记为。
了解了群及置换群的概念和一些衍生的定义，并不能够很好的应用到实际问题中去，还必须了解群和置换群及其衍生定理的一些性质才能更好的解决问题。
性质1：每一个置换可表示成互不相交的轮换的乘积，而且如果不计次序，分解是唯一的。
证明[2]： 。
1）可以表示成互不相交的对换之积。归纳证明。
2）唯一性。假设，。令。任取，证明使得，从而。同理。
性质2：每一个置换都可以表示成一些对换的乘积。
。
证明[1]：（数学归纳法）时，。
假设当时命题成立，即；
当时，。
综上，命题得证。
性质3：每一个有限群都与一个置换群同构。
性质4[8]：（Burnside引理）设有限群作用于有限集合上，则在的作用下的轨道（此处的轨道即为一种等价关系，并按照这种等价关系对集合的划分）数目为，其中和式是对每一个群元素求和，是的全体不动点的总数。
证明[5]：设，，将作用于上的不动点情况用一张表表示出来，其中表上为的元素，左边为的元素，表中第行第列记为，并令
。
表1：将作用于上的不动点情况
把每一行的元素加起来，其和正好是的不动点数，且把每一列元素相加，其和正好是。于是有
。
由于是有限集，在作用下形成的轨道数也是有限的，故可设在作用下的轨道为。可以把上式左边的和先对同一轨道上的元素所对应的相加，然后再对不同的轨道相加，即
。
由于，，即同一轨道上的稳定子群的阶数相同，所以
。
故
。
综上得证。
性质5[6]：(Burnside定理)设有限群作用于有限加权集合上（的加权是指轨道数目的权重），则在的作用下的轨道的平均权之和为
。
性质6[8]：（Pólya定理）设是个对象的一个置换群，用种颜色去染这个对象，则不同的染色方案数为：
。
其中，为的循环数。
珠子染色模型及相似模型应用
问题的引入
在上一节中我们讨论了群和置换群及其他衍生概念的定义性质，这仅仅是前人研究的理论知识，必须要加以利用，去解决一些问题，比如数学、物理等问题才能让这些研究的结果发光发亮。首先引入珠子染色模型的问题。
引例:现有黑白两种颜色去染两个珠子，可以得到几种不同的项链？
这题的答案很显然，三种。但如果简单的增加珠子数量呢？例如变为黑白去染十个珠子有几种不同染色方法，一样的问题，还能快速的得出答案吗？又或者假设例子中两个珠子固定，这时答案就变成种。而第二个问题也可以很快的得出答案种，但是这样的考虑是不符合实际情况的，项链是一个容易翻转和旋转的模型，不太可能固定珠子的位置不动，这时这类问题就变得复杂起来，思考起来会有不小的阻碍，而通过第一章中置换群的特性就可以帮助我们解决这类问题。
问题的一般化及其解
由引例了解了这个模型的大意后，下面来探讨珠子染色问题的一般情况。
问题：一个包含个珠子的项链，用种颜色染色，求共有多少种染法。
版权保护: 本文由 hbsrm.com编辑，转载请保留链接: www.hbsrm.com/jsj/xxaq/957.html
