排列、组合与二项式定理.ppt

第20章排列与组合,10.1分类计数原理与分步计数原理,问题1某人从甲地到乙地，可以乘汽车、轮船或火车，一天中汽车有3班，轮船有2班，火车有1班一天中乘坐这些交通工具从甲地到乙地共有多少种不同的走法？,实例考察,问题2某人从甲地出发，经过乙地到达丙地从甲地到乙地有A，B，C共3条路可走；从乙地到丙地有a，b共2条路可走那么，从甲地经过乙地到丙地共有多少种不同的走法？,10.1分类计数原理与分步计数原理,分类计数原理（加法原理）：,如果完成一件事有n类办法，在第1类办法中有k1种不同的方法，在第2类办法中有k2种不同的方法在第n类办法中有kn种不同的方法，那么，完成这件事共有Nk1k2kn种不同的方法,10.1分类计数原理与分步计数原理,分步计数原理（乘法原理）：,10.1分类计数原理与分步计数原理,如果一件事需要分成n个步骤完成，做第1步有k1种不同的方法，做第2步有k2种不同的方法做第n步有kn种不同的方法，那么，完成这件事共有Nk1k2kn种不同的方法,例1书架上层放有5本不同的语文书，中层放有6本不同的数学书，下层放有4本不同的外语书求解下列问题：（1）从中任取1本，有多少种不同的取法？（2）从中任取语文、数学和外语书各1本，有多少种不同的取法？,10.1分类计数原理与分步计数原理,解（1）从书架上任取1本书，有3类办法：第1类办法是从上层取语文书，可以从5本书中任取1本，有5种方法；第2类办法是从中层取数学书，可以从6本书中任取1本，有6种方法；第3类办法是从下层取外语书，可以从4本书中任取1本，有4种方法根据分类计数原理，得到不同的取法的种数是N56415,10.1分类计数原理与分步计数原理,（1）从中任取1本，有多少种不同的取法？,解从书架上任取语文、数学和外语书各1本，可以分成3个步骤完成：第1步是从上层取1本语文书，有5种方法；第2步是从中层取1本数学书，有6种方法；第3步是从下层取1本外语书，有4种方法根据分步计数原理，得到不同的取法的种数是N564120,10.1分类计数原理与分步计数原理,（2）从中任取语文、数学和外语书各1本，有多少种不同的取法？,例2甲、乙两个同学做“石头、剪刀、布”的游戏，出手一次，共有多少种不同的情况发生？如果三个人做此游戏，出手一次，又有多少种不同的情况发生？,10.1分类计数原理与分步计数原理,分析虽然甲、乙两个同学是同时出手，但不妨看作甲先出手、乙后出手，这是两个接连进行的过程,解甲出手有3种选择，乙出手也有3种选择，所以两人做游戏出手一次，共有339种不同的情况类似地，如果甲、乙、丙三人做此游戏，出手一次，共有33327种不同的情况,1在一次读书活动中，指定的书目包括：不同的文学书3本，历史书5本，科技书7本，某同学任意选读其中1本，共有多少种不同的选法？2某班三好学生中男生有5人，女生有4人，从中任选1人去领奖，共有多少种不同的选法？从中任选男女各1人去参加座谈会，共有多少种不同的选法？,10.1分类计数原理与分步计数原理,3某手机生产厂为某种机芯设计了3种不同的外形，每种外形又有5种不同色彩的外壳及6种不同的屏幕背景灯光，问这种手机共可设计多少种不同的款式？4由1，3，5，7这4个数字组成的没有重复数字的两位数共有多少个？,10.1分类计数原理与分步计数原理,10.2排列,要从甲、乙、丙3名工人中选取2名，分别安排上日班和晚班，找出所有的选择方法，将下表补充完整,实例考察,10.2排列,有分别编号的4个小球和3个盒子，要选取其中的3个小球分别放入盒子中，每个盒子只能放一个球，下表已给出两种放置方法，请你补充列出其余所有方法,一、排列与排列数的概念,10.2排列,10.2排列,10.2排列,一般地，从n个不同的元素中任取m个元素（n，mN*，mn），按照一定的顺序排成一列，称为从n个不同的元素中取出m个元素的一个排列,1判断下列问题是不是求排列数的问题，如果是，请写出相应的排列数的符号：（1）把5只苹果平均分给5个同学，计算共有多少种分配方法（2）从5只苹果中取出2只给某位同学，计算共有多少种选择方法（3）10个人互写一封信，计算共写多少封信（4）10个人互通一次电话，计算共通几次电话,10.2排列,2按要求写出排列，并写出相应的排列数的符号：（1）3个元素a，b，c全部取出的所有排列（2）从5个元素a，b，c，d，e中任取2个元素的所有排列,10.2排列,10.2排列,二、排列数公式,10.2排列,由此可得排列数公式：,10.2排列,排列数公式的特点是：等号右边第1个因数是n，后面的每个因数都比它前面一个因数少1，最后一个因数为nm1，共有m个因数相乘,根据分步计数原理，全部填满m个空位共有n（n1）（n2）（nm1）,10.2排列,例1计算下列各题：,10.2排列,解（2）,本题也可以直接用计算器计算计算的按键过程为：计算的按键过程为：,10.2排列,解由于即解得所以,例2若，求,10.2排列,例3有5本不同的书，发给3名同学，每人1本，共有多少种不同的分法？,例4某信号兵用红、黄、蓝3面旗挂在竖直的旗杆上表示信号，每次可以任挂1面、2面或3面，并且不同的悬挂顺序表示不同的信号，一共可以表示多少种信号？,10.2排列,10.2排列,例5用09这10个数字可以组成多少个没有重复数字的三位数？,解法1符合条件的三位数可以分为3类：第1类：每位数字都不是0的三位数，有个.第2类：个位数字是0的三位数，有个.第3类：十位数字是0的三位数，有个.根据分类计数原理，符合条件的三位数的个数是,10.2排列,解法2因为百位上的数字不能是0，所以可分两个步骤来完成：第1步，先排百位上的数字，它只能从除0以外的19这9个数字中任选一个，有P种选法第2步，再排十位和个位上的数字，它可以从余下的9个数字（包括0）中任选两个，有P种选法根据分步计数原理，所求的三位数的个数是,19,29,解法3从09这10个数字中任选3个数字的排列数为P，其中0排在百位上的排列数为P，因此所求的三位数的个数是,310,29,10.2排列,10.2排列,例6以所有26个英文字符组成一个26位的密码，规定在一个密码中不出现相同的字符，那么可以组成多少种不同的密码？以单台计算机去解密，若计算机解密的速度是每秒钟检查107个不同的密码，那么最多需要多少时间才能解密？（结果以年为单位，保留6位有效数字）,解26个英文字符是26个不同的元素，一个密码是26个元素的一个全排列，总计密码数是26的全排列数所以组成的密码数是26！,计算机解密耗时最长的情况是直到最后一个才检查到设置的密码，此时耗时T为所以，用题中所给计算机解密，最多需要时间约为12788.3亿年,10.2排列,计算：2若，求n。3由0，1，2，3，5，7，9这7个数字能组成多少个没有重复数字的三位数？4（1）7人排队，甲必须站在正中间有多少种排法？（2）7人排队，甲，乙必须站头尾有多少种排法,10.2排列,10.3组合,在一个4人（甲、乙、丙、丁）参加的小型工作会议上，任何一位与会者都要同其他与会者每人握手一次下表已给出两次握手的双方名单，请补充列出其他各次握手的双方名单,实例考察,10.3组合,列出各次握手的双方名单就是要从4个人中选出两人，且不计两人间的顺序，并将各种选法罗列出来,要从甲、乙、丙3名工人中选取2名，共同值晚班，有多少种选择方法？请逐一列出,10.3组合,一、组合与组合数的概念,（1）在人数为60人的班级中，选出5人参加专业知识竞赛，有多少种选法？（2）由20人组成的足球队中，除守门员外，还需选10人作为首发阵容，可组成多少种不同的首发阵容？又要在50名拉拉队员中挑选20人前往助阵，有多少种挑选方案？,10.3组合,例把下列的问题归结为组合问题，并写出相应的组合数的符号：,10.3组合,1把下列的问题归结为组合问题，并写出相应的组合数的符号：（1）6位朋友互相握手道别，共握手多少次？（2）6道习题任意选做4道题，有多少种不同的选法？（3）正16边形有多少条对角线？,10.3组合,2按要求写出下列组合：（1）从5个元素a，b，c，d，e中任取2个元素的所有组合（2）从4个元素a，b，c，d中任取3个元素的所有组合,10.3组合,10.3组合,二、组合数公式,34,从个不同元素中取个元素的排列数：,10.3组合,根据分步计数原理，得,因此,由此得到组合数公式：,10.3组合,10.3组合,因为所以组合数公式还可写成,根据组合数公式，当mn时有,10.3组合,例1计算：,解,10.3组合,解因为12个点中任何3个点都不在同一直线上，所以任取3个点都可以画出一个三角形因此所求三角形的个数，就是从12个不同的元素中取出3个元素的组合数，即所以一共可画220个三角形,例2平面内有12个点，任何3个点不在同一直线上，以每3个点为顶点画一个三角形，一共可画多少个三角形？,10.3组合,例3一次小型聚会，每一个与会者都和其他与会者握一次手，共有15次握手，问有多少人参加这次聚会？,例4100件商品中含有3件次品，其余都是正品，从中任取3件：（1）3件都是正品，有多少种不同的取法？（2）3件中恰有1件次品，有多少种不同的取法？（3）3件中最多有1件次品，有多少种不同的取法？（4）3件中至少有1件次品，有多少种不同的取法？,解（）因为3件都是正品，所以应从97件正品中取，所有不同取法的种数是,10.3组合,10.3组合,（2）3件中恰有1件次品，有多少种不同的取法？,10.3组合,（3）3件中最多有1件次品，有多少种不同的取法？,解3件中至少有1件次品的取法，包括1件是次品，2件是次品和3件是次品，因此3件中至少有1件次品的取法的