组合数学讲义 南基洙 大连理工大学应用数学系
组合数学讲义 南基洙 大连理工大学应用数学系
目录 第一章引言 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
第一章引言 现在我们利用杨辉使用过的方法构造5阶纵横图: 22 18 14 10 19 12258 22 181|14 1225816 175|13219 10181|142 236192|15
第一章 引言 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 现在我们利用杨辉使用过的方法构造 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 12 25 8 4 21 17 13 9 5 22 18 1 14 10 23 19 15 24 20 11 24 7 20 3 16 12 25 8 4 21 17 13 9 5 22 18 1 14 10 23 6 19 2 15 11 24 7 20 3 4 12 25 8 16 17 5 13 21 9 10 18 1 14 22 23 6 19 2 15 - - 3
第一章引言 我们可以利用构造3、5阶幻方的方法构造奇数阶幻方,即m(=2k+1)阶幻方存在 对于偶数阶幻方存在性的构造方法,我们将分两种情形进行介绍.首先,考虑阶数n=4k时的构造方法 -对角线方法.此时我们完全可以仿照前面4阶幻方的构造技巧,构造n=4k阶幻方.在此仅以8阶幻方为 例说明对角线构造方法 下面的图示可以说明8阶幻方是如何得到的 2|3 6067 9 12135 2021 29 注记:在上图中将主对角线及斜对角线上的元素对称换位,短线上的元素逆时针方向移动8个格,则可 以得到按数字顺序添画的图 53637383940 4142434445464748 其次,我们介绍阶数n=4k+2时幻方的构造方法.在研究幻方的历史中,一个很有意思的现象是,人们 很早就掌握了奇数阶和阶数n=4k的幻方的构造方法,而阶数n=4k+2的幻方的构造方法是直到1918年 才由数学家R 在此我们仅以6,10阶为例说明构造的方法.容易验证下面的图是一个6阶幻方 319222272 2833171015
第一章 引言 我们可以利用构造 3、5 阶幻方的方法构造奇数阶幻方,即 n k ( 2 1) = + 阶幻方存在. 对于偶数阶幻方存在性的构造方法,我们将分两种情形进行介绍.首先,考虑阶数 时的构造方法 ---对角线方法.此时我们完全可以仿照前面 4 阶幻方的构造技巧,构造 n = 4k n = 4k 阶幻方.在此仅以 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 其次,我们介绍阶数 n k = 4 + 2时幻方的构造方法.在研究幻方的历史中,一个很有意思的现象是,人们 很早就掌握了奇数阶和阶数 n = 4k 的幻方的构造方法,而阶数 n k = 4 + 2的幻方的构造方法是直到 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
第一章引言 30534121416 43629131811 下面我们说明上面的6阶幻方是如何得到的 首先,将6×6的方格图形分成4个区域:A,B,C,D,其中的每个区域由3×3的方格组成,如图 其次,令a=n63,然后分别用数字1…32=9:32+1=10,…,2×32=18 2×32+1=19,…,3×32=27;3×32+1=28…,4×32=36构造3阶幻方添入A,B,C,D4个区域 357212325 492‖222720 21416 313629131811 最后,第一步,在A区的中间一行选定第2个元素,在A区其它行选定第一个元素;第二步,在D区选定 与A区相应位置的元素;第三步,调换A区和D区中选定的对应元素 3516261924 30534121416 让我们再看一下10阶幻方的构造过程 首先,分区,每个区域是由5×5的方格组成
第一章 引言 30 5 34 12 14 16 4 36 29 13 18 11 下面我们说明上面的 6 阶幻方是如何得到的. 首先,将6 6 × 的方格图形分成 4 个区域: ABCD ,,, ,其中的每个区域由3 3 × 的方格组成,如图 A C D B 其次,令 6 3 2 2 n a === ,然后分别用数字 2 1, ,3 9 " = ; ; ; 构造 3 阶幻方添入 4 个区域; 2 2 3 1 10, , 2 3 18 += × = " 2 2 2 3 1 19, ,3 3 27 × += × = " 2 3 3 1 28, ,4 3 36 × += × = " 2 ABCD ,,, 8 1 6 26 19 24 3 5 7 21 23 25 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 7 21 23 25 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
第一章引言 其次,令a=”,然后分别用数字1…,a2;a2+1…,2×a2;2xa2+1…,3×a2:3×a2+ 构造5阶幻方添入A,B,C,D4个区域 235714161735557646 10|12|19213|60|62|697153 111825296168755259 92997683904249263340 98|80828991148|303239 93100 8436435027 最后,第一步,在A区的中间一行从第2个元素始选定k(n=4k+2)个元素,在A区其它行从第一个 元素始选定k个元素;第二步,在D区选定与A区相应位置的元素;第三步,在C区的最后一列开始,在每 行选定k-1个元素,在B区选定与C区相应位置的元素;调换A区和D区,B区与C区中选定的对应元 98807141673555764 8x|1923s0e69128 8693|252961687552134 172476839042492633|65 796139597|29311384512 111810077843643502759 事实上,关于阶数为奇数的幻方,我们完全可以采用杨辉的构造方法得到由于我们可以将整数按与整 数4的关系分成4类:4k,4k+1,4+2,4k+3,k∈Z.而其中的两类数为奇数,其中的一类为4的倍数,余 下的一类为余数是2的偶数.所以通过上面的构造过成,我们得到 定理1.1如果n≥3,则n阶幻方是存在的 定理1.22阶幻方不存在
第一章 引言 A C D B 其次,令 2 n a = ,然后分别用数字 ; 2 1, , " a 2 2 a a +1, , 2 " × ; 2 2 2 1, ,3 ×a a + × " ; 构造 5 阶幻方添入 4 个区域; 2 2 3 1, , 4 ×+ × a a " ABCD ,,, 17 24 1 8 15 67 74 51 58 65 23 5 7 14 16 73 55 57 64 66 4 6 13 20 22 54 56 63 70 72 10 12 19 21 3 60 62 69 71 53 11 18 25 2 9 61 68 75 52 59 92 99 76 83 90 42 49 26 33 40 98 80 82 89 91 48 30 32 39 41 79 81 88 95 97 29 31 38 45 47 85 87 94 96 78 35 37 44 46 28 86 93 100 77 84 36 43 50 27 34 最后,第一步,在 A 区的中间一行从第 2 个元素始选定 ( k n k = 4 + 2 )个元素,在 区其它行从第一个 元素始选定 个元素;第二步,在 区选定与 区相应位置的元素;第三步,在C 区的最后一列开始,在每 行选定 个元素, 在 A k D A k −1 B 区选定与C 区相应位置的元素;调换 区和 区, A D B 区与C 区中选定的对应元 素. 92 99 1 8 15 67 74 51 58 40 98 80 7 14 16 73 55 57 64 41 4 81 88 20 22 54 56 63 70 47 85 87 19 21 3 60 62 69 71 28 86 93 25 2 9 61 68 75 52 34 17 24 76 83 90 42 49 26 33 65 23 5 82 89 91 48 30 32 39 66 79 6 13 95 97 29 31 38 45 72 10 12 94 96 78 35 37 44 46 53 11 18 100 77 84 36 43 50 27 59 事实上,关于阶数为奇数的幻方,我们完全可以采用杨辉的构造方法得到.由于我们可以将整数按与整 数 4 的关系分成 4 类: .而其中的两类数为奇数,其中的一类为 4 的倍数,余 下的一类为余数是 2 的偶数.所以通过上面的构造过成,我们得到 4 ,4 1,4 2,4 3, kk k k kZ + + +∈ 定理 1.1 如果 n ≥ 3 ,则 n 阶幻方是存在的. 定理 1.2 2 阶幻方不存在. - - 6
第一章引言 证明假设存在2阶幻方,设其形如下图 a3 a4 则由2阶幻方的定义,a1,a2,a3,a4,应该满足下面的条件:1≤a≤4,其中i=12,34.而且a≠a,当 i≠j时.又应该有 a1+a2=a3 将上面两式整理,得到a2-a3=a3-a2,即a2=a3,矛盾 定理1.3如果n阶幻方存在,则在n阶幻方中每行、每列、对角线及斜对角线上整数的和为 n2+1) 证明由于n阶幻方中所有整数的和是1+2++2:(2+,所以n阶幻方中每行、每列及对角 (n2+1) 线上整数的和恰为—2 n(m2+) 定理1.4在3阶幻方中数字5一定在中间,既 证明假设添出的3阶幻方为 其中1≤a,≤9,a 则 +a4+ao=15 a2+a4+a8=15 a4+a。=15
第一章 引言 证明 假设存在 2 阶幻方,设其形如下图 1 a 2 a a3 4 a 则由 2 阶幻方的定义, 1 a , 2 a , a3 , 4 a ,应该满足下面的条件： ≤ ai ≤ 41 ,其中i = 4,3,2,1 .而且 ≠ aa ji 当 i ≠ j 时.又应该有 4231 4321 aaaa aaaa +=+ + = + , 将上面两式整理,得到 −=− aaaa 2332 ,即 = aa 32 ,矛盾. 定理 1.3 如果 n 阶幻方存在,则在n 阶幻方中每行、每列、对角线及斜对角线上整数的和为 ( ) 2 1 2 nn + . 证明 由于 n 阶幻方中所有整数的和是 2 1 2 + + + " n = ( ) 2 1 22 nn + ,所以 阶幻方中每行、每列及对角 线上整数的和恰为 n 2 2 ( 1) 2 n n n + ( ) = 2 1 2 nn + . 定理 1.4 在 3 阶幻方中数字 5 一定在中间,既 5 证明 假设添出的 3 阶幻方为 a1 a2 a3 4 a a5 a6 a7 a8 其中 ≤≤ 91 , .则 ai ≠ aa ji ⎪ ⎪ ⎩ ⎪ ⎪ ⎨ ⎧ =++ =++ =++ =++ 15 15 15 15 654 753 852 951 aaa aaa aaa aaa , a9 - - 7