组合数学第一章[绪论].ppt

《组合数学第一章[绪论].ppt》由会员分享，可在线阅读，更多相关《组合数学第一章[绪论].ppt（29页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、组组合合数数学学第一章 绪论1.1 例：棋盘的完美覆盖1.2 1.2 例：切割立方体例：切割立方体1.3 1.3 例：幻方例：幻方1.4 1.4 例：例：NimNim取子游戏取子游戏 组合数学是一个古老而又年轻的数学分支。据传说，大禹在4000多年前就观察到神龟背上的幻方.绪论绪论 幻方可以看作是一个3阶方阵，其元素是1到9的正整数，每行、每列以及两条对角线的和都是15。519372486绪论绪论 北宋数学家（约11世纪）贾宪 著有黄帝九章细草、算法斅(xiao)古集（即“古算法导引”）都已失传。杨辉著详解九章算法（1261年）中曾引贾宪的“开方作法本源”图（即指数为正整数的二项式展开系数表，

2、现称“杨辉三角形”）和“增乘开方法”（求高次幂的正根法）。前者比pascal三角形早600年，后者比霍纳（William Geoge Horner，17861837）的方法（1819年）早770年。绪论绪论 1666年莱布尼兹所著组合学论文一书问世，这是组合数学的第一部专著。书中首次使用了组合论（Combinatorics）一词。组合数学的蓬勃发展则是在计算机问世和普遍应用之后。由于组合数学涉及面广，内容庞杂，并且仍在很快地发展着，因而还没有一个统一而有效的理论体系。这与数学分析形成了对照。绪论绪论 组合数学的一般描述组合数学的一般描述：研究离散结构的存在、记数、分析和优化等的一门学科。组合学

3、中的一般性问题组合学中的一般性问题：排列的存在性排列的记数和分类已知排列的性质和结构构造最优的排列绪论绪论 组合数学经常使用的最主要的方法是计数时的合理分类和组合模型的转换。掌握已知的原理已知的原理是基础，数学归纳数学归纳法法则是一种十分重要的技术，解决题目需要进行相当的训练训练。绪论绪论1.1 例：棋盘的完美覆盖1.问题2.一张mn棋盘是指一个具有mn个方格的国际象棋棋盘；一块多米诺骨牌是指有b个方格大小的块连接在一起构成的牌，称为b-牌（bomino，如1-牌、5-牌，2-牌即为通常的多米诺牌，即domino牌）。现考虑牌对棋盘的覆盖，如果存在恰好且不重叠的覆盖就是完美覆盖。绪论绪论 多米

4、诺骨牌完美覆盖等价于分子物理学中的二聚物问题，进而可演变到二分图的匹配理论。2.mn棋盘存在多米诺骨牌的完美覆盖吗？当且仅当m和n至少有一个是偶数时，mn棋盘存在多米诺骨牌的完美覆盖。例如，33棋盘不存在完美覆盖。绪论绪论3.剪去对角的88棋盘存在完美覆盖吗？显然，88棋盘存在完美覆盖，且覆盖方法有1200万种覆盖方法。剪去后，将方格按图 所示黑白相间涂色。显然，一张骨牌必然覆盖一黑一白 两格。若存在覆盖，黑格数必然 等于白格数。但图中有30白格而32黑格。绪论绪论4.mn棋盘存在b-牌的完美覆盖吗？分析1：存在完美覆盖的充分条件是b是m或n的因子。分析2：若b是素数且存在完美覆盖，则b必然是

5、m或n的因子。分析3：对任意的b，存在完美覆盖的充分必要条件是b是m或n的因子。绪论绪论证明：若非素数b除m和n的余数分别为r和s，则可表示成：m=pb+r，其中0rb-1n=qb+s，其中0sb-1 若r和s中某个为0，得证。不妨设r s，往证r=0。绪论绪论涂色。将棋盘上bb的块按下图所示方式涂色（颜色用数字表示）。123b-1 bb12b-1b-1 b12b-21212121221绪论绪论现在，利用以上涂色规则将mn棋盘涂色（图中假定b=4）。1234412334122341123441233412234112344123341223411234412334122341123412341

6、2341234123412341234412312344123123412mnpbqbsr绪论绪论显然，若存在完美覆盖，则图中b种颜色的任意一种所占方格的数量都是等同的。在图中，上面的pb行中每种颜色出现np次；在左下角的r行qb列中每种颜色出现rq次。即每种颜色出现np+rq次。现考虑右下角的rs小块。因rs，而从颜色1开始涂色，因此，每行中颜色1必然出现1次，共r次。为了保证每种的颜色数相同，其他的每种颜色也必须都出现r次，故应该有r*b个方格。绪论绪论其实，右下角的方格数是r*s，故：r*b=r*s若r0，有b=s，矛盾。得证。说明：mn棋盘必存在都能横放骨牌或竖放骨牌的完美覆盖。这样的

