《组合数学讲义(南基洙 大连理工大学应用数学系)》由会员分享，可在线阅读，更多相关《组合数学讲义(南基洙 大连理工大学应用数学系)（143页珍藏版）》请在金锄头文库上搜索。
1、 组合数学讲义组合数学讲义 南基洙南基洙 大连理工大学应用数学系大连理工大学应用数学系 目 录 目 录 第一章 引言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 第四章 抽屉原理
2、 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、有
3、限仿射几何105 2、拉丁方108 3、构作有限射影平面 113 习题 116 第十章 线性群的计数定理及其应用118 1、群在集合上的作用 118 2、Polya计数定理 119 ? 3、有限域上线性群的计数定理 125 4、构造结合方案 128 5、构造认证码 133 习题 138 参考文献 140 名词索引141 - II - 第一章 引言 第一章 引言 第一章 引言 组合数学是一门历史悠久的数学分支,它发源于数学的消遣和游戏.不管是为了消遣,还是为了数学的 美学兴趣,过去研究过的许多组合数学问题,对于今天的纯粹数学或应用数学来说都是非常重要的.特别是 随着数字计算机技术的飞速发展,组合
4、数学更成为现代数学中非常重要的一个研究分支,而且它的影响正 在迅速扩大. 近年来计算机技术对于我们生活的影响越来越大.由于计算机闪电般的计算速度,它已经能够解决以 前许多我们不敢想象的大规模的计算问题.但是计算机它本身不能自己进行运算,它需要以一定的程序为 基础,而这些程序的基础又往往是由一些组合算法构成的,因此组合数学在其中起着非常重要的作用.今天 的组合数学不仅仅能应用于传统的数学应用领域-物理学等,也已应用在社会科学和生物学等一些新的 领域.那么什么是组合数学?它又具体研究那些问题呢? 组合数学所研究的就是一组事物安排成各种各样模式的问题.它研究的核心问题既然是按照一定的规 则来安排一些
5、元素.那么,首先我们要考虑的问题是符合规则的元素安排是否存在？其次,如果符合规则的 元素安排存在,则按此规则的安排的方法数是多少？再有,怎样才能把这样的安排求出来？最后,如果有按 此规则的最优的标准,则需要求出此最优的安排等等.上述几个问题我们依次称为存在性问题、计数问题、 构造问题和最优化问题. 1、 洛书的构造 1、 洛书的构造 相传在四千多年前的中国,大禹为了治理好滔天的洪水,领导人民日夜奔忙,三过家门而不入.在大禹 治好那汹涌澎湃的洪水之后,就有一龙马自河中跃出,献给大禹一幅河图,另外在洛河里也有一神龟背驮了 洛书献给大禹.据传这两部书都包含了治国安邦、平治天下的大道理.以至于在论语中
6、,圣人孔子因为 当时的世风日下,人心不古,而感叹“河不出图”. 如果洛书上的每个圆点代表 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 上面构造洛书的方法记载在我国宋朝大数学家杨辉撰写的续古摘奇算经上.杨辉称这种图为“纵 横图”,他是世界上第一个对这方面进行深入研究的数学家.后来国外的许多数
7、学家也先后开始研究杨辉研 究过的这种洛书,并且将其进行了推广,即把 1,2,个自然数放进由个小正方形组成的正方形方阵 里,而且要求纵、横、对角线及斜对角线上数字的和都相等,满足这些条件的方阵被称之为“阶纵横图”, 在国外称其为“阶魔方阵”或“阶幻方”. 2 n 2 n n nn 在中国古代,由于 3 阶幻方中配置的 9 个数是如此的均衡和完美,它产生了极大的美学冲击,以至使我 们的先人认为其中包含了某种至高无上的真理.如我们的先人把 3 阶幻方和“九宫说”等同起来、把 3 阶 幻方用来占卜吉凶,以及把它视为举行国事大典的建筑格局等等.自从幻方从中国传到世界其他地区之后, 引起了人们的广泛兴趣和
8、重视,一代又一代的学者对它进行了不懈的研究,取得了非常丰富的成果,有关的 文献资料不胜枚举-“单单是关于幻方的著作就足够办一个规模可观的图书馆了”(J.R.Newman).虽然 关于幻方的研究开展的很早,但是目前还没有一般的普遍适用的方法.有些想知道的结论也不是十分清楚, 如阶幻方的个数等.在此我们仅就幻方的构造问题作一简单的介绍. n 容易验证下面的图构成 4 阶幻方 162313 511108 97612 414151 注记注记,在上图中将对角线及斜对角线上的数字对称换位后,我们可以得到按顺序添成的下面图: - - 2 第一章 引言 1234 5678 9101112 13141516 现
9、在我们利用杨辉使用过的方法构造 5 阶纵横图： 1 6 2 11 7 3 16 12 8 4 21 17 13 9 5 22 18 14 10 23 19 15 24 20 25 6 2 11 7 3 16 12258 4 21 17 13 9 5 22 181 14 10 23 19 15 24 20 11247 203 16 12258 4 21 17 13 9 5 22 181 14 10 236 192 15 11247203 41225816 17513219 101811422 23619215 - - 3 第一章 引言 我们可以利用构造 3、5 阶幻方的方法构造奇数阶幻方,即(2
10、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 注
