组合数学 波利亚定理

波利亚定理证明波利亚定理是数论中的重要定理，它对于解决数的分拆问题起着重要的作用。

以下将从引言、前提条件、证明、例子等几个方面来详细讨论波利亚定理。

引言波利亚定理是由意大利数学家波利亚（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) * ...我们可以看到，展开后的表达式中，每一项的系数是用于表示分拆个数的多项式函数。

波利亚计数定理解读波利亚计数定理是组合数学中的一个重要定理，由法国数学家乔治·波利亚于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个蓝球，将这些球排成一排，使得相邻的两个球颜色不同。

关于波利亚的中值定理问题
关于波利亚的中值定理问题
波利亚中值定理是一个常用的数学定理，它指出一系列等差数列的中间值（或
中位数）与最后一个数值之和的一半相等。

这定理是在19世纪30年代由法国数学家米歇尔·波利亚提出的。

波利亚中值定理的公式为，对于一个等差数列，中位数等于最后一个数除以二
的和，即：
M=(a+(n-1)d)/2
其中，M为中位数，a为该等差数列第一个项，n为该数列序列项的个数，d为
公差。

举一个例子，3、7、11、15、19这个等差数列，第一个项a=3，n=5，d=4，根
据题意可求出：
M=(3+(5-1)4)/2=11/2=5.5
可以看出，中位数为5.5，它恰好位于等差数列的中间，也正好等于最后一个
数（19）加上第一个数（3）之和的一半（22/2=11）。

波利亚中值定理最显著的特点是在等差数列中确定中位数的简明性、一致性和
可证明性，它不仅具有理论的用处，也在实际的统计分析等应用中发挥了重要作用。

另外，它还有助于理解和计算平均值、中位数、众数等统计量之间的关系。

因此，波利亚中值定理是数学学习和数据分析中不可或缺的一个定律。

