排列组合1课件

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

全部组合分析公式的推导基于以下两原理（一）加法原理如果完成一件事情有n种方式A1，∙∙∙，An，每种方式中又有mi种方法（1≤i≤n），且AiAj=Ø，则要完成此事共有

一年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为奇数时，（二）乘法原理如果完成一件事情要分几个步骤B1，B2，…，Bn，而每个步骤Bi有mi种方法(1≤i≤n)，那么完成这事共有

例2某人在进小学、初中、高中时都分别有二所学校可选择，那么他就有多种不同的方式从小学到高中。共8种=2x2x2例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}由乘法原理，展式中共有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的每一个正约数就都具有形式其中j1

єA1，…，jk

єAk，故由乘法原理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件（1≤k≤n）来排成一列，共有多少种不同的排法？”高中数学课本中就以此为排列的定义基础。称“从n个不同元素中，任取k（k≤n）个元素按照一定的顺序排成一列，叫做从n个不同元素中取出k个元素的一个排列。”（即线排列）

其实这种定义有一定的局限性，容易使人误将“排成一列”理解为排列问题的本质。最早研究排列问题的国家是印度，早年出现在印度书籍中的例子有：湿婆神的十只手拿十件东西：绳子、钩子、蛇、鼓、豆盖骨、三叉戟、乐架、匕首、箭、弓。这十件东西是她的象征物，如果将这十种东西交换，共有多少种不同的方式？正象哈利神四只手交换狼牙棒、铁饼、莲与贝壳一样。

这里湿婆神的十只手和哈利神的四只手都不是成一列分布，而是分布在躯干的两侧的，所以所拿的东西都不是“按一定的顺序排成一列”。现解决一开始提出的问题。先从n个物体中任取一个放在排首，有n种不同选法。再从余下的n-1个中选出一个来放在排二，有n-1种。这样逐个选出，直到n-k+1个物体中选出一个放在排尾，有n-k+1种不同方法。由乘法原理，有n(n-1)∙∙∙(n-k+1)=

为约定符号

人们通常把n(n-1)∙∙∙2∙1记为n！

∴解：因为一旦取得一个数字后，这个数字所在行与列即划之，所以所取得的k个数字中，不可能有两个同行的，也不可能同列。换言之，即k个数字都是取自不同行也不同列，故有k！个。又因为aij=(i-1)k+j，而每个子集中k个数字中都包含每一行，每一列的数字各一个，所以每个子集中k个数字之和均为

*例：在右图的圆周上均匀地布列着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，…，Sn≥0，则相应的填法合乎要求。如果S1，…，Sn中有负数，则只要将所填数字集体顺时针旋转若干位置，即可得合乎要求的填法。现证之。设Sk=min(S1，…，Sn)，Sk<0

Aai1ai23.重排列重排列即一个依次进行的多重选取过程，并且每一重选取都在一个集合中进行，已经选过的元素还可再选。（这是对乘法原理的最直接应用）重复排列的最简单例子是电话号码，某市的电话号码是7位，每位上的数码无非是0，1，…，9，而且不同位上的数码可以是相同的。如7566783，7533338，7818888，…共有107种

以上是无限重排列中国是世界上最早讨论重排列的国家，《易经》中所收集的资料可以追溯到公元前七世纪。《易经》中有两个符号，叫做“阳爻”和“阴爻”，《易经》讨论了由这样两个符号形成的3个字符和6个字符的所有可能情况。其中3个字符是：阳阳阳、阳阳阴、阳阴阳、阴阳阳阳阴阴、阴阳阴、阴阴阳、阴阴阴