《组合数学（第3版）》课后习题答案

（第二版获第三届电子部优秀教材二等奖)卢开澄 卢华明 编著　本书是《组合数学》（第二版）的修订版。全书共有6章，分别是：排列与组合，母函数与递推关系，容斥原理与鸽巢原理，贝恩塞特引理与波利亚定理，区组设计与编码，组合算法与复杂性分析。本书内容取舍得当，理论联系实际。　本书是计算机系本科生和研究生的教材，也可作为数学专业师生的教学参考书。

目录

• 引言ⅩⅤ第1章排列与组合1
• 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任意阶齐次递推关系137
• 2.11一般线性常系数非齐次递推关系145
• 2.12应用举例151
• 2.13非线性递推关系举例176
• 2.13.1司特林(Stirling)数176
• 2.13.2卡特朗（Catalan)数184
• 2.13.3举例189
• 2.14递推关系解法的补充195
• 习题198第3章容斥原理与鸽巢原理207
• 3.1容斥原理207
• 3.1.1引论207
• 3.1.2容斥原理的两个基本公式208
• 3.1.3例子212
• 3.2棋盘多项式和有限制条件的排列219
• 3.2.1有限制的排列219
• 3.2.2棋盘多项式219
• 3.2.3有禁区的排列问题223
• 3.3广义的容斥原理228
• 3.3.1问题的引入228
• 3.3.2特殊情况229
• 3.3.3一般公式231
• 3.3.4广义容斥原理的证明235
• 3.4广义容斥原理的若干应用238
• 3.5第二类司特林数展开式242
• 3.6错排问题的推广244
• 3.7容斥原理在数论上的应用246
• 3.7.1埃拉托逊斯(Eratosthenes)筛法246
• 3.7.2欧拉函数(n)248
• 3.8n对夫妻问题249
• 3.9反演公式252
• 3.9.1反演定理252
• 3.9.2若干应用256
• 3.10鸽巢原理259
• 3.10.1问题的引入259
• 3.10.2一般的鸽巢原理260
• 3.11鸽巢原理的推广265
• 3.11.1推广形式之一265
• 3.11.2例265
• 3.11.3推广形式之二274
• 3.12拉蒙赛(Ramsey)数275
• 3.12.1拉蒙赛问题275
• 3.12.2拉蒙赛数281
• 习题285第4章贝恩塞特(Burnside)引理与波利亚(Pólya)定理294
• 4.1群的概念294
• 4.1.1定义294
• 4.1.2群的基本性质297
• 4.2置换群299
• 4.3循环、奇循环与偶循环305
• 4.4贝恩塞特(Burnside)引理312
• 4.4.1若干概念312
• 4.4.2重要定理315
• 4.4.3例320
• 4.5波利亚(Pólya)定理324
• 4.6举例327
• 4.7母函数形式的波利亚定理336
• 4.8图的计数342
• 4.9波利亚定理的若干推广348
• 习题354第5章区组设计与编码357
• 5.1问题的提出357
• 5.2拉丁方与正交的拉丁方359
• 5.2.1问题的引入359
• 5.2.2正交拉丁方及其性质361
• 5.3域的概念363
• 5.4Galois域GF(pn)365
• 5.5正交拉丁方的构造368
• 5.6正交拉丁方应用举例372
• 5.7均衡不完全的区组设计(BIBD)374
• 5.7.1基本概念374
• 5.7.2(b,v,r,k,t)设计374
• 5.8区组设计的构成方法380
• 5.9斯梯纳三元系383
• 5.10科克曼女生问题386
• 5.11有限射影空间387
• 5.11.1二维的射影几何387
• 5.11.2有限域上的射影空间391
• 5.12阿达玛(Hadamard)矩阵392
• 5.13编码理论的基本概念398
• 5.14对称二元信道402
• 5.15纠错码404
• 5.15.1最近邻法则404
• 5.15.2汉明不等式405
• 5.16若干简单的编码406
• 5.16.1重复码406
• 5.16.2奇偶校验码407
• 5.17线性码408
• 5.17.1生成矩阵与校验矩阵408
• 5.17.2关于生成矩阵和校验矩阵的定理412
• 5.17.3译码步骤413
• 5.18汉明码413
• 5.19陪集译码法416
• 5.20BCH码420
• 5.21其他编码技术简介423
• 5.21.1利用区组设计纠错码423
• 5.21.2利用阿达玛矩阵进行编码424
• 习题426第6章组合算法与复杂性分析432
• 6.1归并排序算法432
• 6.1.1归并排序432
• 6.1.2举例433
• 6.1.3复杂性分析434
• 6.2快速排序435
• 6.2.1算法的描述435
• 6.2.2复杂性分析438
• 6.3Ford\|Johnson排序法440
• 6.4求第k个元素444
• 6.5排序网络446
• 6.5.101原理447
• 6.5.2Bn网络448
• 6.5.3复杂性估计449
• 6.5.4Batcher奇偶归并网络451
• 6.6快速傅里叶变换(FFT)453
• 6.6.1问题的提出453
• 6.6.2预备定理454
• 6.6.3快速算法455
• 6.6.4复杂性分析459
• 6.7DFS算法460
• 6.7.1算法的引入460
• 6.8判决树465
• 6.8.1银币问题465
• 6.8.2举例468
• 6.9渡河问题472
• 6.10TSM问题与分支定界法473
• 6.11多段判决478
• 6.11.1问题的提出478
• 6.11.2最佳原理481
• 6.11.3矩阵链积问题481
• 6.12NPC问题483