第一章 排列组合.pptVIP

第一章—排列组合;第一章 排列组合;;1.1 加法法则与乘法法则;1.1 加法法则与乘法法则;例1.1.3 机动车牌照字由7个字符组成，第一个字符是汉字，表示省份或军区等，第二个字符是英文字母，表示市、区或行业等，其余5位可选自英文字母或数字（有时用第三个字符表示行业，如出租用T)，问一个市的机动车拥有量最多是多少？;1.1 加法法则与乘法法则;1.1 加法法则与乘法法则;2)“含0”和“含1”不可直接套用。0019(含1但不含0)。 在组合的习题中有许多类似的隐含的规定，要特别留神。;1.1 加法法则与乘法法则;;1.2 一一对应原理;例1.2.1 在65名选手之间进行淘汰赛(即一场的比赛结果，失败者退出比赛),最后产生一名冠军，问要举行几场比赛？;例1.2.2 设凸n边形的任意三条对角线不共点，求对角线在多边形内交点的个数。;;1.3 排列与组合;1.3 排列与组合;规定;例1.3.1 由5种颜色的星状物，20种不同的花排列成如下图案：两边是星状物，中间是3朵花，问共有多少种这样的图案？ ;例1.3.2 A单位有7名代表，B单位有3位代表，排成一列合影，如果要求B单位的3人排在一起，问有多少种不同的排列方案。若A单位的2人排在队伍两端，B单位的3人不能相邻，问有多少种不同的排列方案？;于是我们只需要计算Si即可。; S2=3(1+3+5+7)10+3(1+3+5+7)= 480+48=528;1.3 排列与组合;1.3 排列与组合;1.3 排列与组合;1.3 排列与组合;若球不同，盒子相同，则是从n个中取r个的组合的模型。若放入盒子后再将盒子标号区别，则又回到排列模型。每一个组合可有r!个标号方案。 故有 C(n,r)·r!=P(n,r), 即 C(n,r)=P(n,r)/r!= ;1.3 排列与组合;1.3 排列与组合;;1.4 Sterling近似公式;1.4 Stirling近似公式;1.4 Stirling近似公式;1.4 Stirling近似公式;1.4 Stirling近似公式;1.4 Stirling近似公式;1.4 Stirling近似公式;1.4 Stirling近似公式;1.4 Stirling近似公式;1.4 Stirling近似公式;;1.5 全排列的生成算法;1.5 全排列的生成算法;1.5 全排列的生成算法;1.5 全排列的生成算法;在839647521中从右向左第一个小于右边数字的是元素4，此时有后缀7521；;1.5 全排列的生成算法;1.5 全排列的生成算法;令 j=max{i|PiPi+1}, k=max{i|PiPj} 对换Pj，Pk，并将Pj+1…Pk-1PjPk+1…Pn翻转，;计算给定排列的序号;1.5 全排列的生成算法;1.5 全排列的生成算法;1.5 全排列的生成算法;所以先于此排列的排列的个数为：;将8!,7!,…,1!前面的系数抽出，放一起得 ，此数的特点： 计算排列839647521序号的中间环节，我们称之为中介数。 ※这是一个很有用的概念。;给定排列的序号计算;1.5 全排列的生成算法;给定序号推出排列的方法;2+1=3，但3已经在P5左边出现， 3+1=4 → P5=4;方法2：;1.5 全排列的生成算法;1.5 全排列的生成算法;在数的阶乘表示法下，任意的数m(0≤m≤n!-1)可表示为;由排列求中介数(及序号)的方法;1.5 全排列的生成算法;解 在[1,3]的全排列中,按递增进位制法 123是第1个排列，中介数是00，序号为0; 213是第2个排列，中介数是01，序号为1; 132是第3个排列，中介数是10，序号为2; 231是第4个排列，中介数是11，序号为3; 312是第5个排列，中介数是20，序号为4; 321是第6个排列，中介数是21，序号为5.;由序号(及中介数)求排列的方法;1.5 全排列的生成算法;设在[1,n]上的某排列的中介数为 an-1an-2…a1，则对元素从大到小逐个确定其位置，元素k的位置是从右向左的第ak-1+1个空位，最后留下的空是元素1的位置。;例1.5.7 在递增进位制下，求序号为297191的排列。;例1.5.8 在递增进位制下，求排列794563821的下一个。;例1.5.9 在递增进位制下，求排列794563821后的第10个排列。;1.5.3递减进位制数法;1.5 全排列的生成算法;※ 在递减进位制下求下一个排列十分容易;解 在