组合数学及其应用

第0章引言 组合数学，又称组合论、组合分析、组合学，在数学游戏和博弈中有它的历史渊源，在工程学、化学、生物学、统计学、运筹学、密码学、计算机科学等学科都有广泛的应用.同时兼顾纯粹数学和应用数学两个领域，是组合数学的特色之一.内容的离散性、问题的趣味性、解决问题方法的多样性，是组合数学的独有特色. 组合数学是一个古老而又年轻的数学分支.说它古老，是因为早在4000多年前我国的“河图洛书”的传说就与组合数学有关，历史上许多著名的数学难题与组合数学有关，诸如Konigsberg七桥问题、四色问题、Kirkman女学生问题、正交拉丁方问题等.这些问题吸引了一代又一代青年学子，把他们引进了组合数学研究的殿堂，使得组合数学这门学科不断完善和发展.由于这门学科在自然科学的众多学科里、管理科学的很多分支中及工程学的许多技术领域里，尤其在计算机科学的理论和应用上近几十年得到迅猛飞速的发展，所以在信息时代的今天人们越来越认识到组合数学的重要性.组合数学是一块充满珍花异草的圣地，足以使观赏者流连忘返，更能激发观赏者研究的欲望和热情. 0.1什么是组合数学 我们先举一个典型例子来了解组合数学探讨的到底是什么：把一张白纸划分成n个区域，称两个区域是相邻的如果它们有公共线段，现在把每一个区域都染上一种颜色，条件是相邻的两个区域都不能同色，对这n个区域染色是否用四种颜色就够了？组合数学的问题常常是如此，先规定一件要做的事情，如用四种颜色给区域染色，这件事多半都是很容易做到，而且有各种各样的做法，但我们同时加上了一些约束条件，如相邻区域不得同色，情形就大不一样了.现在有些做法符合条件有些不符合条件，我们问符合条件的做法有多少种，或者问有没有符合条件的做法，或者要找出一种好的做法. 组合数学是研究离散结构的存在、计数、构造和优化等问题的一门学科.组合数学所研究的问题是按照一定的模式将集合的元素进行配置安排），通常反复出现的是以下四种类型的问题： （Ⅰ）配置的存在性； （Ⅱ）配置的计数或近似估计； （Ⅲ）配置的构造或分类； （Ⅳ）配置的优化. 如上述例子中集合的元素是n个区域，配置是用四种颜色染n个区域，规定的模式是相邻的两个区域都不能同色.当配置并非显然存在或不存在时，首要的问题是证明或否定它的存在；当配置显然存在或已证明存在时，需要无重复、无遗漏地求出这种配置的个数，当配置个数的计数存在困难时可对其进行近似估计，随着计算机科学的迅猛发展，为了充分利用计算机资源，需要对配置的计数问题给出算法，因此组合数学成了算法的理论基础；如有可能还要给出配置的构造或按照某种性质对配置进行分类.按照一定的模式将集合的元素进行配置可看作是一种组合结构，组合结构又可看作一种数学模型，社会实践中的一些实际问题可抽象为数学模型，因此对数学模型的研究是十分有意义的.当组合结构确定后，能否进一步优化是组合优化的重要研究内容. 0.2组合问题举例 0.2.1配置的存在性（存在性问题） 如果研究对象在满足某些条件下才能进行下一步安排，当对象是否符合条件并非显然存在或者显然不存在时，首要解决的就是证明存在或者否定存在. 例如，分组密码算法扩散层设计时，经常用到矩阵作为基本单位.设A为n阶方阵，I为n阶单位阵，则满足的方阵A称为对合矩阵.由于对合矩阵的逆矩阵就是本身，所以为了加密和解密过程的一致性，对合矩阵自然被重点关注.那么对于二元域上的n阶方阵，是否一定存在对合矩阵呢？这个问题似乎容易回答，利用穷举方法或者利用特征值构造方法可以容易构造出二元域上n阶对合矩阵.但扩散层设计还有一个性质，就是要求不动点越少越好，也就是点经过矩阵乘积作用后的结果仍是该点，具有这种性质的点的数量越少越好，此时问题变成对于二元域上的n阶对合矩阵，其不动点个数能否达到*低？通过下面简单的证明，我们知道这种要求是完全不存在的. 性质0.1设A为二元域上的n阶对合矩阵，则其不动点个数不小于. 证 这个性质说明二元域上的n阶对合矩阵的不动点个数相当多，几乎占空间的一半，要求同时满足对合性质和不动点个数低，这种配置不存在.从这个例子可以看出，满足一定条件的配置并不总是存在的，这就给我们提出了新的问题：什么条件下配置才是存在的？这就是配置的存在性研究的根本问题，有些时候这些问题的回答并不显而易见. 0.2.2配置的计数（计数问题） 如果所要求的配置存在，则可能有多种不同的配置，这又经常给我们提出这样的问题：有多少可能的配置方案？如何对配置方案进行合理分类？ 例如，银行卡在操作的时候都需要输入6位数字的口令，这里口令个数一共是106个.我们在利用RAR加密一个压缩文档时，同样输入6位口令，这时要求必须有1个小写字母、一个大写字母、一个特殊字符，这时可能的口令又是多少个呢？ 这个时候可以输入的小写字母26个，大写字母26个，数字10个，特殊字符32个，若没有特殊限制此时6位口令共计（26×2+10+32）6=946.加上限制之后，计数变为10×26x26×（94）3. 对于一般的计数问题，多数情形需要研究两个配置是否属于同一个等价数学模型，也就是先研究清楚同类配置判定的数学方法，再给出配置方案分类的计算公式.虽然任何组合问题的计数都有方法可循，但有时需要做大量研究，此时其计数的难度也是巨大的，如果问题有明显的特解，则可以追寻特解的规律进行分类并计算出解的个数. 例如，手机的九宫格图案解锁总共能绘出多少种图案？这个问题相当于把先行后列标记为1，2，3，4，5，6，7，8，9这九个数字的9个点排成3阶矩阵，且合法的密码要求如下： 密码的长度至少为4，*长为9; 密码中不能有重复的数字出现，比如不能同时出现两个2; 密码相邻的数字必须在图形上是相连的，这样才符合手的滑动. 这个问题的计数就复杂得多，需要进行细致的分类研究，其*终结果是389112种，1.7节会详细讨论计算方法. 0.2.3配置的构造或分类（构造性问题） 幻方是古老且流行的数学游戏之一，一个n阶幻方是由数字，构成的矩阵，满足每行每列及两个对角线上的元素之和均为S，这个和数S称为幻和.因为，所以.与此相关的组合问题是确定可以构造n阶幻方的n的值以及寻找构造幻方的一般方法.不难验证不存在2阶幻方，而对于其他任意的n值，都可以构造出n阶幻方.容易给出3阶幻方. 有很多种特殊的幻方构造方法，这里介绍delaLoubere在17世纪发现的构造方法.当n为奇数时，有一种简单的方法来构造n阶幻方.首先把1放在*上面一行的中间位置，然后按下面规则把2，3， ，n这些数字沿一条由左下至右上的斜线相邻放置. （1）当一个数放在*上面一行的（1，k）位置，下一个数放在*下面一行的（n，k+1）位置 （2）当一个数放在*右边一列（kn，n）位置，下一个数放在*左边一列的（1，k-1）位置. （3）当遇到一个位置已经放置，或已经放在右上角位置，则下一个数就放在前一个数的正下方位置. 下面是一个5阶幻方 1992年，丁宗智在《幻方》一书中分别介绍了奇数阶、单偶数阶、双偶数阶幻方的多种构造方法，而且分别给出了这三种幻方的构造模型，然后利用构造模型分别构造出相应的2k+1阶、4k阶、4k+2阶幻方，有兴趣的读者可以参见该书. 在中国数学的发展历程中，我们能够看到有趣的数学、计算工具、棋类游戏都与幻方有着内在的联系.幻方对于近代科学的发展起着很大的作用，可应用到“建路”和“Jordan曲线”等的位置解析学及组合解析学.幻方在密码科学中也发挥着作用.例如，按幻方的置乱变换技术，可以将需保密的图像置乱后，再按幻方原理复原，这种置乱变换可以进行多次. 0.2.4配置的优化（优化问题） 很多应用问题有多种配置方案，不同的配置方案考虑的因素和产生的结果并不完全相同，在实际中我们多希望降低因素个数并提高结果精度，这就需要在一些方案中构造或者发现一些较优的方案配置.这类都是优化问题. 0.3典型组合问题举例 例如，在密码算法利用MILP方法分析时，会碰到用不等式刻画成本的问题.设n为正整数，Z2={0，1}，Z2n=Z2xZ2x xZ2为所有分量均在Z2上取值的n元组组成的集合.对任意给定集合Z2n的非空子集我们总可以用一组整系数线性不等式L完全刻画，也就是说，该线性不等式组在限制变元取值为0和1时，其解所构成的集合恰好等于A.例如，n=3，A={（000），（101），（011），（110）}.我们可以构造一线性不等式组L: 其由4个不等式组成.容易验证，上述线性不等式组L关于，的解集恰好为A给定上的非空子集A，求一整系数线性不等式组L，使得该线性不等式组在Z2n上的解集恰好等于4且要求L中不等式个数尽可能少.当集合A规模增大时，不等式组L并不容易发现，可以用逻辑条件模型和凸闭包的方法进行优化. 本书作为组合数学的基础教材，只涉及前三类问题，并且以计数方法为重点介绍组合数学的基本理论和方法，重点介绍数学归纳法、迭代方法、一一对应方法、组合含义法等基本计数方法.关于上面提到的优化问题，有兴趣的读者可以参考运筹学方面的教材. 0.3典型组合问题举例 0.3.1棋盘的完全覆盖 考虑一个8x8的棋盘，假设有足够多的形状相同的骨牌，骨牌的大小恰好能盖住棋盘的两方格.是否能用32张骨牌盖住棋盘的64个方格？如果能，称这样的配置为棋盘的完全覆盖.一般地，当m和n为何值时，mxn的棋盘能完全覆盖？ 0.3.2Konigsberg七桥问题 Konigsberg这座城市被河流划分为A，B，C，D四区，有七座桥连接这四个区.问能否从某一区出发，每一座桥经过一次且仅一次回到原区（图0.1）? 0.3.3四色猜想 在组合数学（图论）中，也许是在全部数学中，*出名的没有（用数学方法）解决的问题是著名的四色猜想.1872年，著名数学家凯利正式向数学学会提出四色猜想问题，从此四色猜想席卷全球，吸引了大量的数学家为之痴迷.任何一个数学家可以在五分钟之内将这个非凡的问题（也称为四色问题）向马路上的任何一个普通人讲清楚.在讲清楚之后，虽然两个人都懂得了这个问题，但是要想解决它却也无能为力. 四色猜想是：“在一个平面或球面上的任何一张地图只用四种颜色着色，使得具有一段公共边界的两个国家染上不同的颜色.每个国家必须由一个单连通的区域构成1976年6月，两位数学家在两台不同的电子计算机上，用了1200个小时，作了100亿个判断，结果没有一张地图是需要五色的，*终证明了四色定理，轰动了世界.当两位数学家发表他们的研究成果后，当地的邮局在当天发出的所有邮件上都加盖了“四色足够”的特制邮戳，以庆祝这困扰了人们一个多世纪的难题*终得到了解决.不过该方法就像是穷举法，姑且不论这两位数学家是否真的穷举了所有可能情况，相比严谨的理论证明，这种证明无法让人真正信服.四色猜想的理论证明还在继续 0.3.4 36军官问题 有36名军官，来自6个不同的团队，他们有6种不同的军衔.问能否把这36名军官排成一个6x6的方阵，使得每行和每列都是不同团队的军官并且军衔互不相同？ 这个问题是欧拉（Euler）在18世纪作为一个数学游戏提出来的.每名军官可用一个有序对（i，j）来表示，这里i表示他的军衔，j表示他所在的团队，i，j=1，2， ，6.这样36名军官对应36个有序对⑷j）.于是上述问题可表述为：排列这36个有序对（i，j）为一个6x6方阵，使得每行和每列的有序对中**个坐标和第二个坐标上数字1，2， ，6都出现.这样的方阵可以分成两个6x6的