组合数学算法一.pptx

《组合数学算法一.pptx》由会员分享，可在线阅读，更多相关《组合数学算法一.pptx（13页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、加法原理的例子补充|A|，|B|分别为集合A，B中元素的个数补例1 现有长度分别为1，2，n的细木棍各一根，可以以它们为边构成多少个不同的三角形？解：记三角形三边长度为a，b，c，不妨设abc。以c的长度将这些三角形分类，则可分为c=4，c=5，c=n 这样一些不同的类，分别将各类三角形的集合记作B4，B5，Bn，则它们构成了所有三角形的集合B的一个分划，则有 而在Bk 中，三角形三边分别为abk，所以这些点由a=b，a+b=k，b=k三条直线所围成的三角形区域内部。所以当k 为偶数时，有 当k 为奇数时，有 所以n为偶数时，n为奇数时，第1页/共13页补例2 设x表示不超过实数x的最大整数。

2、求方程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是整数 由于

3、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=n 2-n+1 个根 加法原理 用途极多，如将其与其他数学原理，例如抽屉原理结合起来，就可以推出许多有趣的数学命题。第2页/共13页（二）乘法原理 如果完成一件事情要分几个步骤B1，B2，Bn，而每个步骤Bi有mi种方法(1in)，那么完成这事共有 例2 某人在进小学、初中、高中时都分别有二所学校可选择，那么他就有多种不同的方式从小学到高中。共8

4、种=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），在三边上的点中各取一个作为三角形的顶点，可以得到多少个不同的三角形？n1n2n3第3页/共13页*例5 每个完全平方数都有奇数个正约数证：设n=m2是一个完全平方数 而m的素因数分解式

5、为 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（种）（加法原理之应用）第4页/共13页

6、 但它们不可能在一次单程行驶中都卖得出去。我们来考虑其中以前面7个车站中的某一个作为起点，而以后面7个车站中的某一个作为终点的车票，就应当为7x7=49（种）之多（最多种）。凡持这种车票的乘客都要乘车通过7号车站与8号车站之间的路程。但由于汽车满员为25人，所以此类车票中至少会有49-25=24（种）卖不出去。（即只有25人，最多只能卖出25张此类票）这样一来，车上最多只能卖出91-24=67（种）。（三）排列 1.线排列 2.圆排列 3.重排列1.线排列（排列）排列的字面意思是列队。“最基本”例子就是：“要从n个不同的物体中选出k件（1kn）来排成一列，共有多少种不同的排法？”高中数学课本中

7、就以此为排列的定义基础。称“从n个不同元素中，任取k（k n）个元素按照一定的顺序排成一列，叫做从n个不同元素中取出k个元素的一个排列。”（即线排列）第5页/共13页 其实这种定义有一定的局限性，容易使人误将“排成一列”理解为排列问题的本质。最早研究排列问题的国家是印度，早年出现在印度书籍中的例子有：湿婆神的十只手拿十件东西：绳子、钩子、蛇、鼓、豆盖骨、三叉戟、乐架、匕首、箭、弓。这十件东西是她的象征物，如果将这十种东西交换，共有多少种不同的方式？正象哈利神四只手交换狼牙棒、铁饼、莲与贝壳一样。这里湿婆神的十只手和哈利神的四只手都不是成一列分布，而是分布在躯干的两侧的，所以所拿的东西都不是“按

8、一定的顺序排成一列”。现解决一开始提出的问题。先从n个物体中任取一个放在排首，有n种不同选法。再从余下的n-1个中选出一个来放在排二，有n-1种。这样逐个选出，直到n-k+1个物体中选出一个放在排尾，有n-k+1种不同方法。由乘法原理，有 n(n-1)(n-k+1)=为约定符号 人们通常把 n(n-1)21 记为 n！第6页/共13页 现代组合学中对排列下了一个更为妥当的定义：从n个不同元素中有次序地选取k（1kn）个，叫做从n个不同元素中取出k个元素的一个排列。又当k=n时，就叫做一个全排列。有 人们又规定 0！=1 容易的大家都知道了计算。例 把自然数1，2，k2排成一个方阵表。从表中任意

