《组合数学算法一》PPT课件.ppt

一、引言中国是最早研究排列组合的国家。周易就被认为是世界上最早讨论排列组合的书，其中的八卦和六十四卦阵，就属于重复排列问题。我国的洛书有“幻方”的最早记载，幻方是组合数学中构造问题之例，据说“河图”就是一种幻方。历史走着曲折的道路。一些历史悠久的学科，在经历了漫长的不被人们重视的岁月之后，又会重新焕发出青春的活力。组合数学的历史就是如此。它同算术、代数、几何一样古老，源远流长，但却没有它们那种持续不断的发展历程。这不能归咎于它的衰老，而只能解释成历史的青睐尚未到来。历史是公正的，人类创造的每一项伟绩都不至于被遗忘。近几十年来，这门古老的学科年轻了，活跃起来了，开始以前所未有的速度向前发展着，不断取得丰富的成果。促使这种变化出现的最主要动力是二十世纪的计算机科学的迅速发展。计算机科学，数字通讯理论，规划论和试验设计都要求人们把注意力转向研究离散变量的数学学科，其中之一便是组合数学。这种来自尖端学科领域的刺激的出现，激起了这门古老学科领域中从未有过的发展势头，使它一反长期沉睡的状态，成为本世纪最活跃的数学学科之一。,二、排列组合全部组合分析公式的推导基于以下两原理,（一）加法原理如果完成一件事情有n种方式A1，An，每种方式中又有mi种方法（1in），且AiAj=，则要完成此事共有一年365天划分为12个月一个国家划分一些省一个班分为几个小组例1离开福州，飞机有60个航班，火车有10个车次，轮船有2个班次，汽车有100个班次。离开福州的方式有60+10+2+100=172,加法原理的例子补充|A|，|B|分别为集合A，B中元素的个数补例1现有长度分别为1，2，n的细木棍各一根，可以以它们为边构成多少个不同的三角形？解：记三角形三边长度为a，b，c，不妨设ac。以c的长度将这些三角形分类，则可分为c=4，c=5，c=n这样一些不同的类，分别将各类三角形的集合记作B4，B5，Bn，则它们构成了所有三角形的集合B的一个分划，则有而在Bk中，三角形三边分别为ak，所以这些点由a=b，a+b=k，b=k三条直线所围成的三角形区域内部。所以当k为偶数时，有当k为奇数时，有所以n为偶数时，n为奇数时，,补例2设x表示不超过实数x的最大整数。求方程x2-x2=(x-x)2在区间1xn中根的个数。解：显然x=n是方程的一个根。下面我们再分别求出方程在区间1x2，2x3，n-1xn中的根的个数。为此设这些区间中根的个数为B1，B2，Bn-1，即以Bk表示方程在区间kxk+1中根的全体。在kxk+1中，有x=k，如果再记p=x-x，就有0p1。于是原来方程就可以写成(k+p)2-(k+p)2=p2即k2+2kp=k2+2kp+p2注意到k2+2kp+p2=k2+2kp+p2知上式即为2kp=2kp+p2该式右端是一个整数，所以左端也应为整数，即2kp是整数由于k为整数，0p1，所以只有当p=0，1/2k，2/2k，(2k-1)/2k时，等式才能成立。从而知原方程在此区间中恰有2k个根，即|Bk|=2k于是由加法原理知原方程在区间1xn中共有|B1|+|B2|+|Bn-1|+1=2+4+2(n-1)+1=n2-n+1个根加法原理用途极多，如将其与其他数学原理，例如抽屉原理结合起来，就可以推出许多有趣的数学命题。,（二）乘法原理如果完成一件事情要分几个步骤B1，B2，Bn，而每个步骤Bi有mi种方法(1in)，那么完成这事共有例2某人在进小学、初中、高中时都分别有二所学校可选择，那么他就有多种不同的方式从小学到高中。共8种=2x2x2例3多项式乘积(a1+a2+a3)(b1+b2+b3+b4)(c1+c2+c3+c4+c5+c6)(d1+d2)的展开式中有多少不同的项。解：展式中每项均形如aibjckdl，其中i1,2,3，j1,2,3,4，k1,2,3,4,5,6，l1,2由乘法原理，展式中共有3x4x6x2=144（项）例4在ABC的三边上分别取n1，n2，n3个点（不含A,B,C），在三边上的点中各取一个作为三角形的顶点，可以得到多少个不同的三角形？n1n2n3,*例5每个完全平方数都有奇数个正约数证：设n=m2是一个完全平方数而m的素因数分解式为m=，那么n=记A1=0，1，2r1，A2=0，1，2r2，Ak=0，1，2rk那么n的每一个正约数就都具有形式其中j1A1，jkAk，故由乘法原理n一共有|A1|A2|Ak|=(2r1+1)(2r2+1)(2rk+1)个正约数共有奇数个。例6（结合程度较高的例子）一种单向行驶的汽车，满载为25人，全程共设14个车站，中途的每一个车站均可上下乘客。由不同起点到达不同终点的乘客各应购买不同的车票。在一次单程行驶中，车上最多可卖出多少种不同的车票？解：车上应准备由每个车站到达它后面每一个车站的车票，所以一共应准备13+12+2+1=91（种）（加法原理之应用）,但它们不可能在一次单程行驶中都卖得出去。我们来考虑其中以前面7个车站中的某一个作为起点，而以后面7个车站中的某一个作为终点的车票，就应当为7x7=49（种）之多（最多种）。凡持这种车票的乘客都要乘车通过7号车站与8号车站之间的路程。但由于汽车满员为25人，所以此类车票中至少会有49-25=24（种）卖不出去。（即只有25人，最多只能卖出25张此类票）这样一来，车上最多只能卖出91-24=67（种）。（三）排列1.线排列2.圆排列3.重排列1.线排列（排列）排列的字面意思是列队。“最基本”例子就是：“要从n个不同的物体中选出k件（1kn）来排成一列，共有多少种不同的排法？”高中数学课本中就以此为排列的定义基础。称“从n个不同元素中，任取k（kn）个元素按照一定的顺序排成一列，叫做从n个不同元素中取出k个元素的一个排列。”（即线排列）,其实这种定义有一定的局限性，容易使人误将“排成一列”理解为排列问题的本质。最早研究排列问题的国家是印度，早年出现在印度书籍中的例子有：湿婆神的十只手拿十件东西：绳子、钩子、蛇、鼓、豆盖骨、三叉戟、乐架、匕首、箭、弓。这十件东西是她的象征物，如果将这十种东西交换，共有多少种不同的方式？正象哈利神四只手交换狼牙棒、铁饼、莲与贝壳一样。这里湿婆神的十只手和哈利神的四只手都不是成一列分布，而是分布在躯干的两侧的，所以所拿的东西都不是“按一定的顺序排成一列”。现解决一开始提出的问题。先从n个物体中任取一个放在排首，有n种不同选法。再从余下的n-1个中选出一个来放在排二，有n-1种。这样逐个选出，直到n-k+1个物体中选出一个放在排尾，有n-k+1种不同方法。由乘法原理，有n(n-1)(n-k+1)=为约定符号人们通常把n(n-1)21记为n！,现代组合学中对排列下了一个更为妥当的定义：从n个不同元素中有次序地选取k（1kn）个，叫做从n个不同元素中取出k个元素的一个排列。又当k=n时，就叫做一个全排列。有人们又规定0！=1容易的大家都知道了计算。例把自然数1，2，k2排成一个方阵表。从表中任意取一个数，然后删去这个数所在的行和列中的全部数字，再从剩下的(k-1)2个数组成的方阵表中任意取出一个数，并删去这个数所在的行和列中的所有数字。这样一直进行下去，一共可取表中k个不同的数字，它们构成了集合1，2，k2的一个k阶子集。问题是：用这样的方法，共可取得1，2，k2中多少个不同的由k个数字组成的子集？这些子集中的k个数字之和各是多少？12kk+1k+22k(k-1)k+1(k-1)k+2k2,解：因为一旦取得一个数字后，这个数字所在行与列即划之，所以所取得的k个数字中，不可能有两个同行的，也不可能同列。换言之，即k个数字都是取自不同行也不同列，故有k！个。又因为aij=(i-1)k+j，而每个子集中k个数字中都包含每一行，每一列的数字各一个，所以每个子集中k个数字之和均为,2.圆排列从集合S=a1，an的n个不同元素中取出r个元素，按某种次序（如逆时针方向），排成一个圆圈，称这样的排列为圆排列。这里相同的顺序被视同一排列。如：这种圆排列的个数=如果r=n，则例：4对兄弟站成一圈，要求每对兄弟相邻，有多少种不同站法？解：先让哥哥站一圈，有=3！=6（种）不同排法。然后，让4位弟弟插入其中，每人均可在其兄左边亦可右边，故均有2种方式。所以共有6x2=96（种）*例：用4种不同颜色给小正方形木块的4条边着色，每边各涂一种颜色，能有多少种不同的着色花样？解：此处不仅只考虑4种颜色的相对顺序，而且木块可以翻边，因此没有逆时针顺序与顺时针顺序的不同区分。故一共有=3种。,A,B,=,D,C,D,A,B,C,*例：在右图的圆周上均匀地布列着n个方框。今有n个非零实数a1，a2，an满足a1+a2+an=0，要将它们分别填入圆周上的n个方框。证明：至少有(n-1)！种填法可以使得自某个方框A开始按逆时针方向，逐个累加方框中的数字，得出的每一步和数都非负。证：设已将n个数字填入方框，并且自A开始按逆时针依次填入ai1，ai2，ain。现来逐个累加它们得到S1=ai1，S2=ai1+ai2，Sn=ai1+ai2+ain。如果这些S1，Sn0，则相应的填法合乎要求。如果S1，Sn中有负数，则只要将所填数字集体顺时针旋转若干位置，即可得合乎要求的填法。现证之。设Sk=min(S1，Sn)，Sk0,A,ai1,ai2,由于Sk的最小性，知这就是说，只要将所填数字集体顺时针旋转后，使得方框A中的数字变成aik+1（保持各数间原来的相对顺序），即可使得自A中数字开始，按逆时针方向逐个累加数字，所得出的每一步和数均非负。以上证明的事实表明，无论按什么样的相对顺序将数填入方框，都可通过整体旋转这些数而得到一种合乎要求的填数方式，且保持数的相对顺序不变。于是可以断言，合乎要求的填法数目不会少于这n个数字进行圆排列的数目，即(n-1)！种。,3.重排列重排列即一个依次进行的多重选取过程，并且每一重选取都在一个集合中进行，已经选过的元素还可再选。（这是对乘法原理的最直接应用）重复排列的最简单例子是电话号码，某市的电话号码是7位，每位上的数码无非是0，1，9，而且不同位上的数码可以是相同的。如7566783，7533338，7818888，共有107种以上是无限重排列中国是世界上最早讨论重排列的国家，易经中所收集的资料可以追溯到公元前七世纪。易经中有两个符号，叫做“阳爻”和“阴爻”，易经讨论了由这样两个符号形成的3个字符和6个字符的所有可能情况。其中3个字符是：阳阳阳、阳阳阴、阳阴阳、阴阳阳阳阴阴、阴阳阴、阴阴阳、阴阴阴这刚好是由集合阳，阴中依次进行的3重选取过程的所有可能情况。或者叫做由阳、阴二者中每次选取3个重复排列的所有情况。由于其数目共2x2x2=8（个），故易经称之曰“八卦”。相应的六个字符的共有26=64（种），称为“六十四卦”。例公元八世纪，我国流传过一个问题，据说是一个和尚提出的：围棋盘上有361个位置，既可放黑子，或白子，又可空着，共有多少种不同的情况。3361（种）,