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