9、取一个数，然后删去这个数所在的行和列中的全部数字，再从剩下的(k-1)2个数组成的方阵表中任意取出一个数，并删去这个数所在的行和列中的所有数字。这样一直进行下去，一共可取表中k个不同的数字，它们构成了集合1，2，k2的一个k阶子集。问题是：用这样的方法，共可取得1，2，k2中多少个不同的由k个数字组成的子集？这些子集中的k个数字之和各是多少？1 2 k k+1 k+2 2k (k-1)k+1 (k-1)k+2 k2第7页/共13页解：因为一旦取得一个数字后，这个数字所在行与列即划之，所以所取得的k个数字中，不可能有两个同行的，也不可能同列。换言之，即k个数字都是取自不同行也不同列，故有k！个。

10、又因为aij=(i-1)k+j，而每个子集中k个数字中都包含每一行，每一列的数字各一个，所以每个子集中k个数字之和均为 第8页/共13页2.圆排列 从集合S=a1，an的n个不同元素中取出r个元素，按某种次序（如逆时针方向），排成一个圆圈，称这样的排列为圆排列。这里相同的顺序被视同一排列。如：这种圆排列的个数=如果r=n，则例：4对兄弟站成一圈，要求每对兄弟相邻，有多少种不同站法？解：先让哥哥站一圈，有 =3！=6（种）不同排法。然后，让4位弟弟插入其中，每人均可在其兄左边亦可右边，故均有2种方式。所以共有6x2=96（种）*例：用4种不同颜色给小正方形木块的4条边着色，每边各涂一种颜色，能有

11、多少种不同的着色花样？解：此处不仅只考虑4种颜色的相对顺序，而且木块可以翻边，因此没有逆时针顺序与顺时针顺序的不同区分。故一共有 =3 种。AB=DCDABC第9页/共13页*例：在右图的圆周上均匀地布列着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。如果这些S

12、1，Sn0，则相应的填法合乎要求。如果S1，Sn中有负数，则只要将所填数字集体顺时针旋转若干位置，即可得合乎要求的填法。现证之。设Sk=min(S1，Sn)，Sk0 Aai1ai2第10页/共13页 由于Sk的最小性，知 这就是说，只要将所填数字集体顺时针旋转后，使得方框A中的数字变成ai k+1（保持各数间原来的相对顺序），即可使得自A中数字开始，按逆时针方向逐个累加数字，所得出的每一步和数均非负。以上证明的事实表明，无论按什么样的相对顺序将数填入方框，都可通过整体旋转这些数而得到一种合乎要求的填数方式，且保持数的相对顺序不变。于是可以断言，合乎要求的填法数目不会少于这n个数字进行圆排列的数

13、目，即(n-1)！种。第11页/共13页3.重排列 重排列即一个依次进行的多重选取过程，并且每一重选取都在一个集合中进行，已经选过的元素还可再选。（这是对乘法原理的最直接应用）重复排列的最简单例子是电话号码，某市的电话号码是7位，每位上的数码无非是0，1，9，而且不同位上的数码可以是相同的。如7566783，7533338，7818888，共有107种 以上是无限重排列 中国是世界上最早讨论重排列的国家，易经中所收集的资料可以追溯到公元前七世纪。易经中有两个符号，叫做“阳爻”和“阴爻”，易经讨论了由这样两个符号形成的3个字符和6个字符的所有可能情况。其中3个字符是：阳阳阳、阳阳阴、阳阴阳、阴阳阳 阳阴阴、阴阳阴、阴阴阳、阴阴阴 这刚好是由集合阳，阴中依次进行的3重选取过程的所有可能情况。或者叫做由阳、阴二者中每次选取3个重复排列的所有情况。由于其数目共2x2x2=8（个），故易经称之曰“八卦”。相应的六个字符的共有26=64（种），称为“六十四卦”。例 公元八世纪，我国流传过一个问题，据说是一个和尚提出的：围棋盘上有361个位置，既可放黑子，或白子，又可空着，共有多少种不同的情况。3361（种）第12页/共13页感谢您的观看！第13页/共13页