组合数学基础李乔

第十一讲 Burnside 引理与 Polya 定理

§1 (置换群基本概念) (本页） §2 (Burnside 引理与循环指标) §3 (Burnside 引理的应用) §4 (Polya 定理及其应用)

Redfield-Polya 定理是组合数学理论中最重要的定理之一．自从 1927 年 Redfield 首次运用 group reduction function 概念，现在称之为群的循环指标（circle index of a group），至今 60 多年来，他在许多实际计数问题上得到了广泛的应用，它以置换群为理论基础，与生成函数有机地结合在一起，揭示了一类具有组合意义的计数的规律性．

抽象地说在一集合内，定义了一个等价关系，人们往往关心由这个等价关系所决定的等价类的数目，Refield-Polya 理论就是为解决这类问题而发展起来的复杂计数理论．

为了帮助读者理解，本章例举了较多的实例． §1 置换群的基本概念

设有限集合 换 是从 到自身上的

，集合中的元素称为“点”．集合 上的一个置对应的映射：

设 是集合 上的另一个置换，置换 与 的乘积定义为复合映射：

例 1 设 上的二个置换：

求乘积

《组合数学》 第一章 组合数学基础

第1章 组合数学基础

1. 排列组合的基本计数问题 2. 多项式系数的计算及其组合意义 3. 排列组合算法 1.1 绪 论

（一） 背景

起源：数学游戏

幻方问题：给定自然数1, 2, …, n2，将其排列成n阶方阵，要求每

行、每列和每条对角线上n个数字之和都相等。这样的n阶方阵称为n阶幻方。每一行（或列、或对角线）之和称为幻方的和（简称幻和）。

例：3阶幻方，幻和＝(1＋2＋3＋?＋9)/3＝15。

关心的问题 存在性问题：即n阶幻方是否存在？

计数问题：如果存在，对某个确定的n，这样的幻方有多少种？ 构造问题：即枚举问题，亦即如何构造n阶幻方。

8 3 4 1 5 9 6 7 2 2 9 4 7 5 3 6 1 8 奇数阶幻方的生成方法：

一坐上行正中央，依次斜填切莫忘， 上边出格往下填，右边出格往左填， 右上有数往下填，右上出格往下填。

例：将2，4，6，8，10，12，14，16，18填入下列幻方：

1/51 姜建国

《组合数学》 第一章 组合数学基础

《组合数学》 第一章 组合数学基础

第1章 组合数学基础

1. 排列组合的基本计数问题 2. 多项式系数的计算及其组合意义 3. 排列组合算法 1.1 绪 论

（一） 背景

起源：数学游戏

幻方问题：给定自然数1, 2, …, n2，将其排列成n阶方阵，要求每

行、每列和每条对角线上n个数字之和都相等。这样的n阶方阵称为n阶幻方。每一行（或列、或对角线）之和称为幻方的和（简称幻和）。

例：3阶幻方，幻和＝(1＋2＋3＋?＋9)/3＝15。

关心的问题 存在性问题：即n阶幻方是否存在？

计数问题：如果存在，对某个确定的n，这样的幻方有多少种？ 构造问题：即枚举问题，亦即如何构造n阶幻方。

8 3 4 1 5 9 6 7 2 2 9 4 7 5 3 6 1 8 奇数阶幻方的生成方法：

一坐上行正中央，依次斜填切莫忘， 上边出格往下填，右边出格往左填， 右上有数往下填，右上出格往下填。

例：将2，4，6，8，10，12，14，16，18填入下列幻方：

1/51 姜建国

《组合数学》 第一章 组合数学基础

ACM暑期集训 组合数学（1） 数论

1 约数和倍数

设 a，b为整数，a≠0.

若有一整数c，使得 b = ac，则称 a是b的因数 或称a是b的约数 称b为是a的倍数

并称a整除b，记为a|b

整数的整除性有下列基本性质： ① 1|a ② a|0 ③ a|a

④ 若a|b且b|c，则a|c.

⑤ 若a|b，则对任意整数m，有am|bm ⑥ 若ac|bc且c≠0，则a|b

⑦ 若a|b且a|c，有 a|(b+c) 整数的表示法：

带余形式 b=aq+r 0≤r<|a|

十进制表示形式 b?ann?1n10?an?110????a0

标准分解式 b?pa1aan1p22??pn 2的乘方与奇数之积式 b?2mt(t为奇数)

2 最大公约数和最小公倍数 最大公约数GCD(a,b)

若GCD(a,b)=1，称a与b互素。 最小公倍数LCM(a,b)

ab = GCD(a,b)×LCM(a,b)

辗转相除法（Euclid算法）

如果m除以n的商是q，余数是r，即 m=nq+r，则 GCD(m,n)=GCD(n,r) int gcd(int a,int b) int GCD(in

第二章作业答案

7. 证明，对任意给定的52个整数，存在两个整数，要么两者的和能被100整除，要么两者的差能被100整除。

证明 用100分别除这52个整数，得到的余数必为0, 1,?, 99这100个数之一。将余数是0的数分为一组，余数是1和99的数分为一组，?，余数是49和51的数分为一组，将余数是50的数分为一组。这样，将这52个整数分成了51组。由鸽巢原理知道，存在两个整数分在了同一组，设它们是a和b。若a和b被100除余数相同，则a?b能被100整除。若a和b被100除余数之和是100，则a?b能被100整除。

11. 一个学生有37天用来准备考试。根据过去的经验，她知道她需要不超过60小时的学习时间。她还希望每天至少学习1小时。证明，无论她如何安排她的学习时间（不过，每天都是整数个小时），都存在连续的若干天，在此期间她恰好学习了13小时。 证明 设从第一天到第i天她共学习了ai小时。因为她每天至少学习1小时，所以

a1,a2,?,a37和a1?13,a2?13,?,a37?13都是严格单调递增序列。因为总的学习时间

不超过

60

小时，所以a37?60，a37?13?73。a1,a2,?,a37,

a1?13,a2?13,?,a37?

卢开澄组合数学--

§3.1 容斥原理引论第三章 容斥原理和鸽巢原理 §1 容斥原理引论例 [1,20]中2或3的倍数的个数 [解] 2的倍数是：2,4,6,8,10, 12,14,16,18,20。 10个

卢开澄组合数学--

§3.2 容斥原理3的倍数是：3,6,9,12,15, 18。 6个 但答案不是10+6=16 个，因为6, 12,18在两类中重复计数，应减 去。故答案是：16-3=13

卢开澄组合数学--

§3.2 容斥原理容斥原理研究有限集合的交或并 的计数。 [DeMorgan定理] 论域U,补集 AA {x | x U 且x A} ,有

(a)

A B A B

(b) A B A B

卢开澄组合数学--

§3.2 容斥原理证：(a)的证明。 设 x A B ,则 x A B x A B 相当于 x A和 x B 同时成立，亦即x A B x A B

(1)

卢开澄组合数学--

§3.2 容斥原理反之，若 x A B,即x A和x B

故 x A和x B.亦即x A B x A B

习题二

2.1 证明：在一个至少有2人的小组中，总存在两个人，他们在组内所认识的人数相同。 证明：

假设没有人谁都不认识：那么每个人认识的人数都为[1,n-1]，由鸽巢原理知，n个人认识的人数有n-1种，那么至少有2个人认识的人数相同。

假设有1人谁都不认识：那么其他n-1人认识的人数都为[1,n-2]，由鸽巢原理知，n-1个人认识的人数有n-2种，那么至少有2个人认识的人数相同。

假设至少有两人谁都不认识，则认识的人数为0的至少有两人。

2.2 任取11个整数，求证其中至少有两个数的差是10的整数倍。

证明：对于任意的一个整数，它除以10的余数只能有10种情况：0，1，…，9。现在有11个整数，由鸽巢原理知，至少有2个整数的余数相同，则这两个整数的差必是10的整数倍。 2.3 证明：平面上任取5个坐标为整数的点，则其中至少有两个点，由它们所连线段的中点的坐标也是整数。 2.3证明：

有5个坐标，每个坐标只有4种可能的情况：（奇数，偶数）；（奇数，奇数）；（偶数，偶数）；（偶数，奇数）。由鸽巢原理知，至少有2个坐标的情况相同。又要想使中点的坐标也是整数，则其两点连线的坐标之和为偶数。因为 奇数+奇数 = 偶数 ； 偶数+偶数=偶

填空题

1．将5封信投入3个邮筒，有_____243 _种不同的投法．

2．5个男孩和4个女孩站成一排。如果没有两个女孩相邻，有 43200 方法．

3．22件产品中有2件次品，任取3件，恰有一件次品方式数为__ 380 ______． 4．(x?y)6所有项的系数和是_64_ _．答案：64 5．不定方程x1?x2?x3?2的非负整数解的个数为_ 6 ___．

6．由初始条件f(0)?1,f(1)?1及递推关系f(n?2)?f(n?1)?f(n)确定的数列

{f(n)}(n?0)叫做Fibonacci数列

7．（3x-2y）20 的展开式中x10y10的系数是

c1020310(?2)10．

8．求6的4拆分数P4(6)? 2 ．

?5,f(5)?，试求89．已知在Fibonacci数列中，已知f(3)?3,f(4)Fibonacci数f(20)?10946

10．计算P4(12)?

P4(12)??Pk(12)?P1(8)?P2(8)?P3(8)?P4(8)k?14?P1(8)?P2(8)??Pk(5)??Pk(4)?1?4?5?5?15

k?1k?13411

习题二 证明：在一个至少有2人的小组中，总存在两个人，他们在组内所认识的人数相同。证明： 假设没有人谁都不认识：那么每个人认识的人数都为[1,n-1]，由鸽巢原理知，n个人认识的人数有n-1种，那么至少有2个人认识的人数相同。 假设有1人谁都不认识：那么其他n-1人认识的人数都为[1,n-2]，由鸽巢原理知，n-1个人认识的人数有n-2种，那么至少有2个人认识的人数相同。假设至少有两人谁都不认识，则认识的人数为0的至少有两人。

任取11个整数，求证其中至少有两个数的差是10的整数倍。证明：对于任意的一个整数，它除以10的余数只能有10种情况：0，1，…，9。现在有11个整数，由鸽巢原理知，至少有2个整数的余数相同，则这两个整数的差必是10的整数倍。证明：平面上任取5个坐标为整数的点，则其中至少有两个点，由它们所连线段的中点的坐标也是整数。2.3证明：有5个坐标，每个坐标只有4种可能的情况：（奇数，偶数）；（奇数，奇数）；（偶数，偶数）；（偶数，奇数）。由鸽巢原理知，至少有2个坐标的情况相同。又要想使中点的坐标也是整数，则其两点连线的坐标之和为偶数。因为 奇数+奇数 = 偶数 ； 偶数+偶数=偶数。因此只需找以上2个情况相同的点。而已证明：

第五章 Pólya计数理论

1. 计算（123）（234）（5）（14）（23）,并指出它的共轭类.

解：题中出现了5个不同的元素：分别是：1，2，3，4，5。即|Sn|＝5。

(123)(234)(5)(14)(23)?12345??12345??12345?

???23145????13425????43215?????????12345??12345????34125????43215?? ?????12345????21435?? ???(12)(34)(5)

（5）（12）（34）的置换的型为1122而Sn中属于1122型的元素个数为个其共轭类为

（5）（14）（23），（5）（13）（24），（1）（23）（45），（1）（24）（35）， （1）（25）（34），（2）（13）（45），（2）（14）（35），（2）（15）（34）， （3）（12）（45），（3）（14）（25），（3）（15）（24），（4）（12）（35）， （4）（13）（25），（4）（15）（24）

2. 设D是n元集合,G是D上的置换群.对于D的子集A和B,如果存在??G,

使得B?{?(a)|a?A},则称A与B是等价的.求G的等价类的个数.