7、覆盖称为平凡覆盖。绪论绪论5.完美覆盖能否被切分？试说明：一个44棋盘总可以被切分成两块而不损坏任一块骨牌。实现切分的直线可称为断层线。若不存在切分，则图中x1、x2和x3都不是断层线，即每个都会切到骨牌。对于x1，它不能只切一个骨牌。否则，x1绪论绪论 第一行的3个余下方格不能都由横牌覆盖。即x1必须切割2块以上的骨牌。类似地，x2和x3也必须切割2块以上的骨牌。可见，覆盖中必须有6块以上的竖牌。同样地，对竖断层线则至少有6块以上横牌。说明，要想不损坏任一骨牌则至少要12块以上骨牌，但一个44棋盘的覆盖中只有8块骨牌。得证。绪论绪论1.2 1.2 例：切割立方体例：切割立方体问题：一个边长3

8、尺的立方体，要将其切割成27个边长1尺的立方体，至少需要切割多少次？初看较繁，可换一种 想法。显然，不用重排，6次 可切割出来。而中心的 小立方体的6个面都是切割后形成的面，故不能少于6次。即6次最少。绪论绪论1.3 1.3 例：幻方例：幻方1.问题2.前文已提及。一个n阶幻方是由1、2、n2组成的方阵，其每行、每列以及两条对角线元素和都相等。2.奇数阶幻方3.因为n2个整数之和为n2(n2+1)/2，故每行之和（称为幻和）为n(n2+1)/2。绪论绪论 可见，不存在2阶幻方。因为其和为5，对1来说，同行（或列）只能为4，而对角线放2或3都不能使和为5。当n为奇数时，有一种简单的构造方法。1置

9、1行中间；顺序将各数置于右上方位置。若当前数位于1行n列或当前数的右上角已填入了其它数，则下一个数填在当前数下方；若当前数的右上方超出了矩阵，则下一个数循环填在另一侧。绪论绪论 例：5阶幻方。偶数阶幻方较繁，可参考其它书籍。除了加幻方外，还有乘幻方等。17241823571446132010121921111825215162239绪论绪论1.4 1.4 例：例：NimNim取子游戏取子游戏1.问题2.两个人，面对k（k1）堆硬币，各堆的硬币数分别为n1、n2、nk。游戏的目的是取到最后一枚硬币，规则如下：3.(1)游戏人交替取走硬币；4.(2)轮到某人取子时，只能从其中的任一堆中取走任意多的

10、硬币，但至少取走一枚。取到含有最后一枚硬币者胜。绪论绪论2.方法3.直觉可知，胜负受硬币数目多少影响不大，但应与奇偶性有关。4.分析的一般规则：为了深入理解和强化直觉，往往可先考虑小的或特殊的情形，然后再扩展你的看法以解决一般的问题。5.绪论绪论A.两堆的情况(1)若两堆大小相同，先拿者负。后者模拟前者动作即可；(2)若两堆大小不同，先拿者胜。他只要从大堆中取子使其变成与小堆一样大。事实是：大小相同的堆是否为偶数。B.k2的一般情况任何一个整数可以表示成二进制形式，如57=25+24+23+20=(111001)2，可认为每个堆都由一些小的堆组成，小堆的大小为2i。绪论绪论对任意的i，2i大小

11、的子堆在任意一个堆中的个数只能为0或1。如果在某个堆中取子，至少会使一个子堆消失。对 n1、n2、nk大小的堆，可用二进制表示为（不足者在前面填0）：n1=asa2a1a0n2=bsb2b1b0nk=ese2e1e0可见，具有2i大小的子堆有ai+bi+ei个。如果每种子堆的个数都是偶数，称游戏是平衡的，否则称为非平衡的。绪论绪论结论：(1)若游戏平衡，先拿者负。只要取子，至少有一种子堆不平衡。后者只要再保持平衡即可；(2)若游戏非平衡，先拿者胜。他只要从最高的不平衡处着手使游戏平衡即可。可看一个实际例子。绪论绪论例：4-堆的Nim取子游戏，其中各堆的大小分别为7，9，12和15。23=822=421=220=1大小为7的堆0111大小为9的堆1001大小为12的堆1100大小为15的堆1111