组合数学讲义
南基洙
大连理工大学应用数学系
目 录
第一章 引言………………………………………………………………………………………………1
1、洛书的构造………………………………………………………………………………………………1
2、费波那契数列……………………………………………………………………………………………8
3、有趣的走路问题………………………………………………………………………………………10
4、有限射影平面…………………………………………………………………………………………11
习题………………………………………………………………………………………………………13
第二章 多项式定理及其应用 …………………………………………………………………………16
1,排列,组合的概念………………………………………………………………………………………16
2、组合数的整数性质 ……………………………………………………………………………………20
3、二项式定理及其应用…………………………………………………………………………………22
4、二项式系数的单峰性质………………………………………………………………………………25
5、多项式定理……………………………………………………………………………………………26
习题………………………………………………………………………………………………………28
第三章 分划与Stirling数………………………………………………………………………………29
1,分划和第二类Stirling数 ……………………………………………………………………………29
2,第一类Stirling数 ……………………………………………………………………………………31
3、分划的简单应用 ………………………………………………………………………………………36
4、对称多项式 ……………………………………………………………………………………………40
习题………………………………………………………………………………………………………41
第四章 抽屉原理 ………………………………………………………………………………………43
1、抽屉原理及其应用 ………………………………………………………………………………43
2、Ramsey 数及其性质 ……………………………………………………………………………46
3、简单构造实数……………………………………………………………………………………47
习题………………………………………………………………………………………………………49
第五章 容斥原理及其应用 ……………………………………………………………………………50
1、容斥原理 ………………………………………………………………………………………………50
2,Mobius 函数……………………………………………………………………………………………55
3、线性不定方程的非负解 ………………………………………………………………………………57
4、计数整数点 ……………………………………………………………………………………………60
习题……………………………………………………………………………………………63
第六章 差分与有限级数 ………………………………………………………………………………65
习题 ……………………………………………………………………………………………………… 70
第七章 线性齐次递归关系 …………………………………………………………………………72
1、递归关系的例子………………………………………………………………………………………72
2、特征方程没有重根…………………………………………………………………………………74
3、特征方程有重根……………………………………………………………………………………76
4、非齐次递归关系…………………………………………………………………………………79
5、母函数及其应用………………………………………………………………………………………81
习题………………………………………………………………………………………………………93
- I -
第八章 代数学基础 ……………………………………………………………………………………95
1、群论基础………………………………………………………………………………………………95
2、环论基础………………………………………………………………………………………………98
3、域论基础………………………………………………………………………………………………100
习题………………………………………………………………………………………………………104
第九章 有限几何与拉丁方 ……………………………………………………………………………105
1、有限仿射几何…………………………………………………………………………………………105
2、拉丁方………………………………………………………………………………………………108
3、构作有限射影平面 ………………………………………………………………………………113
习题 ……………………………………………………………………………………………………116
第十章 线性群的计数定理及其应用…………………………………………………………………118
1、群在集合上的作用 …………………………………………………………………………………118
2,Polya计数定理 ……………………………………………………………………………………119
3、有限域上线性群的计数定理 ………………………………………………………………………125
4、构造结合方案 ………………………………………………………………………………………128
5、构造认证码 …………………………………………………………………………………………133
习题 ……………………………………………………………………………………………………138
参考文献 ………………………………………………………………………………………………140
名词索引…………………………………………………………………………………………………141
- II -
第一章 引言
第一章 引言
组合数学是一门历史悠久的数学分支,它发源于数学的消遣和游戏.不管是为了消遣,还是为了数学的美学兴趣,过去研究过的许多组合数学问题,对于今天的纯粹数学或应用数学来说都是非常重要的.特别是随着数字计算机技术的飞速发展,组合数学更成 为现代数学中非常重要的一个研究分支,而且它的影响正在迅速扩大,
近年来计算机技术对于我们生活的影响越来越大.由于计算机闪电般的计算速度,它已经能够解决以前许多我们不敢想象的大规模的计 算问题.但是计算机它本身不能自己 进行运算,它需要以一定的程序为基础,而这些程序的基础又往往是由一些组合算法构成的,因此组合数学在其中起着非常重要的作用.今天的组合数学不仅仅能应用于传统的数学应用领域---物理学等,也已应用在社会科学和生物学等一些新的领域.那么什么是组合数学?它又具体研究那些问题呢?
组合数学所研究的就是一组事物安排成各种各样模式的问题.它研究的核心问题既然是按照一定的规则来安排一些元素.那么,首先我们要考虑的问题是符合规则的元素安排是否存在?其次,如果符合规则的元素安排存在,则按此规则的安排的方法数是多少?再有,怎样才能把这样的安排求出来?最后,如果有按此规则的最优的标准,则需要求出此最优的安排等等.上述几个问题我们依次称为存在性问题、计数问题、
构造问题和最优化问题,
1,洛书的构造
相传在四千多年前的中国,大禹为了治理好滔天的洪水,领导人民日夜奔忙,三过家门而不入.在大禹治好那汹涌澎湃的洪水之后,就有一龙马自河中跃出,献给大禹一幅河图,另外在洛河里也有一神龟背驮了洛书献给大禹.据传这两部书都包含了治国安邦、平治天下的大道理.以至于在《论语》中,圣人孔子因为当时的世风日下,人心不古,而感叹“河不出图”,
如果洛书上的每个圆点代表 1,则我们把洛书的图形用阿拉伯数字写出来就是下面的 阶正方形阵列
33×
4 9 2
3 5 7
8 1 6
我们容易验证其中每行、每列、对角线及斜对角线上三个数字的和都是 15.现在我们就来说明上面的
- - 1
第一章 引言
图是如何得到的,
1
4 2
7 5 3
8 6
9
4 9 2
7 5 3
8 1 6
4 9 2
3 5 7
8 1 6
上面构造洛书的方法记载在我国宋朝大数学家杨辉撰写的《续古摘奇算经》上.杨辉称这种图为“纵横图”,他是世界上第一个对这方面进行深入研究的数学家.后来国外的许多数学家也先后开始研究杨辉研究过的这种洛书,并且将其进行了推广,即把 1,2,…,个自然数放进由 个小正方形组成的正方形方阵里,而且要求纵、横、对角线及斜对角线上数字的和都相等,满足这些条件的方阵被称之为,阶纵横图”,
在国外称其为,阶魔方阵”或,阶幻方”,
2
n
2
n
n
n n
在中国古代,由于 3 阶幻方中配置的 9 个数是如此的均衡和完美,它产生了极大的美学冲击,以至使我们的先人认为其中包含了某种至高无上的真理.如我们的先人把 3 阶幻方和“九宫说”等同起来、把 3 阶幻方用来占卜吉凶,以及把它视为举行国事大典的建筑格局等等.自从幻方从中国传到世界其他地区之后,
引起了人们的广泛兴趣和重视,一代又一代的学者对它进行了不懈的研究,取得了非常丰富的成果,有关的文献资料不胜枚举---“单单是关于幻方的著作就足够办一个规模可观的图书馆了”(J.R.Newman).虽然关于幻方的研究开展的很早,但是目前还没有一般的普遍适用的方法.有些想知道的结论也不是十分清楚,
如 阶幻方的个数等.在此我们仅就幻方的构造问题作一简单的介绍,n
容易验证下面的图构成 4 阶幻方
16 2 3 13
5 11 10 8
9 7 612
414151
注记,在上图中将对角线及斜对角线上的数字对称换位后,我们可以得到按顺序添成的下面图,
- - 2
第一章 引言
1234
5678
9101 12
13 14 15 16
现在我们利用杨辉使用过的方法构造 5 阶纵横图,
1
6 2
1 7 3
16 12 8 4
21 17 13 9 5
2 18 14 10
23 19 15
24 20
25
6 2
1 7 3
16 12258 4
21 17 13 9 5
2 181 14 10
23 19 15
24 20
1 247 203
16 12 25 8 4
21 17 13 9 5
22 18 1 14 10
236 192 15
11 24 7 20 3
41225816
17 5 13 21 9
10 18 1 14 22
23619215
- - 3
第一章 引言
我们可以利用构造 3、5 阶幻方的方法构造奇数阶幻方,即 (2 1)nk= + 阶幻方存在,
对于偶数阶幻方存在性的构造方法,我们将分两种情形进行介绍.首先,考虑阶数 时的构造方法
---对角线方法.此时我们完全可以仿照前面4阶幻方的构造技巧,构造
4n= k
k4n= 阶幻方.在此仅以8阶幻方为例说明对角线构造方法,
下面的图示可以说明 8 阶幻方是如何得到的,
64 2 3 61 60 6 7 57
9 55 54 12 13 51 50 16
17 47 46 20 21 43 42 24
40 26 27 37 36 30 31 33
32 34 35 29 28 38 39 25
41 23 22 44 45 19 18 48
49 15 14 52 53 11 10 56
8 58 59 5 4 62 63 1
注记:在上图中将主对角线及斜对角线上的元素对称换位,短线上的元素逆时针方向移动 8 个格,则可以得到按数字顺序添画的图,
1 2 3 4 5 6 7 8
9 10 11 12 13 14 15 16
17 18 19 20 21 22 23 24
25 26 27 28 29 30 31 32
33 34 35 36 37 38 39 40
41 42 43 44 45 46 47 48
49 50 51 52 53 54 55 56
57 58 59 60 61 62 63 64
其次,我们介绍阶数 4nk2= + 时幻方的构造方法.在研究幻方的历史中,一个很有意思的现象是,人们很早就掌握了奇数阶和阶数 的幻方的构造方法,而阶数4n= k 24nk= + 的幻方的构造方法是直到1918年才由数学家R.Strachey 给出,
在此我们仅以 6,10 阶为例说明构造的方法.容易验证下面的图是一个 6 阶幻方
35 1 6 26 19 24
3 32 7 21 23 25
31 9 2 22 27 20
8 28 33 17 10 15
- - 4
第一章 引言
30 534121416
4 36 29 13 18 11
下面我们说明上面的 6 阶幻方是如何得到的,
首先,将 的方格图形分成 4 个区域:,其中的每个区域由66×,,,ABCD 33× 的方格组成,如图
AC
DB
其次,令
6
3
22
n
a ===,然后分别用数字
2
1,,3 9= " ; ;; 构造 3 阶幻方添入 4 个区域;
22
3 1 10,,2 3 18+= × = "
22
23 119,,33 27×+= ×= "
2
33 1 28,,43 36×+= ×= "
2
,,,ABCD
8 1 6 26 19 24
3 5 7212325
4 9 2 22 27 20
35 28 33 17 10 15
30 32 34 12 14 16
31 36 29 13 18 11
最后,第一步,在 区的中间一行选定第2个元素,在 区其它行选定第一个元素;第二步,在 区选定与 区相应位置的元素;第三步,调换 区和 区中选定的对应元素,
A A D
A A D
35 1 6 26 19 24
3 32 7212325
31 9 2 22 27 20
8 28 33 17 10 15
30 5 34 12 14 16
4 36 29 13 18 11
让我们再看一下 10 阶幻方的构造过程,
首先,分区,每个区域是由 5 的方格组成; 5×
- - 5
第一章 引言
AC
DB
其次,令
2
n
a =,然后分别用数字 ;
2
1,,a "
22
1,,2aa+ ×