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

《20排列、组合与二项式定理.ppt》由会员分享，可在线阅读，更多相关《20排列、组合与二项式定理.ppt（55页珍藏版）》请在三一文库上搜索。

1、第20章 排列与组合,10.1 分类计数原理与分步计数原理,问题1 某人从甲地到乙地，可以乘汽车、轮船或火车，一天中汽车有3班，轮船有2班，火车有1班一天中乘坐这些交通工具从甲地到乙地共有多少种不同的走法？,实例考察,问题2 某人从甲地出发，经过乙地到达丙地从甲地到乙地有A，B，C共3条路可走；从乙地到丙地 有a，b共2条路可走那么，从甲地经过乙地到丙地共有多少种不同的走法？,10.1 分类计数原理与分步计数原理,分类计数原理（加法原理）：,如果完成一件事有n类办法，在第1类办法中有k1种不同的方法，在第2类办法中有k2种不同的方法在第n类办法中有kn种不同的方法，那么，完成这件事共有 Nk1

2、k2kn 种不同的方法,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类办法是从上层取

3、语文书，可以从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）从中任取语

4、文、数学和外语书各1本，有多少种不同的取法？,例2 甲、乙两个同学做“石头、剪刀、布”的游戏，出手一次，共有多少种不同的情况发生？如果三个人做此游戏，出手一次，又有多少种不同的情况发生？,10.1 分类计数原理与分步计数原理,分析 虽然甲、乙两个同学是同时出手，但不妨看作甲先出手、乙后出手，这是两个接连进行的过程,解 甲出手有3种选择，乙出手也有3种选择，所以两人做游戏出手一次，共有339种不同的情况 类似地，如果甲、乙、丙三人做此游戏，出手一次，共有 33327种不同的情况,1在一次读书活动中，指定的书目包括：不同的文学书3本，历史书5本，科技书7本，某同学任意选读其中1本，共有多少种不同的

5、选法？ 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个盒子，

6、要 选取其中的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个人互通一次电话，计算共通几次电

7、话,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）,本题也可以直接用计算器计算 计算 的按键过程为： 计算

8、的按键过程为：,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的三位数，有 个. 根据分类计数原理，符合条

9、件的三位数的个数是,10.2 排 列,解法2 因为百位上的数字不能是0，所以可分两个步骤来完成： 第1步，先排百位上的数字，它只能从除0以外的19这9个数字中任选一个，有P 种选法 第2步，再排十位和个位上的数字，它可以从余下的9个数字（包括0）中任选两个，有P 种选法 根据分步计数原理，所求的三位数的个数是,1 9,2 9,解法3 从09这10个数字中任选3个数字的排列数为P ，其中0排在百位上的排列数为P ，因此所求的三位数的个数是,3 10,2 9,10.2 排 列,10.2 排 列,例6 以所有26个英文字符组成一个26位的密码，规定在一个密码中不出现相同的字符，那么可以组成多少种不同

10、的密码？以单台计算机去解密，若计算机解密的速度是每秒钟检查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人排队，甲，乙必

11、须站头尾有多少种排法,10.2 排 列,10.3 组 合,在一个4人（甲、乙、丙、丁）参加的小型工作会议上，任何一位与会者都要同其他与会者每人握手一次下表已给出两次握手的双方名单，请补充列出其他各次握手的双方名单,实例考察,10.3 组 合,列出各次握手的双方名单就是要从4个人中选出两人，且不计两人间的顺序，并将各种选法罗列出来,要从甲、乙、丙3名工人中选取2名，共同值晚班，有多少种选择方法？请逐一列出,10.3 组 合,一、组合与组合数的概念,（1）在人数为60人的班级中，选出5人参加专业知识竞赛，有多少种选法？ （2）由20人组成的足球队中，除守门员外，还需选10人作为首发阵容，可组成多少

12、种不同的首发阵容？又要在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 组 合,二、组合数公式,3 4,从个不同元素中取个

13、元素的排列数 ：,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

14、次握手，问有多少人参加这次聚会？,例4 100件商品中含有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件次品的取法的种数是,10.3 组 合,（4）3件中至少有1件次品，有多少种不同的取法？,10.3 组 合,10.3 组 合,三、组合数的性质,在一般情况下：从n个元素中选出m个元素的组合数，与从n个元素中选出nm个元素的组合数是相等的 由此，得到组合数的一种重要性质：,10.3 组 合,解,例1 计算,10.3 组 合,例2 已知 ，求n,解 为使 ，可令n=3n2，即n=1 又因为 ，所以 成立 又因此也可令10n=3n2，即n=3 因此，n=1或n=3,10.3 组 合,