下载文档原格式
波利亚定理证明波利亚定理是数论中的重要定理，它对于解决数的分拆问题起着重要的作用。
以下将从引言、前提条件、证明、例子等几个方面来详细讨论波利亚定理。
引言波利亚定理是由意大利数学家波利亚（Giorgi Pólya）于1918年提出的，它是更普遍形式的斯特林公式，用于解决非负整数的分拆问题。
波利亚定理在组合数学、数论和多项式函数方面有着广泛的应用。
前提条件在正式证明波利亚定理之前，我们需要了解一些基本概念和前提条件。
首先，我们定义一个分拆为把一个正整数n表示为若干个正整数的和，这些正整数可以相同也可以不同。
例如，对于正整数4的分拆可以是4=1+1+1+1=1+1+2=2+2=1+3。
其次，我们定义一个分拆的个数为同一个正整数的所有分拆的个数。
例如，对于正整数4，它的分拆个数为4。
最后，波利亚定理的表述如下：对于任意正整数n，其分拆个数可以表示为多项式函数。
即存在多项式函数P(n)，使得n的分拆个数等于P(n)。
证明为了证明波利亚定理，我们需要借助生成函数的概念。
生成函数是一种将多项式序列和数学问题联系起来的数学工具，它在组合数学中广泛应用。
首先，我们定义一个生成函数F(x)，它表示一个正整数的分拆函数。
F(x) = (1 + x + x^2 + x^3 + ...) * (1 + x^2 + x^4 + x^6 + ...) * (1 + x^3 + x^6 + x^9 + ...) * ...其中，每个括号代表一个无穷级数，表示相应正整数的所有分拆个数。
我们可以观察到，F(x)的展开式中，x^n的系数恰好等于正整数n 的分拆个数。
接下来，我们将F(x)进行展开。
F(x) = (1 + x + x^2 + x^3 + ...) * (1 + x^2 + x^4 + x^6 + ...) * (1 + x^3 + x^6 + x^9 + ...) * ...= (1 + x + x^2 + x^3 + ...) * (1 + x^2 + x^4 + x^6 + ...) * (1 + x^3 + x^6 + x^9 + ...) * ...× (1 - x^1) * (1 - x^2) * (1 - x^3) * ...我们可以看到，展开后的表达式中，每一项的系数是用于表示分拆个数的多项式函数。
第六章 P ól y a (波利亚)定理6.1 群论基础普通代数主要涉及的计算对象为数，运算方式多为加、减、乘、除。
本节将把运算对象扩展到一般的集合元素，运算方式也可以是多种多样，例如矩阵运算、集合的并、交、差运算等。
换言之，我们要将研究对象及其运算和所要讨论的性质延伸到抽象代数的范畴。
§6.1.1 群的概念定义6.1.1 给定非空集合G 及定义在G 上的二元运算“·”，若满足以下四个条件，则称集合G 在运算“·”下构成一个群，简称G 为一个群。
：（1）封闭性：a ，b ∈G ，则a ·b ∈G ；（2）结合律：（a ·b ）·c ＝a ·(b ·c)；（3）单位元：存在e ∈G ，对任意a ∈G ，有a ·e ＝e ·a ＝a ；（4）逆元素：对任意a ∈G ，存在b ∈G ，使得a ·b ＝b ·a ＝e ，称b 为a 的逆元素，记为a －1 。
群的运算符“·”可略去，即 a ·b ＝ab .群的运算并不要求满足交换律。
如果某个群G 中的代数运算满足交换律，则称G 为交换群或Abel 群。
群的元素可以是有限个，叫作有限群 ；也可以是无限个，叫无限群。
以|G|表示有限群中元素的个数，称为群的阶，那么当G 为无限群时，可以认为|G|＝∞。
例6.1.1 偶数集，整数集Z ，有理数集Q ，实数集R ，复数集C 关于数的加法构成群，称为加法群。
因为数的运算对加法满足要求（1）和（2）。
其中的单位元为0，每个数a 关于加法的逆元为：a －1＝－ a 。
但是，关于数的乘法，这些集都不构成群。
因为在偶数集中关于普通乘法不存在单位元。
而在Z 、Q 、R 、C 中，虽然关于普通乘法有单位元1，但数0没有逆元。
例6.1.2 不含零的有理数集Q1，实数集R1和复数集C1关于数的乘法构成群其中单位元为e ＝1，数a 的逆元为aa 11=-。
burnside定理和polya计数Burnside定理和Polya计数引言：组合数学是一门研究对象的排列和组合规律的学科。
在组合数学中，有两个重要的定理：Burnside定理和Polya计数。
这两个定理在对称性的研究中起着重要的作用。
本文将介绍Burnside定理和Polya 计数的概念、原理和应用，并对它们的关系进行探讨。
一、Burnside定理1. 概念：Burnside定理，也称作轮换定理，是由英国数学家威廉·伯恩赛德于1897年提出的。
它是一种用于计算置换群的不动点数量的方法，特别适用于计算对称性问题。
2. 原理：Burnside定理的核心思想是通过对置换群的每个元素进行分类，来计算不动点的总数。
具体来说，对于一个给定的置换群G和一个对象X，如果对象X在置换g下保持不变，则称X是置换g的不动点。
Burnside定理给出了计算所有不动点数量的方法。
3. 应用：Burnside定理在组合计数中有广泛的应用，特别是在计算染色问题和多边形的对称性问题上。
例如，当我们考虑将n个相同的珠子穿在一个项链上，Burnside定理可以帮助我们计算出不同的项链数量。
二、Polya计数1. 概念：Polya计数是由匈牙利数学家乔治·波利亚于1937年提出的。
它是一种计算置换群下不同染色方案数量的方法，通过考虑置换群的不变子群来计算。
2. 原理：Polya计数的核心思想是通过考虑置换群的不变子群来计算不同染色方案的数量。
具体来说，对于一个给定的置换群G和一组颜色C，Polya计数可以帮助我们计算出在置换群作用下，具有不同颜色方案数量。
3. 应用：Polya计数在组合计数中有广泛的应用，特别是在计算多边形染色、手链染色和立方体染色等问题上。
例如，当我们考虑将一个正方形的四个顶点染色，Polya计数可以帮助我们计算出不同的染色方案数量。
三、Burnside定理与Polya计数的关系1. 关系：Burnside定理和Polya计数都是研究置换群的方法，都可以用于计算对称性问题和染色问题。
波利亚的解题理论（讲稿）同学们好!今天我们大家一起来学习波利亚的解题理论。
首先，让我们了解一下波利亚的生平.乔治·波利亚（George Polya,1887-1985）美籍匈牙利数学家，生于匈牙利,青年时期曾在布达佩斯、维也纳、哥廷根、巴黎等地攻读数学、数学、物理和哲学,1912年获数学博士学位。
他是法国科学院、美国全国科学院和匈牙利科学院的院士，是20世纪举世公认的数学家和数学教育家,也是享有国际盛誉的数学方法论大师,为数学方法论的现代研究,特别是为数学解题教学研究奠定了必要的理论基础。
他的成就主要包括解题理论、数学教学理论和教师教育理论,发表200多篇论文和许多专著，主要著作包括:《怎样解题》（1944)、《数学的发现》（1954）、《数学与猜想》（1961)等。
其中《怎样解题》与《数学的发现》集中论述了怎样解题的问题,而《数学与猜想》则对合情推理进行了生动地、富有创造性地论述。
在数学方面,对实变函数、复变函数和概率论等若干分支领域作出了开创性的贡献,留下了以他的名字命名的术语和定理。
在数学解题研究领域,波利亚是一面旗帜，也是一代宗师。
这里主要介绍他的解题理论。
学习波利亚的解题理论，首先需要了解对“解题”过程的界定。
波利亚认为，解题是智力的特殊成就，题目是数学的心脏，数学教学的本质在于教会学生解题，解题思想“应当诞生在学生心里，教师仅仅像助产士那样行事"（苏格拉底语),由此,数学教师的首要任务是发展学生解决问题的能力.为了帮助学生，为了回答“一个好的解法是如何想出来的”这个令人困惑的问题，他专门研究可解题的思维过程，用朴素而现代化的形式来阐明探索法（既有助于发现的探索方法），并集几十年教学与科研之大成写成《怎样解题》一书,与1948年出版，风靡世界.其中“怎样解题"表仔细分析了求解各种数学问题时的思维过程，成为经典之作。
概括的说来，“怎样解题”表是波利亚的解题理论的核心内容。
波利亚计数定理解读波利亚计数定理是组合数学中的一个重要定理，由法国数学家乔治·波利亚于1889年提出。
该定理是一种计算排列和组合的方法，可以帮助我们快速求解一些复杂的排列组合问题。
在实际问题中，波利亚计数定理有着广泛的应用，特别是在计算不同元素的排列组合情况时，可以大大简化计算过程。
本文将对波利亚计数定理进行解读，介绍其基本概念和应用方法。
### 波利亚计数定理的基本概念波利亚计数定理是一种用于计算排列组合的定理，其核心思想是将一个集合划分为若干个不相交的循环类，然后根据每个循环类的元素个数来计算排列组合的情况。
具体来说，波利亚计数定理可以描述如下：设集合A有n个元素，其中元素a1有n1个，元素a2有n2个，……，元素ak有nk个，且满足n1 + n2 + … + nk = n。
若对于任意的置换σ，有置换σ中的元素ai的循环类有ci个，则集合A的置换数为：N = (n!)/(n1! * n2! * … * nk!) * (c1^n1 * c2^n2 * … *ck^nk)其中，n!表示n的阶乘，n1!、n2!、…、nk!分别表示n1、n2、…、nk的阶乘，c1、c2、…、ck分别表示元素a1、a2、…、ak的循环类个数。
### 波利亚计数定理的应用方法波利亚计数定理的应用方法主要包括以下几个步骤：1. 确定集合元素和循环类：首先需要确定待计算的集合A中的元素个数和每个元素的个数，然后根据题目要求确定每个元素的循环类个数。
2. 计算置换数：根据波利亚计数定理的公式，计算集合A的置换数。
将集合A的元素个数和循环类个数代入公式中，按照公式逐步计算得到最终的置换数。
3. 应用于具体问题：将计算得到的置换数应用于具体的问题中，根据题目要求进行进一步的计算和分析，得出最终的结果。
### 波利亚计数定理的例题解析下面通过一个具体的例题来解析波利亚计数定理的应用：例题：有5个红球和3个蓝球，将这些球排成一排，使得相邻的两个球颜色不同。
组合数学中的Polya计数原理应用方向组合数学是数学中的一个重要分支领域，研究的是集合、排列、组合等离散结构的性质和规律。
其中，Polya计数原理是组合数学中的一项重要工具，被广泛用于解决各种计数问题。
本文将介绍Polya计数原理的基本概念及其在组合数学中的应用方向。
一、Polya计数原理的基本概念Polya计数原理，又称群论计数定理，是由匈牙利数学家乔治·波利亚于20世纪初提出的。
它基于群论的概念，用于解决组合计数问题。
Polya计数原理的核心思想是将问题的计数转化为对一定置换群下的不动点的计数。
所谓“置换群”，指的是一个具有结合律、可逆性和封闭性的集合，集合中的元素是对原始对象进行排列的一种操作。
例如，对于一个正方形的顶点，我们可以通过旋转和翻转操作来改变其位置。
在这个例子中，我们可以构建一个有8个元素的置换群，用来描述这些操作。
根据Polya计数原理，对于一个置换群G和一个有n个元素的结构，若置换群G的作用下，有m个置换不变的结构（即旋转、翻转等操作不改变结构本身），那么这个结构的计数就等于集合的元素数量除以G中不动点的数量，即N = (n!/|G|) * m。
二、Polya计数原理的应用方向1. 组合图形计数Polya计数原理在组合图形计数中有广泛的应用。
以方格填色问题为例，若要对一个n x m的方格网进行填色，要求相邻方格的颜色不相同。
使用Polya计数原理可以将该问题转化为计算某个置换群的不动点数量问题，从而得到方格填色的计数结果。
2. 筚路蓝缕问题筚路蓝缕问题是指从原点出发，只允许向上和向右移动，到达目标点的路径计数问题。
这类问题常用的解决方法是使用组合数学中的Catalan数，而Polya计数原理可以用于对Catalan数结果的计数验证，从而增加了对路径计数问题的理解。
3. 化学同分异构体计数在化学领域中，同分异构体计数是一个具有实际应用的问题。
同分异构体是指化学物质中具有相同分子式但结构不同的分子。
2012 年同等学力计算机综合组合数学辅导-波利亚定理图6.6.9 具有 4 个顶点12 条边的有向图同法，可以用 S4 导出关于 e1 , e2 ，…， e12 的 24 阶置换群，其格式为的一个，的 6 个，的 8 个，的 3 个，的 6 个。
根据 Pólya 定理可得 Q12 的轮换指标＝ 1 令得＝＝其中 x 2 y10 的系数为 5，即有两条边的四个顶点的有向图共有 5 种（见图 6.6.10）。
图 6.6.10 图6.6.10 四个顶点两条边的不等价的有向图而与图 6.6.10（c）等价的有两条边的有向图共有 12 个，见图6.6.11。
图 6.6.11 图6.6.11 与图 6.6.10（c）等价的 4 点两边有向图2012 年同等学力计算机综合组合数学辅导-波利亚定理习 1. 2. 题六一张卡片分成 4×2 个方格，每格用红蓝两色涂染，可有多少种方法？一根木棍等分成 n段，用 m 种颜色涂染，问有多少种染法？当 n＝m＝ 2 和 n＝m＝3 时各有多少种方法？正五角星的五个顶点各镶嵌一个宝石，若有 m 种颜色的宝石可供选择，问可以有多少种方案？有一个正方形木筐，用漆刷 4 边。
现有三种不同颜色的漆，可有多少种不同的涂法？一个圆分成 6 个相同的扇形，分别涂以三色之一，可有多少种涂法？两个变量的布尔函数 f(x,y的全体关于变量下标可以进行置换时，其等价类的个数为多少？写出其布尔表达式。
红、蓝、绿三种颜色的珠子，每种充分多，取出 4 颗摆成一个圆环，可有多少种不同的摆法？某物质分子由 5 个 A 原子和 3 个 B 原子组成，8 个原子构成一个正立方体，问最多可能有几类分子？验证下列函数对于运算是一个群：，， x ，，。
，用 g,r,b,y 四种颜色涂染正方体的六个面，求其中两个面用色 g，两个面用色 y，其余一面用 b，一面用 r 的方案数。
对一正六面体的八个顶点，用 y 和 r 两种颜色染色，使其中有 5 个顶点用色 y，其余 3 个顶点用色 r，求其方案数。
polya 定理Polya 定理是一种由乔治·波利亚在数学领域中提出来的定理。
它可以用于求解不同颜色的序列排列的数目，是数学中一个非常重要的理论。
该定理还可以引申到其他领域中，如化学和物理学。
接下来，我们将从几个不同的方面来讨论 Polya 定理。
一、定义Polya 定理又称作 Burnside 定理，它是在群论中被提出来的一个基本问题。
该定理的定义如下：设 G 是一个有限群，α 是一个作用在集合 X 上的置换群，N是 X 的颜色数，则 X 的置换群在等价关系下的集合数目为：L(G, α, N) = 1/|G| * Σg∈G N^{C(g)}其中，|G| 表示 G 的阶，即 G 中元素的个数。
C(g) 表示 g 在置换α 中的循环数。
二、应用范围Polya 定理在组合数学中的应用范围非常广泛。
例如，它可以用于求解多边形的不同染色方案数目和若干个等价类的划分数目。
在化学中，它可以用于预测分子对称性和对称性种类的数量。
在物理学中，它可以用于求解晶体的总对称性和空间群的种类。
因此，Polya 定理在不同的领域中都有着广泛而重要的应用。
三、证明过程Polya 定理的证明较为复杂，这里仅简单提及一下证明过程。
首先，根据 Burnside 引理，我们可以得到 Polya 定理应用于置换群的等价类数目的公式。
其次，我们需要将这个公式推广到一般情况下的群作用中。
具体步骤如下：1. 首先，我们需要找到一个等价关系，它将 G 作用在 X 上的置换分成若干种等价类。
2. 接着，我们需要证明每一个等价类都可以对应一个单独的集合，它包含着和该等价类中的置换对应的项的数目。
3. 然后，我们需要证明这些集合的并集等于整个置换群 G。
4. 最后，我们需要利用群论中的公式计算每个集合所对应的排列数目，使得所有集合的数目相加等于 Polya 定理中的公式。
四、总结Polya 定理是一种在群论中非常重要的定理。
它可以用于求解不同颜色的序列排列的数目，以及预测物理和化学等领域中的对称性种类和数量。
波利亚计数Polya计数将波利亚计数定理整理在这⾥，作为⼀个总结和介绍，也⽅便以后复习为什么学习Polya计数定理通过Polya计数定理，我们可以计算等价类的数量，⽐如下⾯这个问题：⽤mm种颜⾊给⼀个正⽅形染⾊，如果正⽅形可以⾃由转动，求染⾊⽅案数让我们从⼀些概念开始1 等价关系1.1 等价关系的定义假设VV是⼀个集合，SS是定义在VV上的⼀个关系，若SS有如下性质：⾃反性传递性对称性那么， SS就是⼀个等价关系aa和bb有关系SS,可以记为aSbaSb假设定义关系SS，图形aa可以旋转得到bb⇔⇔aSbaSb例如图中的⽅块1⽅块1和⽅块2⽅块2具有关系SS，即他们可以通过旋转得到彼此，⽽⽅块1⽅块1和⽅块2⽅块2则没有关系SS1.2 等价类通过上图，可以看出来：⽅块1⽅块1和⽅块2⽅块2是同⼀类的，⽽⽅块1⽅块1和⽅块2⽅块2则是另外两类，于是可以想到集合VV上的等价关系SS将集合的元素划分到不同的类中，我们把它称为等价类⽽包含元素aa的等价类则是由满⾜aSbaSb的所有元素bb组成的(当然也包含元素aa),即C(a)={b∈V|aSb}C(a)={b∈V|aSb}仔细想⼀想，不难发现两个不同等价类是不相交的2 置换群2.1 置换群的定义假设A={1,2,…,n}A={1,2,…,n}，通过置换，将AA中的元素重新排列，得到另⼀个排列a1,a2,…,a n a1,a2,…,a n，可以把这个过程写成12…na1a2…a n(12…n a1a2…a n)所以，可以将置换看成⼀个双射函数f:{1,2,…,n}→{1,2,…,n}f:{1,2,…,n}→{1,2,…,n}置换之间也可进⾏合成运算π1=12344213π2=12342143π1=(12344213) π2=(12342143) () ()()π1∘π2=1234 2431π1∘π2=(1234 2431)π1∘π2(1)=π1(π2(1))=2π1∘π2(1)=π1(π2(1))=2⽽在置换集合XX上定义的群则称为置换群，置换群也是群也要满⾜群的性 质运算封闭π1∈X,π2∈X⇒π1∘π2∈Xπ1∈X,π2∈X⇒π1∘π2∈X满⾜结合律有单位元，置换I(a)=aI(a)=a有逆元，π∘π−1=Iπ∘π−1=I但是置换与计算不同染⾊模式数量有什么关系？图形的旋转等变换都可以⽤⼀个只置换来表⽰我们把1-4按顺时针放到正⽅形的四个⽅块中π1=12341234π1=(12341234)旋转90∘90∘π2=12344123π2=(12344123)2.2 置换群衍⽣的等价关系假设G=(X,∘)G=(X,∘)，通过置换π∈Xπ∈X，元素aa可以被置换为其他元素π(a)=bπ(a)=b，可以发现这⾥也存在⼀种等价关系， 可以定义等价关系SS:aSb⇔∃π∈G,π(a)=baSb⇔\existπ∈G,π(a)=bπ∈G也可以来表⽰π∈Xπ∈G也可以来表⽰π∈X⽽包含aa的等价类C(a)C(a)是由所有满⾜aSbaSb的元素bb组成的，因此我们也可以说C(a)={π(a) |π∈G}C(a)={π(a) |π∈G}如果A={1,2,3}A={1,2,3}π1=123123π1=(123123)() ()()()π2=123321π2=(123321)X={π1,π2}X={π1,π2},可以验证G={X,∘}G={X,∘}是⼀个置换群，{1,3}{1,3}是⼀个等价类，{2}{2}是⼀个等价类可以证明⾃反、对称、传递是满⾜的3 伯恩赛德引理这个定理将给出置换群衍⽣出的等价关系的（不同）等价关系数量的计数⽅法3.1 伯恩赛德引理假设GG是⼀个置换群，aa是AA中的元素，如果π(a)=aπ(a)=a，则称AA中的元素aa在置换ππ下是不变的(Invariant)，Inv(π)Inv(π)表⽰不变元素的数量定理 假设GG是⼀个集合AA的置换群，设SS是GG上衍⽣出来的等价关系，那么SS中的等价类的数量由下式给出:1 |G|∑π∈G Invπ)1 |G|∑π∈G Inv(π)|G||G|是置换群中置换的数量，让我们来⽤⼀下这个定理，假设GG下⾯的置换组成π1=231234,π2=234134,π1=(12341234),π2=(12342134),π3=231243,π4=2342143,π3=(12341243),π4=(12342143),可以看出来，有两个等价类分别是{1,2}{1,2}，{3,4}{3,4}，等价类的数量为22可以验证Inv(π1)=4,Inv(π2)=2,Inv(π3)=2,Inv(π4)=0Inv(π1)=4,Inv(π2)=2,Inv(π3)=2,Inv(π4)=0等价类的数量=14(4+22+0)=2等价类的数量=14(4+2+2+0)=23.2 伯恩赛德引理的证明Part 1这个证明可以跳过，对后⾯阅读没有什么影响对于AA中的元素aa，我们可以定义稳定算⼦(Stabilizer)的概念，St(a)St(a)是保持元素aa不变的置换的集合，St(a)={π∈G|π(a)=a}St(a)={π∈G|π(a)=a}，=π2=123231,π3=123312,π1=(123123,π2=123231),π3=(123312),()((14)(12)(14)(1)+(123123),()()π1)(St(2)={π1}St(2)={π1}，包含22的等价类C(2)={π1(2),π2(2),π3(2)}={1,2,3}C(2)={π1(2),π2(2),π3(2)}={1,2,3}可以发现|St(2)|×|C(2)|=|G|=3|St(2)|×|C(2)|=|G|=3，这不是巧合引理 假设GG是⼀个置换群，⽽且a∈Aa∈A，那么，|St(a)|×|C(a)|=|G||St(a)|×|C(a)|=|G|让我们来简单证明这个定理假设C(a)={b1,b2,⋯,b r}C(a)={b1,b2,⋯,b r}，那么存在⼀个π1π1，满⾜π1(a)=b1π1(a)=b1，同样存在π2(a)=b2π2(a)=b2,⋯⋯,设P={π1,π2,…,πr}P={π1,π2,…,πr}，⽽且|P|=|C(a)||P|=|C(a)|，于是转化为证明|St(a)|×|P|=|G||St(a)|×|P|=|G|从GG中选⼀个置换ππ, ππ⼀定将aa置换成⼀个元素，设该元素为b k b k，即π(a)=b kπ(a)=b k，另⼀个⽅⾯，πk(a)=b kπk(a)=b k,因此π−1k∘π(a)=aπ−1k∘π(a)=a，即π−1k∘π∈St(a)π−1k∘π∈St(a)，πk∘(π−1k∘π)=ππk∘(π−1k∘π)=π这说明GG中的元素ππ可以由St(a)St(a)和C(a)C(a)中的元素合成得到然后我们再来说明这是唯⼀的假设π=πk∘γ=πl∘δπ=πk∘γ=πl∘δ ，γγ和δδ都在St(a)St(a)中，因此πk∘γ(a)=b k=πl∘δ(a)=b lπk∘γ(a)=b k=πl∘δ(a)=b l，因此l=kl=k，这种组合⽅式是唯⼀的，因此|St(a)|×|C(a)|=|G||St(a)|×|C(a)|=|G|Part 2让我们继续证明伯恩赛德引理假设A={1,2,…,n}A={1,2,…,n}, G={π1,π2,…,πm}G={π1,π2,…,πm}，让我们看看下⾯这个式⼦的是否成⽴|Inv(π1)|+|Inv(π2)|+⋯+|Inv(πm)|=|St(1)|+|St(2)|+⋯+|St(n)||Inv(π1)|+|Inv(π2)|+⋯+|Inv(πm)|=|St(1)|+|St(2)|+⋯+|St(n)|可以发现都计数的是满⾜π(a)=aπ(a)=a序对<π,a><π,a>的个数，因此等式是成⽴的将等式两边同时除以|G|，左边就得到了伯恩赛德引理的型式，⽽右边，根据Part1中的引理可以转化为1C(1)+1C(2)+⋯+1C(n) (1)1C(1)+1C(2)+⋯+1C(n) (1)⽽C(a)C(a)是⼀个等价类，两个等价类的交集要么是全集要么是空集，假设C(a)={b1,b2,…,b r}C(a)={b1,b2,…,b r},那么，1C(b1)+1C(b2)+⋯+1C(b r)=1r+1r+⋯+1r=11C(b1)+1C(b2)+⋯+1C(b r)=1r+1r+⋯+1r=1于是(1)式计数的就是等价类的个数4 等价着⾊伯恩赛德引理和计算等价着⾊数量有什么关系呢?其实伯恩赛德引理不能直接帮助我们计算等价着⾊的数量，但是我们可以适当的定义等价关系，然后再计算等价着⾊的数量假设C(R,D)C(R,D)使⽤RR中的颜⾊，来给DD中的元素染⾊的着⾊集合，假设RR是⿊⾊和⽩⾊，DD是图中的节点，那么C(R,D)C(R,D)是给图中节点染⾊的集合C(R,D)={C1,C2,⋯,C16}C(R,D)={C1,C2,⋯,C16}定义在C(R,D)C(R,D)上的置换π∗π∗，将⼀种着⾊变为另⼀种着⾊，更形式⼀点，假定ff是⼀个着⾊，那么新着⾊π∗fπ∗f定义为(π∗f)(a)(π∗f)(a)是f(π(a))f(π(a))同样，也可以定义C(R,D)C(R,D)上的置换群，G∗={π∗|π∈G}G∗={π∗|π∈G}，GG和G∗G∗的元素数量⼀样，因为ππ和π∗对应于⼀种相同旋转π∗对应于⼀种相同旋转。
波利亚计数定理
波利亚定理（Pólya定理）又称多项式分部定理，由匈牙利数学家George Pólya于1919年提出。
它是一个重要的定理，在许多数学领域都有重要的应用，例如组合数学、统计学、离散数学等等。
波利亚定理的定义：设P(n)为任意个多项式的最高次项的系数，其次数为n，则该多项式的和表示为：
P(n)=A（1+x+x^2 + x^3+...+x^n）
其中，A称为该多项式的均分常数，它也可以用来描述多项式的分部展开结果。
波利亚定理的推导：对于一个多项式P(n)，它的最高项与x^n相乘，因为它们具有同样的次数以及相同的系数，因此形式上可以改写为：
又因为带入x ∞ 后，各项将等于零，并且整个式子只剩下一项，即最高次项系数，因此：
P(n)=A。
易知，A和P(n)之间的关系就是波利亚计数定理：
（1）组合数学中，展开多项式可以用波利亚定理来表示，有助于快速计算。
（2）统计学中，波利亚定理可以用来计算概率，可以用它来计算取得目标的概率。
（3）离散数学中，波利亚方程可以用来求解线性递推关系。
总结：
波利亚定理（Pólya定理）是一个非常重要的定理，它的定义是描述一个多项式P(n)的最高次项系数和均分常数之间的关系；它的推导带来了多项式展开及求和等等的方法，且它在许多数学领域都有重要的应用，比如组合数学、统计学、离散数学等等。
所以，该定理已经被广泛应用于实际问题的解决上。
第六章Pól y a(波利亚)定理6.1 群论基础普通代数：计算对象为数，运算方式多为加、减、乘、除。
扩展：计算对象为一般的集合元素，运算方式也可以是多种多样。
例如矩阵运算、集合的并、交、差运算等。
抽象代数：应用：代数、计数、通信编码、信息与网络安全等。
§6.1.1 群的概念定义6.1.1给定非空集合G及定义在G上的二元运算“·”，若满足以下四个条件，则称集合G在运算“·”下构成一个群，简称G为一个群。
：（1）封闭性：a，b∈G，则a·b∈G；（2）结合律：（a·b）·c＝a·(b·c)；（3）单位元：存在e∈G，对任意a∈G，有a·e＝e·a＝a；（4）逆元素：对任意a∈G，存在b∈G，使得a·b＝b·a＝e，称b为a的逆元素，记为a－1。
群的运算符“·”可略去，即a·b＝ab .群的运算并不要求满足交换律。
如果某个群G中的代数运算满足交换律，则称G为交换群或Abel群。
群的元素可以是有限个，叫作有限群；也可以是无限个，叫无限群。
以|G|表示有限群中元素的个数，称为群的阶，那么当G为无限群时，可以认为|G|＝∞。
例6.1.1偶数集，整数集Z，有理数集Q，实数集R，复数集C关于数的加法构成群，称为加法群。
因为数的运算对加法满足要求（1）和（2）。
其中的单位元为0，每个数a关于加法的逆元为：a－1＝－a。
但是，关于数的乘法，这些集都不构成群。
因为在偶数集中关于普通乘法不存在单位元。
而在Z 、Q 、R 、C 中，虽然关于普通乘法有单位元1，但数0没有逆元。
例6.1.2 不含零的有理数集Q 1，实数集R 1和复数集C 1关于数的乘法构成群其中单位元为e ＝1，数a 的逆元为a a11=-。
例6.1.3 G ＝{1，－1}关于乘法构成群单位元为e ＝1，由于 (－1)－1＝－1，所以数a ＝－1的逆元为它自身。
