第七章、第七章、 Pólya定定理理 §7.1 群群论根底根底§7.1.1 群的定义 定义7.1.1代数系统〔G， · 〕假设满足以下条件：〔1〕结合律：对恣意a，b，c G， 〔a · b) · c=a ·(b · c);〔2〕G中有一个元素e，适宜对于G中恣意元素a，都有 e·a = a·e = a 〔3〕对于G中恣意a，都可找到G中一个元素a-1，满足a·a-1 = a-1·a = e，那么称〔G， ·〕为群元素e称为G的单位元素，a-1称为a的逆元素假设群G包含的元素个数有限，那么称G为有限群，否那么称G为无限群假设只需〔1〕成立，称〔G， ·〕为半群 例例7.1.1 设Z为整数集，整数集，+、、·是数的加法和乘法，是数的加法和乘法，那么那么〔〔1〕〔〕〔Z，， +〕是群，称〕是群，称为整数加法群由于整数加法群由于存在元素存在元素0，适宜，适宜对于于Z中恣意元素中恣意元素a，都有，都有0 + a = a + 0= a，即，即0为单位元素；且位元素；且对于于Z中恣中恣意意a，都可找到，都可找到Z中一个元素中一个元素-a〔〔a的相反数〕，的相反数〕，满足足a + 〔〔-a〕〕 = 〔〔-a〕〕 + a = 0，即，即-a为a的的逆元素。
逆元素〔〔2〕〔〕〔Z，， ·〕不是群由于〕不是群由于虽然存在然存在单位元位元素素e，适宜，适宜对于于Z中恣意元素中恣意元素a，都有，都有1·a = a·1 = a，但除了，但除了1和和-1外，其它元素均无逆元素外，其它元素均无逆元素 例7.1.2 设Q为一切有理数组成的集合，R为一切实数组成的集合，C为一切复数组成的集合； Q*为一切非零有理数组成的集合，R*为一切非零实数组成的集合，C*为一切非零复数组成的集合，+、·是数的加法和乘法，那么 〔Q，+〕、〔R，+〕、〔C，+〕都是群； 〔Q， ·〕、〔R， ·〕、〔C，·〕都不是群，由于0无逆元素； 〔Q*， ·〕、〔R*， ·〕、〔C*，·〕都是群 例例7.1.3 设S是一个非空集合，是一个非空集合，ρ〔〔S〕〕 是是S的的幂集，集，∩和和∪∪是是ρ〔〔S〕上的交运算和并运算，〕上的交运算和并运算，那么那么 〔〔1〕〔〕〔ρ〔〔S〕，〕，∩〕不是群，〕不是群，虽然存在然存在单位元素位元素S，但不是恣意元素都存在逆元素；，但不是恣意元素都存在逆元素； 〔〔2〕〔〕〔ρ〔〔S〕，〕，∪∪〕也不是群，〕也不是群，虽然存在然存在单位元素：空集，但不是恣意元素都存在逆元位元素：空集，但不是恣意元素都存在逆元素。
素例例7.1.4 设A是是实数域上一切数域上一切n阶非奇特矩非奇特矩阵的的集合，集合，*为矩矩阵的乘法，不的乘法，不难验证〔〔A，，*〕〕 是是群 定理定理7.1.1 群具有以下性群具有以下性质：：单位元位元e独一；独一；逆元独一；逆元独一；满足消去律：即足消去律：即对a，，b，，c∈∈G，假，假设ab＝＝ac，，那么那么b＝＝c；假；假设ba＝＝ca，那么仍有，那么仍有b＝＝c；；a，，b∈∈G，那么，那么(ab)-1＝＝b-1a-1 ，更普通有，更普通有(ab…c)-1＝＝c-1…b-1a-1；；假假设G是有限群，那么是有限群，那么对恣意恣意a∈∈G，必存在一个，必存在一个最小常数最小常数r，使，使ar＝＝e，从而，从而a-1＝＝ar-1r称称为元素元素a的的阶 §7.1.2 群的性群的性质 定理定理7.1.2 设G是一个群，在一个乘是一个群，在一个乘积a1…an中可以恣中可以恣意加括号而求其意加括号而求其值证明：明： 要要证定理，只需定理，只需证明恣意加括号而得的明恣意加括号而得的积等于等于按次序由左而右加括号所得的按次序由左而右加括号所得的积 〔〔…〔〔〔〔a1·a2〕〕·a3〕〕…·an-1〕〕·an 〔〔7.1.1〕〕 〔〔7.1.1〕式〕式对于于n=1，，2不成不成问题；；对于于n=3，由，由结合合律也不成律也不成问题。
如今如今对n用用归纳法，假定法，假定对少于少于n个因个因子的乘子的乘积〔〔7.1.1〕式成立，〕式成立，试证对n个因子的乘个因子的乘积〔〔7.1.1〕式也成立〕式也成立设有由有由a1…an恣意加括号而得到的恣意加括号而得到的乘乘积A，求，求证A等于〔等于〔7.1.1〕式 设在在A中最后一次中最后一次计算是前后两部分算是前后两部分B与与C相乘：相乘： A = 〔〔B〕〕·〔〔C〕〕 今C的因子个数小于n，故由归纳假设，C等于按次序自左而右加括号所得的乘积〔D〕·an由结合律，A=〔B〕·〔C〕=〔B〕·〔〔D〕·an〕=〔〔B〕·〔D〕〕·an但〔B〕·〔D〕的因子个数小于n，故由归纳假设，〔B〕·〔D〕等于按次序由左而右加括号所得的乘积 〔B〕·〔D〕=〔…〔〔a1·a2〕·a3〕…·an-2〕·an-1 因此A =〔〔B〕·〔D〕〕·an =〔〔…〔〔a1·a2〕·a3〕…·an-2〕·an-1〕·an 即A等于〔7.1.1〕式 n个a连乘所得的积称为a的n次方，记为an。
我们规定a0=1，a-n=〔an〕-1 am·an=am+n，〔am〕n=amn 定义7.1.2设〔G，·〕是一个群， H是G的一个子集，假设按照G中的乘法运算·，H仍是一个群，那么〔H，·〕叫做〔G，·〕的子群假设G的一个子群H不等于G，即HG，那么〔H，·〕叫做〔G，·〕的真子群 例例7.1.5 一切整数按照加法作成一个群一切整数按照加法作成一个群对于恣意整数于恣意整数m，，m的一切倍数在加法下的一切倍数在加法下作成整数加法群的一个子群作成整数加法群的一个子群例例7.1.6 任任选群群G的一个元素的一个元素a，，设a的的阶为r，那么，那么H＝＝{a，，a2，，…，，a r-1，，ar＝＝e}是是G的子群这样的群的群H是由某个固定是由某个固定元素元素a的乘方的乘方组成的，成成的，成为循循环群，或称群，或称H是由元素是由元素a生成的群，生成的群，a叫做叫做H的生成元的生成元 定理定理7.1.2 有限群的有限群的阶数必能被其子群的数必能被其子群的阶数整数整除定定义7.1.3 假假设群〔群〔G，，·〕的运算〕的运算·适宜交适宜交换律，律，那么称〔那么称〔G，，·〕〕为Abel群或交群或交换群群定理定理7.1.3 在一个在一个Abel群〔群〔G，，·〕中，一个乘〕中，一个乘积可以恣意可以恣意颠倒因子的次序而求真倒因子的次序而求真值。
假假设群群G的运算不写作乘的运算不写作乘·而写作加而写作加+，那么，那么G叫做一个加法群，我叫做一个加法群，我们不断假定一个加法群是不断假定一个加法群是一个一个Abel群：群： a+b=b+a 在乘法群中写做在乘法群中写做1的如今写做的如今写做0：： a+0=a 在乘法群中写做a-1而称为a的逆的，如今写做-a而称为a的负： a+〔-a〕= 0n为恣意整数时，在乘法群中写作an而称为a的n次方的，如今写做na而称为a的n倍三个指数律如今成为下面的方式： 〔m+n〕a = ma+na， m〔a+b〕= ma+mb， m〔na〕=〔mn〕a §7.2置置换群群 重要的一重要的一类群群 一方面，任何有限群都可以用它表示；一方面，任何有限群都可以用它表示； 另一方面，在伽另一方面，在伽罗瓦瓦实际中它起关中它起关键作用 它它还在本章的在本章的Burnside引理及引理及Pólya定理定理中起着根本作用中起着根本作用 定定义7.2.1 设M是一个非空的有限集合，是一个非空的有限集合，M的一的一个一个一对一一变换称称为一个置一个置换。
设M的元素的元素为a1，，a2，，…，，an，那么，那么M的置的置换σ可以可以简记为 σ＝＝ ，， bi=σ〔〔ai〕，〕，i=1，，2…，，nＭ的每个置Ｍ的每个置换对应a1，， a2，， … ，， an的一个的一个陈列，不同的置列，不同的置换对应不同的不同的陈列列;此外，此外，a1，， a2，， … ，， an的恣意的恣意陈列也确定列也确定M的一个置的一个置换.所以，所以，M的置的置换共有共有n！个，其中！个，其中n是是M的元数，的元数，M上的置上的置换也称也称为n元置元置换以下用Sn表示表示这n！！个置个置换作成的集合作成的集合 例例7.2.1 设M={1，，2，，3}，那么有，那么有3！！=6个个3元置元置换，，σ1＝＝ 为3元恒等置元恒等置换，，σ2= 类似地可以得到似地可以得到σ3＝，＝， σ4＝，＝， σ5＝，＝， σ6＝。
＝故，故，S3 = {σ1，，σ2，，σ3，，σ4，，σ5，，σ6}对M中恣意元素中恣意元素a及及M的恣意两个置的恣意两个置换σ，，τ，，规定定στ〔〔a〕〕=σ〔〔τ〔〔a〕〕例例7.2.2 设σ＝＝ ，，τ＝＝ ，，那么那么στ= 置换的乘法有下述一些性质： (1) 满足结合律：〔στ〕ρ=σ〔τρ〕， (2) n元恒等置换是Sn中的单位元素e，设为σ0，有：σ0τ=τσ0 (3) 每个n元置换在Sn 中都有逆元素 称为n元恒等置换 定理定理7.2.1 n元置元置换的全体作成的集合的全体作成的集合Sn对置置换的乘法作成一个群，称的乘法作成一个群，称为n 次次对称群另外一方面，置另外一方面，置换群的运算和群的运算和实际也是也是对称称图形运算和形运算和计数的根本工具数的根本工具例例7.2.3将将顶点分点分别为1，，2，，3的正三角形〔的正三角形〔见图7.2.1〕〕绕中心中心O沿逆沿逆时针方向分方向分别旋旋转0°、、120°、、240°，可看成，可看成顶点集点集{1，，2，，3}的置的置换，，那么有那么有〔〔1〕旋〕旋转对称关系称关系 ＝＝e，， 〔〔转0°〕〕, 〔〔转120°〕〕 〔〔转240°〕〕 21BCA3图图7.2.12逆时针旋转 〔2〕翻转对称关系，即将三角形123分别绕对称轴1A、2B、3C翻转180°得顶点集的另一类置换：〔绕3C〕 〔绕2B〕 〔绕1A〕因此，描画正三角形的全部对称关系，对应以上六种置换。
延续两次对称映射对应两个置换的乘积，那么置换集在置换乘法下构成一个三次对称群S321BCA3图图7.2.1 定定义7.2.2 设σ是是M的置的置换，假，假设可取到可取到M的元素的元素a1，， …，，ar使使σ〔〔a1〕＝〕＝a2，， σ〔〔a2〕〕= a3 ，， σ〔〔ar-1〕〕= ar，， σ〔〔ar〕〕= a1，而，而σ不不变M的其他的其他的元素，那么的元素，那么σ称称为一个一个轮换，， 记为 〔〔a1 a2 … ar 〕〕 当然可以把当然可以把a1，，… ，，ar中的恣意元素中的恣意元素ai排在排在头一一位而改写成位而改写成 〔〔ai ai+1 … ar a1 … ai-1〕〕 例例7.2.4 σ== 〔〔1 3 4〕〕=〔〔3 4 1〕〕=〔〔4 1 3〕定定义7.2.3 M的两个的两个轮换 σ=〔〔a1…ar〕和〕和τ=〔〔b1…bs〕〕说是不相是不相杂或不相交，假或不相交，假设 a1，，… ，， ar和和b1，，…，，bs都不一都不一样。
定理定理7.2.2假假设σ和和τ是两个不相是两个不相杂的的轮换，那么其乘法适宜交，那么其乘法适宜交换律，即律，即στ=τσ定理定理7.2.3恣意置恣意置换σ恰有一法写成不相恰有一法写成不相杂的的轮换乘乘积证明：先明：先证σ可以写成不相可以写成不相杂的的轮换的乘的乘积，取恣意，取恣意a1∈∈M〔〔1〕假〕假设σ〔〔a1〕〕 = a1，那么，那么a1本人就作成一个本人就作成一个轮换〔〔2〕〕设σ〔〔a1〕〕= a2，， σ〔〔a2〕〕= a3，，…这样下去，由于下去，由于M有有限，故到某一个元素限，故到某一个元素ar，其，其σ〔〔ar〕必然不能再是新的元素，即〕必然不能再是新的元素，即这σ〔〔ar〕必在〕必在a1，，…，，ar之内由于之内由于σ是一是一对一的，我一的，我们已有已有σ〔〔ai〕〕= ai+1，，i=1，，2，， …，，r-1，所以，所以σ〔〔ar〕只能是〕只能是a1于是我是我们得到一个得到一个轮换〔〔a1…ar〕假设M曾曾经没有另外的元素，没有另外的元素，那么那么σ就等于就等于这个个轮换，否那么，否那么设b1不在不在a1，，…，，ar之内，那之内，那么同么同样作法又可得到一个作法又可得到一个轮换〔〔b1…bs〕。
由于〕由于a1，，…，，ar各各自已有自已有变到它的元素，所以到它的元素，所以b1，，…，，bs中不会有中不会有a1，，…，，ar出出现，即，即这两个两个轮换不相不相杂假设M的元素已尽，那么的元素已尽，那么σ就等于就等于这两个两个轮换的乘的乘积，否那么如上又可得到一个，否那么如上又可得到一个轮换如此类推，推，由于由于M有限，最后必得有限，最后必得 σ=〔 a1…ar〕〔b1…bs〕 …〔c1…ct〕 〔7.2.1〕 即σ表成了不相杂的轮换的乘积今证表法独一，设σ又可表为不相杂的轮换的乘积如下： σ=〔 a’1…a’r’〕〔b’1…b’s’〕 …〔c’1…c’t’〕 〔7.2.2〕看〔7.2.1〕式中的恣意轮换，例如〔a1…ar〕 a1必出如今〔7.2.2〕式中的某个轮换之内，例如〔a’1…a’r’〕由于一个轮换中恣意元素都可排在头一位，无妨假定a1＝a’１于是，a2=σ〔a1〕=σ〔a’1〕= a’2，，a3=σ〔a2〕=σ〔a’2〕= a’3，…，如此类推，可见〔a1…ar〕必和〔a’1…a’r’〕完全一样，这就是说，〔7.2.1〕中的恣意轮换必出如今〔7.2.2〕中，同样〔7.2.2〕中的恣意轮换必出如今〔7.2.1〕中，因之，〔7.2.1〕和〔7.2.2〕一样，最多陈列在方法不同，但不相杂的轮换相乘适宜交换律，所以陈列的次序本来是可以恣意颠倒的。
定定义7.2.4 设〔〔a1a2…ar〕〕为一一轮换，我，我们称称r为该轮换的的长度，一度，一轮换的的长度也就是度也就是其中所含的元素个数普通地，我其中所含的元素个数普通地，我们称称长度度为r的的轮换为r阶轮换特特别，，长度度为2的的轮换称称为对换根据公式根据公式7.2.3可知，恣意置可知，恣意置换都可写成都可写成对换的乘的乘积 〔〔a1a2…ar〕＝〔〕＝〔a1a2〕〔〕〔a1 a3〕〕… 〔〔a1ar-1〕〔〕〔a1ar〕〕 〔〔7.2.3〕〕 于是由定理于是由定理7.2.3即可推知以下推即可推知以下推论 推论推论7.2.3 对恣意置换，有一法〔但未 对恣意置换，有一法〔但未必只需一法〕可将其写成一些对换的乘必只需一法〕可将其写成一些对换的乘积定义定义7.2.5 可以分解为奇数个对换之积的可以分解为奇数个对换之积的置换称为奇置换，可以分解为偶数个对置换称为奇置换，可以分解为偶数个对换之积的置换称为偶置换换之积的置换称为偶置换定理定理7.2.4 Sn中一切偶置换的构成一个中一切偶置换的构成一个n！！/2阶的子群阶的子群,称为交错群称为交错群,记为记为An。
§7.3 Burnside引理 §7.3.1 共轭类定定义7.3.1 假假设n次置次置换可表示可表示为互不交互不交杂C1个个1轮换，，C2个个2轮换，，……，，Cn个个n轮换的乘的乘积，那么此置，那么此置换 称称为〔〔C1，，C2，，…，，C n〕〕类型，或型，或(1) C1 (2) C2 …(n)Cn 类型 显然，然， 例例7.3.1 ＝〔＝〔1〕〔〕〔2 3 4〕〔〕〔5 6 7〕属于〕属于11203240506070类型，型，简写写为〔〔1132〕 例例7.3.2 3次次对称群称群S3中一切置中一切置换的的类型是型是满足方程足方程C1•1＋＋C2•2＋＋C3•3＝＝3的一的一切非切非负整数解〔整数解〔见表表7.3.1〕：〕： 〔〔C1，，C2，，C3〕属于〕属于{〔〔3，，0，，0〕，〔〕，〔1，，1，，0〕，〔〕，〔0，，0，，1〕〕} 定定义7.3.2 置置换群群G中属于同一中属于同一类型〔型〔C1,C2,…,Cn〕的全体置〕的全体置换，叫做，叫做该类型相型相应的共的共轭类，，记为D〔〔C1,C2,…,Cn〕〕 。
例例7.3.3将将S3按共按共轭类分成三分成三类，，见表表7.3.1 类（C1,C2,…,Cn）类中置换类中元素数（3，0，0） （1）（2）（3）1（1，1，0） （1 2）（3），（1 3）（2），（1）（2 3） 3（0，0，1） （1 2 3），（1 3 2） 2 定理定理7.3.1 Sn中属中属(1) (2) …(n) 共共轭类的个数的个数为C1 C2 Cn n！C1!C2!…Cn!1 2 … n C1 C2 Cn 证 (1) (2) …(n) 即 C1 C2 Cn(·)…(·)(··)…(··)… (·…·)…(·…·) _∧_/ \1个 _∧_/ \2个 ____∧____/ \n个\______ ______/ \/ C1个\________ ________/ \/ C2个\________ ________/ \/ Cn个 1〕一个长度为k的循环有k种表示， 2〕Ck个长度为k的循环有Ck! 种。
因此Ck个k阶循环在陈列时有Ck!kCk个表示 1,2,…,n的全陈列共有n!个，给定一个陈列，装入格式得一置换除以这些反复度得 n!/(C1!C2!…Cn!1 2 … n )个不同的置换.C1 C2 Cn 例例7.3.4对称群共有对称群共有3个共轭类，即个共轭类，即 §7.3.2 不不动置置换类 定定义7.3.3 设G是集合是集合S={1,2,…, n}上的一个置上的一个置换群，群，k∈∈S, δ∈∈G，假，假设δ (k)=k,即置即置换δ将将k变为k, 那么称那么称k为置置换δ的不的不动点G中一切以中一切以k为不不动点的全体置点的全体置换，构成，构成G的一个子集，称的一个子集，称为k的不的不动置置换类(k=1,2,…, n),记为Zk例例7.3.5 在在S3中，中， Z1={e, (2,3)}, Z2={e, (1,3)}, Z3={e, (1,2)}. 定理7.3.2 置换群G中关于k的不动置换类Zk是G的一个子群封锁性：k→k→k, k k. 结合性：自然有单位元：G的单位元属于Zk.有逆元：P∈Zk,k→k,那么k→k,P-1∈Zk. ∴Zk≤G.P2 P1P1P2PP-1 §7.3.3 等价等价类G={(1)(2)(3)(4),(12),(34),(12)(34)}.在G下，1变2，3变4，但1不变3。
E1=E2={1, 2}, E3=E4={3, 4}.2 个不同的等价类普通[1,n]上G将[1,n]分成假设干等价类，满足等价类的3个条件.(a)自反性;(b)对称性;(c)传送性 定定义7.3.4 设G是集是集S={1,2,…, n}上的置上的置换群群G={δ1, δ2,…, δr}.假假设存在集合中的元素存在集合中的元素i, j，，满足足δ〔〔i〕〕=j,那那么称么称i 与与j 等价等价,记为i=j；； S中与中与i等价的元素的全体等价的元素的全体记为Ei，称，称为元素元素i的的“轨道〞道〞. Ei中的元素的个数称中的元素的个数称为轨道的道的长度度. 元素元素i与与j的的这种等价关系种等价关系满足如下性足如下性质：： 反身性反身性: 对称性：称性： 传送性送性:因此，定因此，定义7.3.4中定中定义的等价关系就是离散数学中所的等价关系就是离散数学中所提到的等价关系，而每个提到的等价关系，而每个Ei就是相就是相应的等价的等价类 定理定理7.3.3 设设G是是[1,n]上的一个置换群，上的一个置换群，Ek是是[1,n]在在G的作用下包含的作用下包含k的等价类，的等价类，Zk是是k不动置换类。
有不动置换类有|Ek||Zk|=|G|. 定理定理7.3.4 设G是是n元集元集S={1,2,…,n}上的置上的置换群群, G={δ1,δ2,…,δn},δ把每个把每个δi都表示成不相都表示成不相杂的的轮换的乘的乘积，令，令λk (δi)表示置表示置换δi中中k阶轮换的个数的个数,那么那么G在在S上上诱导出的等价关系将出的等价关系将S划划分分为不同等价不同等价类的个数的个数为 L=[λ1(δ1)+ λ1(δ2)+…+ λ1(δr)]/|G| (7.3.1) 其中其中λ1(δ)为置置换δ中的不中的不动点点(即即1阶轮换)的的个数个数. 证明证明 按两种方法计算按两种方法计算S在在G中的一切置中的一切置换作用下不动点的总个数换作用下不动点的总个数N.〔〔1〕按置换逐个计算〕按置换逐个计算: 〔〔2〕按〕按S中的每一个元素计算中的每一个元素计算: 两种方法所求结果应该一致两种方法所求结果应该一致,即即 (7.3.2) 由假设由假设S可分解可分解L个不同的等价类，设个不同的等价类，设为。
为 而且 ，假设 (定理7.3.3) 从而有 代入式(7.3.2)整理即得(7.3.1)式成立 例如，G={e,(12), (34), (12)(34)}. λ1(a1)=4, λ 1(a2)=2, λ1(a3)=2, λ1(a4)=0.l=[4+2+2+0]/4=2. 以本例列表分析： 1 2 3 4 λ 1(aj)(1)(2)(3)(4) 1 1 1 1 4 (1)(12)(3)(4) 0 0 1 1 2 (1) (2)(1)(2)(34) 1 1 0 0 2 (1) (2)(12)(34) 0 0 0 0 0 (2) |Zk| → 2 2 2 2 8 Sjk kaj42 12 12 例例7.3.7把一个把一个2×2的方格棋的方格棋盘〔〔图7.3.1〕用黑、白两种〕用黑、白两种颜色涂色，其中每个方色涂色，其中每个方格必需涂成黑色或者白色中的一种格必需涂成黑色或者白色中的一种颜色，色，求有多少种不同的涂色方案？其中假求有多少种不同的涂色方案？其中假设两种涂色方案两种涂色方案经过旋旋转后是一后是一样的那么的那么以以为是一种涂色方案。
是一种涂色方案 分成4格，2着色，方案：经过转动一样的图象算同一方案图象数总是大于方案数1 2 3 4 5 6 7 89 10 11 12 13 14 15 16S={1,2,…,16} 不动：p1=(1)(2)…(16)逆时针转90 ：p2=(1)(2)(3 4 5 6)(7 8 9 10) (11 12)(13 14 15 16)顺时针转90 ：p3=(1)(2)(6 5 4 3)(10 9 8 7) (11 12)(16 15 14 13) 转180 ：p4=(1)(2)(3 5)(4 6)(7 9)(8 10) (11)( 12) (13 15)(14 16)(16+2+2+4)/4=6(种方案) 例例7.3.8 用红用红(r)、黄、黄(y)和绿和绿(g)色颜料色颜料给给3个珠子穿成的项链涂色，求能得到多个珠子穿成的项链涂色，求能得到多少个不同的项链。
假定项链允许旋转，少个不同的项链假定项链允许旋转，但不允许翻转但不允许翻转解解 图图7.3.3 显然用3种颜色涂色3个珠子，273种旋转可以使得项链旋转之后和原来项链重合，即逆时针旋转0°，120°和240°，共对应3个置换，分别是：(27+3+3)/3=11 1937年年，，美美国国数数学学家家Pólya G. 以以<关关于于群群图和和化化学学化化合合物物的的组合合计算算方方法法>为题，，发表表了了长达达110页的著名的著名论文 这篇篇论文文推推行行了了Burnside 引引理理，，给出出了了普普遍遍适适用的普通用的普通计数方法数方法——Pólya计数定理 目目前前，，Pólya定定理理已已成成为组合合数数学学中中强有有力力的的计数数工工具具同同时，，这一一定定理理在在化化学学和和生生物物学学中中也也有有重要的作用重要的作用7.4 Pólya定理 设S=[1,n], M={S1,S2,…Sm}是m种颜色的集合，对S中的元素用M中的颜色着色，得到的图象集合,共有m n 个图象两种涂色方案等价是指：存在置换，将S中元素的一种染色方案变为另一种方案。
求共有多少种不等价的方案？ 定定义7.4.1 恣意一种涂色方案可以表示恣意一种涂色方案可以表示为一个映射一个映射f: S-> C ，其中，其中f规定了定了S中各个中各个元素的染色方案，它将恣意元素的染色方案，它将恣意a€S染上染上颜色色f(a) € C一切一切这样的映射构成集合的映射构成集合CS ，， |CS|= |C| | S|= mn这样就出就出现了两个置了两个置换群群H 与与G: H作用在集合作用在集合S上，上， G作用在方案集作用在方案集CS上上. 两个群之间有内在的联络： 对应于 ，相应地在 CS上诱导出一个置换 ， 且有 〔 为置换 中不相杂轮换的个数〕 例例7.4.1在上面在上面问题，，n=4,m=2仍用两色涂色四仍用两色涂色四个小正方形，被染色的个小正方形，被染色的对象集象集S={1,2,3,4} ，，颜色集色集C={b,w} ，涂色方案集，涂色方案集 这里，里，H是是针对S的置的置换集〔集〔绕正方形中心逆正方形中心逆时针旋旋转〕：〕： 其中其中分分别表示逆表示逆时针旋旋转0°，，90°，，180°和和270°. 不动：p1=(1)(2)…(16) λ1(p1)=24=逆时针转90 ：p2=(1)(2)(3 4 5 6)(7 8 9 10) (11 12)(13 14 15 16) λ1(p2)=21=转180 ：p3=(1)(2)(3 5)(4 6)(7 9)(8 10) (11)( 12) (13 15)(14 16) λ1(p3)=22=顺时针转90 ：p4=(1)(2)(6 5 4 3)(10 9 8 7) (11 12)(16 15 14 13)λ1(p2)=21= 例如 有4个不相杂的轮换，将每个轮换中的点涂以某种颜色，由于每个轮换有两种颜色选择，故共得16 种方案，恰好对应在Cs中不动置换作用下p1的16种方案。
其他情形依次类推即同一循环中的元素都着同一种颜色的图象在Pi的作用下坚持不变 因此求着色的方案数也即求图象的等价类个数按 Burside定理，求等价类的个数归结为每个置 换下的不动点(不动图象)的个数 定理定理7.4.1(Pólya定理定理) 设设H是是n个对象的一个置换群，用个对象的一个置换群，用m种颜色涂染这种颜色涂染这 n个对象，一个对象涂恣意一种颜色，那么在个对象，一个对象涂恣意一种颜色，那么在H作用下不等价的方案数为作用下不等价的方案数为: 为将置换为将置换q表示成不相交的轮换的个数，表示成不相交的轮换的个数，其中包括单轮换其中包括单轮换. 例例7.4.2 用红，黄，蓝三色对等边三角形的顶点用红，黄，蓝三色对等边三角形的顶点染色染色(例例7.3.8)，共有多少种不同方案，共有多少种不同方案(翻转和旋翻转和旋转〕？转〕？ 123 解：设针对的解：设针对的 置换群为置换群为 所求不等价的方案数为： 123〔只需旋转〕 只允许旋转的情况多一种涂色方案，由于图7.3.4中方案a22和a23经过旋转可以变成同一种涂色方案假设改为用4种颜色染色，那么 例例7.4.3 正正6面体的面体的6个面分别用红，蓝两种颜色个面分别用红，蓝两种颜色着色，有多少方案？着色，有多少方案？ 设6个面分别是1，2，3，4，5，6，那么S={1,2,3,4,5,6},找到S上的置换群H。
〔前3后5〕如图7.4.1所示，除了不动置换外，有3种类型的旋转：2614〔a)(b)(c) 〔1〕如图〔a〕所示，经过1和6两个面中心所在直线的对称轴的逆时针旋转90°，180°和270°逆时针旋转90°的置换为(1)(2345)(6) ，思索位置的不同，同类的置换有3个逆时针旋转180°的置换为(1)(24)(35)(6) ，思索位置的不同，同类的置换有3个逆时针旋转270°的置换为(1)(5432)(6) ，思索位置的不同，同类的置换有3个 6142 〔2〕如图〔b〕所示，绕对面棱的中点所在直线的对称轴逆时针旋转180°，对应的置换为(16)(25)(34)，根据位置的不同，同类的置换有6个；2164 〔3〕如图〔c〕所示，绕对角线为对称轴的逆时针旋转120°和240°逆时针旋转120°的置换为(346)(152)，思索位置的不同，同类的置换有4个逆时针旋转240°的置换为(643)(251)，思索位置的不同，同类的置换有4个 2461 因此|H|=24，根据Pólya定理，不同的涂色方案数为， 。