组合数学算法(一).ppt

一、引言
中国是最早研究排列组合的国家。《周易》就被认为是世界上最早讨论排列组合的书,其中的《八卦》和《六十四卦》阵,就属于重复排列问题。我载,幻方是组合数学中构造问题之例,据说“河图”就是一种幻方。
历史走着曲折的道路。一些历史悠久的学科,在经历了漫长的不被人们重视的岁月之后,又会重新焕发出青春的活力。组合数学的历史就是如此。它同算术、代数、几何一样古老,源远流长,但却没有它们那种持续不断的发展历程。这不能归咎于它的衰老,而只能解释成历史的青睐尚未到来。历史是公正的,人类创造的每一项伟绩都不至于被遗忘。近几十年来,这门古老的学科年轻了,活跃起来了,开始以前所未有的速度向前发展着,不断取得丰富的成果。促使这种变化出现的最主要动力是二十世纪的计算机科学的迅速发展。计算机科学,数字通讯理论,规划论和试验设计都要求人们把注意力转向研究离散变量的数学学科,其中之一便是组合数学。这种来自尖端学科领域的刺激的出现,激起了这门古老学科领域中从未有过的发展势头,使它一反长期沉睡的状态,成为本世纪最活跃的数学学科之一。
二、排列组合全部组合分析公式的推导基于以下两原理
(一)加法原理
如果完成一件事情有n种方式A1,∙∙∙,An,每种方式中又有mi种方法(1≤i≤n),且Ai Aj=Ø ,则要完成此事共有

一年365天划分为12个月
一个国家划分一些省
一个班分为几个小组
例1 离开福州,飞机有60个航班,火车有10个车次,轮船有2个班次,汽车有100个班次。
离开福州的方式有60+10+2+100=172
加法原理的例子补充|A|,|B|分别为集合A,B中元素的个数
补例1 现有长度分别为1,2,∙∙∙,n的细木棍各一根,可以以它们为边构成多少个不同的三角形?
解:记三角形三边长度为a,b,c,不妨设a<b<c,则应有a+b>c 。以c的长度将这些三角形分类,则可分为c=4,c=5, ∙∙∙,c=n 这样一些不同的类,分别将各类三角形的集合记作B4,B5,∙∙∙,Bn,则它们构成了所有三角形的集合B的一个分划,则有
而在Bk 中,三角形三边分别为a<b<k ,其中k为定值。于是可将(a,b)对应为平面中的格点,如图。由于还有a+b>k ,所以这些点由a=b, a+b=k,b=k三条直线所围成的三角形区域内部。所以当k 为偶数时,有
当k 为奇数时,有
所以n为偶数时,


n为奇数时,
补例2 设[x]表示不超过实数x的最大整数。求方程x2 - [x2] = (x - [x] )2在区间1≤x≤n中根的个数。
解:显然x=n是方程的一个根。下面我们再分别求出方程在区间1≤x<2,2≤x<3,…,n-1≤x<n中的根的个数。为此设这些区间中根的个数为B1,B2,…,Bn-1, 即以Bk表示方程在区间k≤x<k+1中根的全体。
∵在k≤x<k+1中,有[x]=k ,如果再记p= x-[x] ,就有0≤p<1。于是原来方程就可以写成(k+p)2 -[(k+p)2]=p2 即k2 +2kp=[k2 +2kp+p2]
注意到[k2 +2kp+p2]=k2 +[2kp+p2] 知上式即为 2kp=[2kp+p2]
该式右端是一个整数,所以左端也应为整数,即2kp是整数
由于k为整数,0≤p<1,所以只有当p=0 ,1/2k ,2/2k ,…,(2k-1)/2k
时,等式才能成立。从而知原方程在此区间中恰有2k个根,即| Bk |=2k
于是由加法原理知原方程在区间1≤x≤n中共有
| B1 |+ | B2 |+ …+| Bn-1 |+1=2+4+ …+2(n-1)+1=n 2 -n+1 个根
加法原理用途极多,如将其与其他数学原理,例如抽屉原理结合起来,就可以推出许多有趣的数学命题。
(二)乘法原理
如果完成一件事情要分几个步骤B1 ,B2 ,…,Bn ,而每个步骤Bi有mi种方法(1≤i≤n) ,那么完成这事共有

例2 某人在进小学、初中、高中时都分别有二所学校可选择,那么他就有多种不同的方式从小学到高中。
共8种=2 x 2 x 2
例3 多项式乘积
(a1+a2+a3) (b1+b2+b3+b4) (c1+c2+c3+c4+c5+c6) (d1+d2)
的展开式中有多少不同的项。
解:展式中每项均形如aibjckdl,其中i є{1,2,3} ,j є{1,2,3,4} ,
k є{1,2,3,4,5,6} , l є{1,2}
由乘法原理,展式中共有 3 x 4 x 6 x 2 =144 (项)
例4 在ΔABC的三边上分别取n1,n2,n3个点(不含A,B,C),在三边上的点中各取一个作为三角形的顶点,可以得到多少个不同的