ACM 暑期集训 组合数学（5） 置换群与P ólya 定理1 群的基本概念ba e ab b a a a e e a a b b ac b a c b a A A b a A b a A =======∈∈∀-1543)()(21,,，则）逆元：（）单位元：（）可交换性：（）可结合性：（）封闭性（算的性质上的二元运算。

二元运为，则称都有，如果对于，运算设非空集合οοοοοοοοοοοοο上的二元运算。

是非空集合，代数系统A A οο〉〈为无限群。

为有限群。

否则，称是有限集合，称如果。

，下是一个群，记作群在运算则称集合存在逆元）对于（）存在单位元（是可结合的）运算（是封闭的）运算（，满足下述条件：，设给定代数系统G G G G G G Ga G a eG *〉〈=*∈∈∀***〉〈-1,43212 置换群{}个不同的置换。

次置换共有例如：到自身的双射，，，次置换：集合!14234321321,321321n n s k k kk n n X n n ⎪⎪⎭⎫⎝⎛=⎪⎪⎭⎫ ⎝⎛==ΛΛΛϕ⎪⎪⎭⎫⎝⎛=⎪⎪⎭⎫ ⎝⎛⋅⎪⎪⎭⎫ ⎝⎛=⋅⎪⎪⎭⎫⎝⎛=⎪⎪⎭⎫ ⎝⎛=⋅≠⋅=⋅⋅4312432132144321142343213214432114234321))(()(t s t s s t t s i s t i t s X t s t s X 则例如律。

即置换的乘法无交换。

一般地，为上的一个置换，且定义仍是，置换的乘法和上的置换设⎪⎪⎭⎫ ⎝⎛=⎪⎪⎭⎫ ⎝⎛=⎪⎪⎭⎫⎝⎛=-n k k k k s k k k k n s n n I n n X ΛΛΛΛΛΛ3213213213213211321的逆置换为为恒等置换。

称{}，称为置换群。

乘法运算下构成一个群在置换的的置换组成的集合，是由集合设G X t t t G m ,,,21Λ=⎭⎬⎫⎩⎨⎧⎪⎪⎭⎫ ⎝⎛⎪⎪⎭⎫ ⎝⎛⎪⎪⎭⎫ ⎝⎛⎪⎪⎭⎫ ⎝⎛⎪⎪⎭⎫ ⎝⎛⎪⎪⎭⎫ ⎝⎛=312321,123321,231321,213321,132321,3213213S S n X n次对称群，记作法下构成一个上的全体置换在置换乘集合POJ 2369 Permutations 求置换P 的秩k （order ）：P k =IPOJ 1026 Cipher 求置换P 的k 次幂P k 。

波利亚数学解题思想在有余数除法中的应用波利亚数学是数论中一个重要的分支领域，它以法国数学家波利亚的名字命名，主要研究整数的性质和规律。

而在有余数除法中，波利亚数学解题思想也可以得到应用，帮助我们解决某些数论问题。

本文将从波利亚数学的基本概念出发，介绍它在有余数除法中的应用，并举例说明其解题方法。

我们来简单介绍一下波利亚数学的一些基本概念。

波利亚数学主要研究整数的性质和规律，其中最为著名的应用便是质数分布。

波利亚提出了一个关于素数分布的猜想，即一个给定的区间内，素数的分布大致遵循一个对数规律。

这一猜想成为了数学界长期关注的问题，直到20世纪才由数学家梅特拉斯证明。

在有余数除法中，我们经常会遇到一些数字之间的关系问题，例如同余方程、同余定理等。

而波利亚数学的思想可以为我们提供一些思路和方法，帮助我们解决这类问题。

在同余方程中，我们需要找到满足特定条件的整数解，而波利亚数学提供了一些解题思想来帮助我们寻找这些解。

波利亚数学中一个重要的概念是模运算，即将一个整数除以另一个正整数得到的余数。

在模运算中，我们可以得到很多有用的信息，例如同余关系、模运算的性质等。

通过模运算，我们可以将一些复杂的问题简化为求解同余方程或者利用模运算的性质来得到一些结论。

下面我们来举一个例子来说明波利亚数学在有余数除法中的应用。

假设我们需要解决如下同余方程：求解x满足x ≡ 3 (mod 7)x ≡ 4 (mod 9)这个问题可以通过波利亚数学的思想来解决。

我们可以利用模运算的性质将这两个同余方程合并为一个方程。

由中国剩余定理，我们知道这两个方程等价于一个模m=n1*n2=7*9=63的方程，并且这个方程有解。

接下来，我们利用模运算的性质，可以通过一些简单的计算来得到具体的解。

通过以上例子，我们可以看到波利亚数学的思想在有余数除法中的应用是非常有效的。

波利亚数学还可以在解决一些数论问题中发挥作用。

我们经常会遇到一些关于素数的问题，例如素数分布、素数性质等。

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)的最高次项系数和均分常数之间的关系；它的推导带来了多项式展开及求和等等的方法，且它在许多数学领域都有重要的应用，比如组合数学、统计学、离散数学等等。

所以，该定理已经被广泛应用于实际问题的解决上。

离散数学中的图论与组合数学离散数学是数学的一个分支领域，研究离散化的结构和对象，而图论和组合数学则是离散数学中的两个重要分支。

本文将探讨图论和组合数学的基本概念和应用。

一、图论图论是研究图及其性质和应用的数学分支。

图是由一组顶点和连接这些顶点的边组成的数学结构。

具体来说，图由顶点的集合和边的集合构成，顶点间的边表示了它们之间的关系。

1.1 图的基本概念在图论中，我们经常会遇到以下几个基本概念：顶点：图中的一个节点或一个元素，用于表示一个实体或一个抽象的对象。

边：连接顶点的线段，表示顶点之间的关系。

路径：由边连续连接的顶点序列。

回路：起点和终点相同的路径。

距离：两个顶点间的路径长度。

连通性：图中任意两个顶点之间存在路径。

1.2 图的应用图论在现实生活和计算机科学中都有广泛的应用，其中一些重要的应用包括：网络分析：图论可用于分析社交网络、互联网和公共交通网络等复杂的网络结构。

电路设计：图论可以帮助设计电路和优化电路的布局。

路线规划：图论可应用于解决最短路径和旅行商问题等。

二、组合数学组合数学是一门研究离散结构的数学分支，主要研究离散对象的计数、排列、组合和选择等问题。

它涉及到排列组合、图论、图表以及递归等数学技术。

2.1 排列与组合排列是从给定对象中选取若干个并按照特定顺序排列的方式，而组合则是从给定对象中选取若干个但不考虑顺序的方式。

排列与组合的计数问题在实际应用中经常出现，比如：从n个数中选取m个不同的数，有多少种选择方式？从n个人中选取m个人组成一个团队，有多少种不同的团队组合方式？2.2 图论与组合数学的联系图论和组合数学有着紧密的联系，它们互相补充和借鉴。

图的着色问题是图论和组合数学中的一个重要问题。

着色问题可以简单地理解为如何用有限数量的颜色为图中的每个顶点染色，使得相邻的顶点颜色不同。

另一个联系是组合数学中的波利亚定理，它可以用于计算图的数量。

波利亚定理告诉我们，一个n个顶点的图中存在多少个不同的子图。

波利亚不等式的简证及推广
波利亚不等式是一个著名的数学定理，它最早是由18世纪法国数学家波利亚
提出的；它概括地表达了当一个函数,f(x)定义在实数段上，满足函数值在正负定
义域上单调递减的条件时，所有的端点小x的加权平均值的值都小于函数值的条件。

在原始的波利亚不等式中，函数f(x)有实数值，小x有n个实数。

它可以被
推广到复数的情况，假设函数f(z)是一个复数函数，它的定义域是(ζ，)；在定
义域上，具有单调递减的性质，满足f|>f；那么可以证明下面的复数波利亚不等
式成立：
左侧部分：Σ∣zn∣⏊f(zn) ≤ Σ∣zn∣f(z)+Σ∣zn∣⏊f(zn)
右侧部分：Σ∣zn∣f(z) ≤ Σ∣zn∣f(zn)+Σ∣zn∣⏊f(zn)
其中，Σ|zn|f(zn)表示所有的取值的加权平均值，Σ|zn|⏊f(zn)表示所有取
值的加权平均值，z表示函数f(z)在定义域上取得最小值，n表示实数被取得多少
个子域，即实数被分门帝n次。

经过扩展后的波利亚不等式，既对复数函数f(z)这种复杂形式的函数具有广
泛的应用价值，也可以用于多元函数定义域上的递减函数。

总之，波利亚不等式是一个强大的数学定理，虽然它最初是用来回答函数小x
加权平均值的一个简单的定理，但经过推广，它的研究用途已经极为广泛，被用来作为一种优化技巧，被广泛应用于科学技术、电脑科学、金融经济和工程及许多其他领域。

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，求其方案数。