





定价:19.8元
印次:3-11
ISBN:9787302045816
出版日期:2002.08.22
印刷日期:2006.10.18
图书责编:张民
图书分类:教材
(第二版获第三届电子部优秀教材二等奖)卢开澄 卢华明 编著 本书是《组合数学》(第二版)的修订版。全书共有6章,分别是:排列与组合,母函数与递推关系,容斥原理与鸽巢原理,贝恩塞特引理与波利亚定理,区组设计与编码,组合算法与复杂性分析。本书内容取舍得当,理论联系实际。 本书是计算机系本科生和研究生的教材,也可作为数学专业师生的教学参考书。
电子计算机的出现是20世纪的大事,它改变了我们这个世界的面貌。可以毫不夸张地说,它的影响遍及所有的角落,几乎无处不感觉到它的存在。数学更不例外。严格地说,电子计算机本身就是近代数学的辉煌成就。将计算机与数学割裂开来,既不合理也不可能。组合学也就是在计算机科学蓬勃发展的刺激下崛起的,从而成为近若干年来最活跃的数学分支。它研究的问题有的可追溯到欧拉和哈密尔顿等18世纪的数学家,但它成为一个新的分支还是近若干年的事。它从与计算机科学相结合中获得了广阔的发展空间,从而也为计算机科学奠定了理论基础。 什么是计算机科学呢?有的学者将它定义为研究算法的一门学科。研究算法无疑是计算机科学的重要领域,也是本丛书的核心内容,贯穿始终。组合学家在20世纪70年代初建立的算法复杂性“NP理论”,至今仍然令无数计算机科学工作者与数学工作者为之折腰。 计算机科学里的组合学内容十分广泛。本丛书涉及组合分析、图论、组合算法、近代密码学、编码理论及算法复杂性等7部分。 组合分析是算法的理论基础。组合分析之于组合算法犹如数学分析于与计算数学,众所周知,前者是后者的理论根基。 图论原来是组合数学这个“家族”的主要成员,只因它已成长壮大,故自立门户独立出去。 算法复杂性的NP理论是近30年的一大成就。研究表明,对于一类叫做NPC类的困难问题,至今都不存在有效算法,但它们难度相当,只要其中任何一个找到多项式解法,则全体都获得解决;或证明它们根本不存在有效办法。不论是前者还是后者都还看不见露到海平面上的桅杆塔,它吸引了众多的有志之士。密码学是其中十分引人入胜的分支。如若设计好的密码,对它的破译等价于某一NPC类...
1.1基本计数法则1
1.1.1加法法则、乘法法则及排列与组合1
1.1.2应用举例2
1.2一一对应5
1.3排列11
1.4圆周排列15
1.5组合16
1.6排列的生成算法23
1.6.1序数法23
1.6.2字典序法26
1.6.3换位法28
1.7组合的生成30
1.8允许重复的组合与不相邻的组合31
1.8.1允许重复的组合31
1.8.2不相邻的组合33
1.9组合的解释34
1.10应用举例46
1.11司特林(Stirling)公式58
1.11.1瓦利斯(Wallis)公式58
1.11.2司特林公式的证明60
习题63第2章母函数与递推关系68
2.1母函数的引入68
2.2母函数的性质73
2.2.1若干基本的母函数74
2.2.2基本公式75
2.3整数的拆分80
2.4费勒斯(Ferrers)图像85
2.5关于拆分数p(n)的讨论88
2.5.1欧拉公式88
2.5.2拆分数估计式94
2.6指数型母函数97
2.6.1问题的提出97
2.6.2指数型母函数的引入99
2.7递推关系举例104
2.8Fibonacci(费卜拉契)数列115
2.8.1问题的提出115
2.8.2问题的解116
2.8.3若干等式119
2.8.4优选法121
2.9解线性常系数递推关系特征根法126
2.9.1二阶线性常系数齐次递推关系126
2.9.2一阶、二阶线性常系数非齐次递推关系133
2.9.3叠加原理136
2.10任意阶齐次递推关系13...