数学选修23解排列问题的常用技巧2

《数学选修23解排列问题的常用技巧2》由会员分享，可在线阅读，更多相关《数学选修23解排列问题的常用技巧2（54页珍藏版）》请在金锄头文库上搜索。

1、数学数学选修修2-3解排列解排列问题的常用技巧的常用技巧2 名称名称内容内容分类计数原理分类计数原理分步计数原理分步计数原理定定定定 义义义义相同点相同点相同点相同点不同点不同点不同点不同点1.两个原理的区别与联系：两个原理的区别与联系：统计做一件事或完成一项工作的方法数统计做一件事或完成一项工作的方法数 直接（直接（直接（直接（分类分类分类分类）完成）完成）完成）完成 间接（间接（间接（间接（分步分步分步分步）完成）完成）完成）完成做一件事，完成它可以有做一件事，完成它可以有做一件事，完成它可以有做一件事，完成它可以有n n类办法，类办法，类办法，类办法，第一类办法中有第一类办法中有第一类办

2、法中有第一类办法中有mm1 1种不同的方法，种不同的方法，种不同的方法，种不同的方法，第二类办法中有第二类办法中有第二类办法中有第二类办法中有mm2 2种不同的方法种不同的方法种不同的方法种不同的方法，第第第第n n类办法中有类办法中有类办法中有类办法中有mmn n种不同的方法，种不同的方法，种不同的方法，种不同的方法， 那么完成这件事共有那么完成这件事共有那么完成这件事共有那么完成这件事共有 N=N=mm1 1+ +mm2 2+ +mm3 3+mmn n 种不同的方法种不同的方法种不同的方法种不同的方法做一件事，完成它可以有做一件事，完成它可以有做一件事，完成它可以有做一件事，完成它可以有n

3、 n个步骤，个步骤，个步骤，个步骤，做第一步中有做第一步中有做第一步中有做第一步中有mm1 1种不同的方法，种不同的方法，种不同的方法，种不同的方法，做第二步中有做第二步中有做第二步中有做第二步中有mm2 2种不同的方法种不同的方法种不同的方法种不同的方法，做第做第做第做第n n步中有步中有步中有步中有mmn n种不同的方法，种不同的方法，种不同的方法，种不同的方法， 那么完成这件事共有那么完成这件事共有那么完成这件事共有那么完成这件事共有 N=N=mm1 1 mm2 2 mm3 3mmn n 种不同的方法种不同的方法种不同的方法种不同的方法. .2.2.排列和组合的区别和联系：排列和组合的区

4、别和联系：名名名名 称称称称排排排排 列列列列组组组组 合合合合定义定义定义定义种数种数种数种数符号符号符号符号计算计算计算计算公式公式公式公式关系关系关系关系性质性质性质性质 ，从从从从n n个不同元素中取出个不同元素中取出个不同元素中取出个不同元素中取出mm个元个元个元个元素，素，素，素，按一定的顺序按一定的顺序按一定的顺序按一定的顺序排成一列排成一列排成一列排成一列从从从从n n个不同元素中取出个不同元素中取出个不同元素中取出个不同元素中取出mm个元个元个元个元素，素，素，素，把它并成把它并成把它并成把它并成一组一组一组一组所有排列的的个数所有排列的的个数所有排列的的个数所有排列的的个数

5、所有组合的个数所有组合的个数所有组合的个数所有组合的个数1.某校组织学生分某校组织学生分4个组从个组从3处风处风景点中选一处去春游景点中选一处去春游,则不同的则不同的春游方案的种数是春游方案的种数是_A. B. C. D.课前热身练习课前热身练习C2.将数字将数字1、2、3、4 填入标号为填入标号为1、2、3、4 的四个方格里的四个方格里 , 每格填一个数字，每格填一个数字，则每个方格的标号与所填的数字都不相则每个方格的标号与所填的数字都不相同的填法共有同的填法共有_ A. 6 种种 B. 9种种 C.11种种 D.23种种B课前热身练习课前热身练习3.3.判断下列问题是组合问题还是排列问题判

6、断下列问题是组合问题还是排列问题? ? (1)(1)设集合设集合设集合设集合A A=a a, ,b b, ,c c, ,d d, ,e e, ,则集合则集合则集合则集合A A的含有的含有的含有的含有3 3个元素个元素个元素个元素的子集有多少个的子集有多少个的子集有多少个的子集有多少个? ?(2)(2)某铁路线上有某铁路线上有某铁路线上有某铁路线上有5 5个车站个车站个车站个车站, ,则这条铁路线上则这条铁路线上则这条铁路线上则这条铁路线上共需准备多少种车票共需准备多少种车票共需准备多少种车票共需准备多少种车票? ? 有多少种不同的火车票价？有多少种不同的火车票价？有多少种不同的火车票价？有多少

7、种不同的火车票价？组合问题组合问题组合问题组合问题排列问题排列问题排列问题排列问题(3)10(3)10名同学分成人数相同的数学和名同学分成人数相同的数学和名同学分成人数相同的数学和名同学分成人数相同的数学和英语两个学习小组，共有多少种分法英语两个学习小组，共有多少种分法英语两个学习小组，共有多少种分法英语两个学习小组，共有多少种分法? ?组合问题组合问题组合问题组合问题(4)10(4)10人聚会，见面后每两人之间要人聚会，见面后每两人之间要人聚会，见面后每两人之间要人聚会，见面后每两人之间要握手相互问候，共需握手多少次握手相互问候，共需握手多少次握手相互问候，共需握手多少次握手相互问候，共需握

8、手多少次? ?组合问题组合问题组合问题组合问题(5)(5)从从从从4 4个风景点中选出个风景点中选出个风景点中选出个风景点中选出2 2个安排游览个安排游览个安排游览个安排游览, ,有多少种有多少种有多少种有多少种不同的方法不同的方法不同的方法不同的方法? ?组合问题组合问题组合问题组合问题 (6) (6)从从从从4 4个风景点中选出个风景点中选出个风景点中选出个风景点中选出2 2个个个个, ,并确定这并确定这并确定这并确定这2 2个风景点的个风景点的个风景点的个风景点的游览顺序游览顺序游览顺序游览顺序, ,有多少种不同的方法有多少种不同的方法有多少种不同的方法有多少种不同的方法? ?排列问题排

9、列问题排列问题排列问题组合问题组合问题组合问题组合问题排列组合问题总的原则排列组合问题总的原则合理合理分类和分类和准确准确分步分步解法解法解法解法分析：先安排甲，按照要求对其进行分类，分两类：分析：先安排甲，按照要求对其进行分类，分两类：分析：先安排甲，按照要求对其进行分类，分两类：分析：先安排甲，按照要求对其进行分类，分两类： 根据分步及分类计数原理，不同的站法共有根据分步及分类计数原理，不同的站法共有根据分步及分类计数原理，不同的站法共有根据分步及分类计数原理，不同的站法共有: :示例示例 6个同学和个同学和2个老师排成一排照相个老师排成一排照相, 2个老个老师站中间师站中间,学生甲不站排

10、头学生甲不站排头,学生乙不站排尾学生乙不站排尾,问共问共有多少种不同的排法？有多少种不同的排法？1 1）若甲在排尾上，则剩下的）若甲在排尾上，则剩下的）若甲在排尾上，则剩下的）若甲在排尾上，则剩下的5 5人可自由安排，有人可自由安排，有人可自由安排，有人可自由安排，有 种方法种方法种方法种方法. . 2 2）若甲在第）若甲在第）若甲在第）若甲在第2 2、3 3、6 6、7 7位，则位，则位，则位，则排尾的排法有排尾的排法有排尾的排法有排尾的排法有 种，乙的排法有种，乙的排法有种，乙的排法有种，乙的排法有 种种种种, , 第第第第2 2、3 3、6 6、7 7位的排法有位的排法有位的排法有位的排

11、法有 种种种种，根据分步计数原理，不，根据分步计数原理，不，根据分步计数原理，不，根据分步计数原理，不同的站法有同的站法有同的站法有同的站法有 种。种。种。种。3）再安排老师）再安排老师,有有2种方法。种方法。把握分类计数原理、分步计数原理是基础把握分类计数原理、分步计数原理是基础如图，某电子器件是由三个电如图，某电子器件是由三个电阻组成的回路阻组成的回路, ,其中有其中有6 6个焊接个焊接点点A A，B B，C C，D D，E E，F F，如果某个焊接点脱落，如果某个焊接点脱落，整个电路就会不通。现发现电路不通了整个电路就会不通。现发现电路不通了, , 那那么焊接点脱落的可能性共有（么焊接点

12、脱落的可能性共有（ ）（A） 6363种种 （B B）6464种种 （C C）6 6种种 （D D）3636种种分析分析:由加法原理可知由加法原理可知由乘法原理可知由乘法原理可知 222222-1=6322222-1=63A（1 1）0 0，1 1，2 2，3 3，4 4，5 5可组成多少个无重复数字可组成多少个无重复数字可组成多少个无重复数字可组成多少个无重复数字 且能被且能被且能被且能被5 5整除的五位数？整除的五位数？整除的五位数？整除的五位数？分类：个位数字为分类：个位数字为分类：个位数字为分类：个位数字为5 5或或或或0 0：个位数为个位数为个位数为个位数为0 0：个位数为个位数为个

13、位数为个位数为5 5：练习题练习题（2 2）0 0，1 1，2 2，3 3，4 4，5 5可组成多少个无重复数可组成多少个无重复数可组成多少个无重复数可组成多少个无重复数字且大于字且大于字且大于字且大于3125031250的五位数？的五位数？的五位数？的五位数？分类：分类：分类：分类：引申引申引申引申1 1：3125031250是由是由是由是由0 0，1 1，2 2，3 3，4 4，5 5组成的无重组成的无重组成的无重组成的无重复数字的五位数中从小到大第几个数？复数字的五位数中从小到大第几个数？复数字的五位数中从小到大第几个数？复数字的五位数中从小到大第几个数？方法一：（排除法）方法一：（排除

14、法）方法一：（排除法）方法一：（排除法）方法二：（直接法）方法二：（直接法）方法二：（直接法）方法二：（直接法）示例示例（20052005福建福建福建福建 理）从理）从理）从理）从6 6人中选人中选人中选人中选4 4人分别到巴黎、人分别到巴黎、人分别到巴黎、人分别到巴黎、伦敦、悉尼、莫斯科四个城市游览，要求每个城市有伦敦、悉尼、莫斯科四个城市游览，要求每个城市有伦敦、悉尼、莫斯科四个城市游览，要求每个城市有伦敦、悉尼、莫斯科四个城市游览，要求每个城市有一人游览，每人只游览一个城市，且这一人游览，每人只游览一个城市，且这一人游览，每人只游览一个城市，且这一人游览，每人只游览一个城市，且这6 6人

15、中甲、乙两人中甲、乙两人中甲、乙两人中甲、乙两人不去巴黎游览，则不同的选择方案共有人不去巴黎游览，则不同的选择方案共有人不去巴黎游览，则不同的选择方案共有人不去巴黎游览，则不同的选择方案共有_ A A300300种种种种B B240240种种种种 C C144144种种种种 D D9696种种种种B（间接法）（间接法）（间接法）（间接法）分析分析分析分析（直接法）分三种情况：（直接法）分三种情况：（直接法）分三种情况：（直接法）分三种情况：情况一情况一情况一情况一, ,不选甲、乙两个去游览不选甲、乙两个去游览不选甲、乙两个去游览不选甲、乙两个去游览情况二情况二情况二情况二: :甲、乙中有一人去

16、游览甲、乙中有一人去游览甲、乙中有一人去游览甲、乙中有一人去游览情况三情况三情况三情况三：甲、乙两人都去游览甲、乙两人都去游览甲、乙两人都去游览甲、乙两人都去游览综上不同的选择方案共有综上不同的选择方案共有综上不同的选择方案共有综上不同的选择方案共有 240240种种种种 1.1.从从4 4名男生和名男生和3 3名女生中选出名女生中选出4 4人参加某个人参加某个座谈会座谈会, ,若这若这4 4人中必须既有男生又有女生人中必须既有男生又有女生, ,则不同的选法共有则不同的选法共有_; ; 3434 种练习题练习题2.3 3成人成人2 2小孩乘船游玩小孩乘船游玩,1,1号船最多乘号船最多乘3 3人

17、人,2,2号船最多乘号船最多乘2 2人人,3,3号船只能乘号船只能乘1 1人人, ,他们任选他们任选2 2只船或只船或3 3只船只船, ,但小孩不能单独乘一只船但小孩不能单独乘一只船, ,这这5 5人共有人共有_乘船方法乘船方法. .2727种种特殊元素和特殊位置优先策略特殊元素和特殊位置优先策略示例示例由由0,1,2,3,4,5可以组成多少个没有重复可以组成多少个没有重复 数字五位奇数数字五位奇数. 解解:由于末位和首位有特殊要求由于末位和首位有特殊要求,应该优先安应该优先安 排排,以免不合要求的元素占了这两个位置以免不合要求的元素占了这两个位置先排末位共有先排末位共有_ 然后排首位共有然后

18、排首位共有_最后排其它位置共有最后排其它位置共有_由分步计数原理得由分步计数原理得=288特殊元素（或位置）优先安排特殊元素（或位置）优先安排示示例例 将将5 5列列车车停停在在5 5条条不不同同的的轨轨道道上上，其其中中a a列列车车不不停停在在第第一一轨轨道道上上，b b列列车车不不停停在在第第二二轨轨道道上上，则不同的停放方法有则不同的停放方法有_（A A）120120种种 （B B）9696种种 （C C）7878种种 （D D）7272种种解：解：解：解：（1 1）(2005 (2005 北京北京北京北京 文文文文) )五个工程队承建某项工程的五个工程队承建某项工程的五个工程队承建某

19、项工程的五个工程队承建某项工程的5 5个不同的子项目，每个工程队承建个不同的子项目，每个工程队承建个不同的子项目，每个工程队承建个不同的子项目，每个工程队承建1 1项，其中甲项，其中甲项，其中甲项，其中甲工程队不能承建工程队不能承建工程队不能承建工程队不能承建1 1号子项目，则不同的承建方案号子项目，则不同的承建方案号子项目，则不同的承建方案号子项目，则不同的承建方案共有（共有（共有（共有（ ）种。）种。）种。）种。（2 2）(2005 (2005 全国全国全国全国II II 理理理理) )在由数字在由数字在由数字在由数字0 0，1 1，2 2，3 3，4 4，5 5所组成的没有重复数字的四位

20、数中，不能被所组成的没有重复数字的四位数中，不能被所组成的没有重复数字的四位数中，不能被所组成的没有重复数字的四位数中，不能被整除的数共有整除的数共有整除的数共有整除的数共有_个个个个 192练习题练习题相邻相间问题相邻相间问题相邻元素捆绑策略相邻元素捆绑策略示例示例.7.7人站成一排人站成一排, ,其中甲乙相邻且丙丁其中甲乙相邻且丙丁相相 邻邻, ,共有多少种不同的排法共有多少种不同的排法. .甲甲乙乙丙丙丁丁由分步计数原理可得共有由分步计数原理可得共有种不同的排法种不同的排法=480解解: : 可先将甲乙两元素捆绑成整体并看成可先将甲乙两元素捆绑成整体并看成 一个复合元素，同时丙丁也看成一

21、个复合元素，同时丙丁也看成一个一个 复合元素，再与其它元素进行排复合元素，再与其它元素进行排列，列， 同时对相邻元素内部进行自排。同时对相邻元素内部进行自排。 某人射击某人射击8 8枪，命中枪，命中4 4枪，枪，4 4枪命中恰好枪命中恰好有有3 3枪连在一起的情形的不同种数为枪连在一起的情形的不同种数为_20练习题练习题不相邻问题插空策略不相邻问题插空策略示示 例例 一一个个晚晚会会的的节节目目有有4 4个个舞舞蹈蹈, ,2 2个个相相声声, ,3 3个个 独独唱唱, ,舞舞蹈蹈节节目目不不能能连连续续出出场场, ,则则节节目目的的出出 场场顺顺序序有有多多少少种种？解解: :分两步进行第一步

22、排分两步进行第一步排2 2个相声和个相声和3 3个独唱共个独唱共 有有 种，种， 第二步将第二步将4 4舞蹈插入第一步排舞蹈插入第一步排好的好的6 6个元素中间包含首尾两个空位共有个元素中间包含首尾两个空位共有种种 不同的方法不同的方法 由分步计数原理由分步计数原理,节目的节目的不同顺序共有不同顺序共有 种种相相相相独独独独独独不相邻问题不相邻问题插空法插空法 对于某几个元素不相邻得排列问题，可先将其它元素对于某几个元素不相邻得排列问题，可先将其它元素对于某几个元素不相邻得排列问题，可先将其它元素对于某几个元素不相邻得排列问题，可先将其它元素排好，然后再将不相邻的元素在已排好的元素之间及排好，

23、然后再将不相邻的元素在已排好的元素之间及排好，然后再将不相邻的元素在已排好的元素之间及排好，然后再将不相邻的元素在已排好的元素之间及两端的空隙之间插入即可。两端的空隙之间插入即可。两端的空隙之间插入即可。两端的空隙之间插入即可。例例例例5 75 7人站成一排照相，要求甲，乙，丙三人不相邻，人站成一排照相，要求甲，乙，丙三人不相邻，人站成一排照相，要求甲，乙，丙三人不相邻，人站成一排照相，要求甲，乙，丙三人不相邻，分别有多少种站法？分别有多少种站法？分别有多少种站法？分别有多少种站法？分析：可先让其余分析：可先让其余分析：可先让其余分析：可先让其余4 4人站好，共有人站好，共有人站好，共有人站好

24、，共有 种排法，再在种排法，再在种排法，再在种排法，再在这这这这4 4人之间及两端的人之间及两端的人之间及两端的人之间及两端的5 5个个个个“ “空隙空隙空隙空隙” ”中选三个位置让甲、中选三个位置让甲、中选三个位置让甲、中选三个位置让甲、乙、丙插入，则有乙、丙插入，则有乙、丙插入，则有乙、丙插入，则有 种方法，这样共有种方法，这样共有种方法，这样共有种方法，这样共有 种不种不种不种不同的排法。同的排法。同的排法。同的排法。（1 1）三个男生，四个女生排成一排，男生、女生）三个男生，四个女生排成一排，男生、女生）三个男生，四个女生排成一排，男生、女生）三个男生，四个女生排成一排，男生、女生各站

25、一起，有几种不同方法？各站一起，有几种不同方法？各站一起，有几种不同方法？各站一起，有几种不同方法？（2 2）三个男生，四个女生排成一排，三个男生，四个女生排成一排，三个男生，四个女生排成一排，三个男生，四个女生排成一排，男生之间、男生之间、男生之间、男生之间、女生之间不相邻，有几种不同排法？女生之间不相邻，有几种不同排法？女生之间不相邻，有几种不同排法？女生之间不相邻，有几种不同排法？捆绑法：捆绑法：插空法：插空法：（3 3）(2005 (2005 辽宁辽宁辽宁辽宁) )用、用、用、用、组成没有重复数字的八位数，要求与相邻，与组成没有重复数字的八位数，要求与相邻，与组成没有重复数字的八位数，

26、要求与相邻，与组成没有重复数字的八位数，要求与相邻，与相邻，与相邻，而与不相邻，这样的八位数共相邻，与相邻，而与不相邻，这样的八位数共相邻，与相邻，而与不相邻，这样的八位数共相邻，与相邻，而与不相邻，这样的八位数共有有有有_个（用数字作答）个（用数字作答）个（用数字作答）个（用数字作答） 练习题练习题(3)(2005 (3)(2005 辽宁辽宁辽宁辽宁) )用、用、用、用、组成没有重复数字的八位数，要求与相邻，组成没有重复数字的八位数，要求与相邻，组成没有重复数字的八位数，要求与相邻，组成没有重复数字的八位数，要求与相邻，与相邻，与相邻，而与不相邻，与相邻，与相邻，而与不相邻，与相邻，与相邻，

27、而与不相邻，与相邻，与相邻，而与不相邻，这样的八位数共有这样的八位数共有这样的八位数共有这样的八位数共有_个（用数字作答）个（用数字作答）个（用数字作答）个（用数字作答） 将与，与，与捆绑在一起排成一列将与，与，与捆绑在一起排成一列将与，与，与捆绑在一起排成一列将与，与，与捆绑在一起排成一列有有有有 种，再将、插入种，再将、插入种，再将、插入种，再将、插入4 4个空位中的两个个空位中的两个个空位中的两个个空位中的两个有有有有 种，故有种，故有种，故有种，故有 种种种种 引申引申引申引申: :用、组成没有重复数字用、组成没有重复数字用、组成没有重复数字用、组成没有重复数字的六位数，要求与相邻，与

28、相邻，与的六位数，要求与相邻，与相邻，与的六位数，要求与相邻，与相邻，与的六位数，要求与相邻，与相邻，与相邻，现将相邻，现将相邻，现将相邻，现将7 7、8 8 插进去，仍要求与相邻，与插进去，仍要求与相邻，与插进去，仍要求与相邻，与插进去，仍要求与相邻，与相邻，与相邻，那么插法共有相邻，与相邻，那么插法共有相邻，与相邻，那么插法共有相邻，与相邻，那么插法共有_种种种种（用数字作答）（用数字作答）（用数字作答）（用数字作答） “相邻相邻”用用“捆绑捆绑”，“不邻不邻”就就“插空插空”例例例例 七人排成一排，甲、乙两人必须相邻，且甲、乙七人排成一排，甲、乙两人必须相邻，且甲、乙七人排成一排，甲、乙

29、两人必须相邻，且甲、乙七人排成一排，甲、乙两人必须相邻，且甲、乙都不与丙相邻，则不同的排法有（都不与丙相邻，则不同的排法有（都不与丙相邻，则不同的排法有（都不与丙相邻，则不同的排法有（ ）种）种）种）种960960960960种种种种 （B B B B）840840840840种种种种 （C C C C）720720720720种种种种 （D D D D）600600600600种种种种解：解：解：解：另解：另解：另解：另解：练习练习练习练习 某城新建的一条道路上有某城新建的一条道路上有某城新建的一条道路上有某城新建的一条道路上有12121212只路灯，为了节只路灯，为了节只路灯，为了节只路灯

30、，为了节省用电而不影响正常的照明，可以熄灭其中三盏省用电而不影响正常的照明，可以熄灭其中三盏省用电而不影响正常的照明，可以熄灭其中三盏省用电而不影响正常的照明，可以熄灭其中三盏灯，但两端的灯不能熄灭，也不能熄灭相邻的两灯，但两端的灯不能熄灭，也不能熄灭相邻的两灯，但两端的灯不能熄灭，也不能熄灭相邻的两灯，但两端的灯不能熄灭，也不能熄灭相邻的两盏灯，可以熄灭的方法共有盏灯，可以熄灭的方法共有盏灯，可以熄灭的方法共有盏灯，可以熄灭的方法共有_（A A A A） 种（种（种（种（B B B B） 种种种种 （C C C C） 种种种种 （D D D D） 种种种种A练习题练习题定序问题倍缩空位插入策

31、略定序问题倍缩空位插入策略定序问题定序问题例例例例6 6 有有有有4 4名男生名男生名男生名男生,3 ,3名女生名女生名女生名女生. .3 3名女生名女生名女生名女生高矮互不等高矮互不等高矮互不等高矮互不等, ,将将将将7 7名学生名学生名学生名学生排成一行排成一行排成一行排成一行, ,要求从左到右要求从左到右要求从左到右要求从左到右, ,女生从矮到高排列女生从矮到高排列女生从矮到高排列女生从矮到高排列, ,有多少种排有多少种排有多少种排有多少种排法？法？法？法？顺序固定问题用顺序固定问题用“除法除法” 对于某几个元素顺序一定的排列问题，可先将这几对于某几个元素顺序一定的排列问题，可先将这几对

32、于某几个元素顺序一定的排列问题，可先将这几对于某几个元素顺序一定的排列问题，可先将这几个元素与其它元素一同进行排列，然后用总的排列个元素与其它元素一同进行排列，然后用总的排列个元素与其它元素一同进行排列，然后用总的排列个元素与其它元素一同进行排列，然后用总的排列数除以这几个元素的全排列数数除以这几个元素的全排列数数除以这几个元素的全排列数数除以这几个元素的全排列数. .所以共有所以共有所以共有所以共有 种。种。种。种。 分析：先在分析：先在分析：先在分析：先在7 7个位置上作全排列，有个位置上作全排列，有个位置上作全排列，有个位置上作全排列，有 种排法。其中种排法。其中种排法。其中种排法。其中

33、3 3个女生因要求个女生因要求个女生因要求个女生因要求“ “从矮到高从矮到高从矮到高从矮到高” ”排，只有一种顺序故排，只有一种顺序故排，只有一种顺序故排，只有一种顺序故 只只只只对应一种排法，对应一种排法，对应一种排法，对应一种排法，定序问题倍缩空位插入策略定序问题倍缩空位插入策略例例4.74.7人排队人排队, ,其中甲乙丙其中甲乙丙3 3人顺序一定共有多人顺序一定共有多 少不同的排法少不同的排法解:( (倍缩法倍缩法) )对于某几个元素顺序一定的排列对于某几个元素顺序一定的排列问题问题, ,可先把这几个元素与其他元素一起可先把这几个元素与其他元素一起进行排列进行排列, ,然后用总排列数除以

34、然后用总排列数除以这几个元这几个元素之间的全排列数素之间的全排列数, ,则共有不同排法种数则共有不同排法种数是：是： （空位法空位法）设想有）设想有7 7把椅子让除甲乙丙以外把椅子让除甲乙丙以外的四人就坐共有的四人就坐共有 种方法，其余的三个种方法，其余的三个位置甲乙丙共有位置甲乙丙共有 种坐法，则共有种坐法，则共有 种种 方法方法 1思考思考: :可以先让甲乙丙就坐吗可以先让甲乙丙就坐吗? ?分房问题分房问题又名：住店法，又名：住店法，重排问题求幂策略重排问题求幂策略住店法住店法住店法住店法解决解决解决解决“ “允许重复排列问题允许重复排列问题允许重复排列问题允许重复排列问题” ”要注意区分

35、两类元素：要注意区分两类元素：要注意区分两类元素：要注意区分两类元素： 一类元素可以重复，另一类不能重复，把不能重复的一类元素可以重复，另一类不能重复，把不能重复的一类元素可以重复，另一类不能重复，把不能重复的一类元素可以重复，另一类不能重复，把不能重复的元素看作元素看作元素看作元素看作“ “客客客客” ”，能重复的元素看作，能重复的元素看作，能重复的元素看作，能重复的元素看作“ “店店店店” ”，再利用，再利用，再利用，再利用乘法原理直接求解。乘法原理直接求解。乘法原理直接求解。乘法原理直接求解。示例示例示例示例 七名学生争夺五项冠军七名学生争夺五项冠军七名学生争夺五项冠军七名学生争夺五项冠

36、军, ,每项冠军只能由一人获每项冠军只能由一人获每项冠军只能由一人获每项冠军只能由一人获得得得得, ,获得冠军的可能的种数有获得冠军的可能的种数有获得冠军的可能的种数有获得冠军的可能的种数有_A. B. C D.A. B. C D.分析：因同一学生可以同时夺得分析：因同一学生可以同时夺得分析：因同一学生可以同时夺得分析：因同一学生可以同时夺得n n项冠军，故学生可重复排列，项冠军，故学生可重复排列，项冠军，故学生可重复排列，项冠军，故学生可重复排列，将七名学生看作将七名学生看作将七名学生看作将七名学生看作7 7家家家家“ “店店店店” ”，五项冠军看作，五项冠军看作，五项冠军看作，五项冠军看作

37、5 5名名名名“ “客客客客” ”，每个，每个，每个，每个“ “客客客客” ”有有有有7 7种住宿法，由乘法原理得种住宿法，由乘法原理得种住宿法，由乘法原理得种住宿法，由乘法原理得 种。种。种。种。注：对此类问题，常有疑惑，为什么不是注：对此类问题，常有疑惑，为什么不是注：对此类问题，常有疑惑，为什么不是注：对此类问题，常有疑惑，为什么不是 呢？呢？呢？呢？用分步计数原理看，用分步计数原理看，用分步计数原理看，用分步计数原理看，5 5是步骤数，自然是指数。是步骤数，自然是指数。是步骤数，自然是指数。是步骤数，自然是指数。重排问题求幂策略重排问题求幂策略示例示例. .把把6 6名实习生分配到名实

38、习生分配到7 7个车间实习个车间实习, ,共有共有 多少种不同的分法多少种不同的分法解解: :完成此事共分六步完成此事共分六步: :把第一名实习生分配把第一名实习生分配 到车间有到车间有 种分法种分法. .7 7把第二名实习生分配把第二名实习生分配 到车间也有到车间也有7 7种分法，种分法， 依此类推依此类推, ,由分步计由分步计数原理共有数原理共有 种不同的排法种不同的排法. .多排问题直排策略多排问题直排策略示例示例.8.8人排成前后两排人排成前后两排, ,每排每排4 4人人, ,其中甲乙在其中甲乙在 前排前排, ,丁在后排丁在后排, ,共有多少排法共有多少排法解解:8人排前后两排人排前后

39、两排,相当于相当于8人坐人坐8把椅子把椅子,可以可以 把椅子排成一排把椅子排成一排. 先在前先在前4个位置排甲乙两个位置排甲乙两个特殊元素有个特殊元素有_种种,再排后再排后4个位置上的个位置上的特殊元素有特殊元素有_种种,其余的其余的5人在人在5个位置个位置上任意排列有上任意排列有_种种,则共有则共有_种种.前排后排后排一般地一般地, ,元素分成多排的排列问题元素分成多排的排列问题, ,可归结为一排考虑可归结为一排考虑, ,再分段研究再分段研究. .小集团问题小集团问题小集团问题先整体局部策略小集团问题先整体局部策略示例示例. .用用1,2,3,4,51,2,3,4,5组成没有重复数字的五位数

40、组成没有重复数字的五位数 其中恰有两个偶数夹其中恰有两个偶数夹1,1,在两个奇数之在两个奇数之 间间, ,这样的五位数有多少个？这样的五位数有多少个？解：把解：把,当作一个小集团与排队当作一个小集团与排队共有共有_种排法，再排小集团内部共有种排法，再排小集团内部共有_种排法，由分步计数原理共有种排法，由分步计数原理共有_种排法种排法.31524小集团小集团小集团排列问题中，先整体后局小集团排列问题中，先整体后局部，再结合其它策略进行处理。部，再结合其它策略进行处理。.计划展出计划展出10幅不同的画幅不同的画,其中其中1幅水彩画幅水彩画,幅油画幅油画,幅国画幅国画, 排成一行陈列排成一行陈列,要

41、求同一要求同一品种的必须连在一起，并且水彩画不在两品种的必须连在一起，并且水彩画不在两端，那么共有陈列方式的种数为端，那么共有陈列方式的种数为_2. 5男生和女生站成一排照像男生和女生站成一排照像,男生相邻男生相邻,女女生也相邻的排法有生也相邻的排法有_种种练习题练习题元素相同问题隔板策略元素相同问题隔板策略应用背景：相同元素的名额分配问题应用背景：相同元素的名额分配问题 不定方程的正整数解问题不定方程的正整数解问题隔板法的使用特征：隔板法的使用特征：相同的元素分成若干部分，每部分至少一个相同的元素分成若干部分，每部分至少一个元素相同问题隔板策略元素相同问题隔板策略示例示例 有有1010个运动

42、员名额，在分给个运动员名额，在分给7 7个班，每个班，每班至少一个班至少一个, ,有多少种分配方案？有多少种分配方案？ 解：因为解：因为10个名额没有差别，把它们排成个名额没有差别，把它们排成一排。相邻名额之间形成个空隙。一排。相邻名额之间形成个空隙。在个空档中选个位置插个隔板，在个空档中选个位置插个隔板，可把名额分成份，对应地分给个可把名额分成份，对应地分给个班级，每一种插板方法对应一种分法班级，每一种插板方法对应一种分法共有共有_种分法。种分法。一班二班三班四班五班六班七班将将n n个相同的元素分成个相同的元素分成m m份（份（n n，m m为正整数）为正整数）, ,每份至少一个元素每份至

43、少一个元素, ,可以用可以用m-1m-1块隔板，插入块隔板，插入n n个元素排成一排的个元素排成一排的n-1n-1个空隙中，所有分法数个空隙中，所有分法数为为（1 1 1 1）将）将）将）将10101010个学生干部的培训指标分配给个学生干部的培训指标分配给个学生干部的培训指标分配给个学生干部的培训指标分配给7 7 7 7个不同个不同个不同个不同的班级，每班至少分到一个名额，不同的分配方的班级，每班至少分到一个名额，不同的分配方的班级，每班至少分到一个名额，不同的分配方的班级，每班至少分到一个名额，不同的分配方案共有案共有案共有案共有_种。种。种。种。（2 2）不定方程）不定方程）不定方程）不

44、定方程 的正整数解的正整数解的正整数解的正整数解共有共有共有共有_组组组组. .练习题练习题平均分组问题除法策略平均分组问题除法策略“分书问题分书问题”平均分组问题除法策略平均分组问题除法策略示例示例. 6本不同的书平均分成本不同的书平均分成3堆堆,每堆每堆2本共有本共有 多少分法？多少分法？解解: 分三步取书得分三步取书得 种方法种方法,但这里出现但这里出现 重复计数的现象重复计数的现象,不妨记不妨记6本书为本书为ABCDEF 若第一步取若第一步取AB,第二步取第二步取CD,第三步取第三步取EF 该分法记为该分法记为(AB,CD,EF),则则 中还有中还有 (AB,EF,CD),(CD,AB

45、,EF),(CD,EF,AB) (EF,CD,AB),(EF,AB,CD)共有共有 种取法种取法 ,而而 这些分法仅是这些分法仅是(AB,CD,EF)一种分法一种分法,故共故共 有有 种分法。种分法。1 将将13个球队分成个球队分成3组组,一组一组5个队个队,其它两组其它两组4 个队个队, 有多少分法？有多少分法？2.10名学生分成名学生分成3组组,其中一组其中一组4人人, 另两组另两组3人人 但正副班长不能分在同一组但正副班长不能分在同一组,有多少种不同有多少种不同 的分组方法的分组方法 （1540）3.3.某校高二年级共有六个班级，现从外地转某校高二年级共有六个班级，现从外地转 入入4 4

46、名学生，要安排到该年级的两个班级且每名学生，要安排到该年级的两个班级且每班安排班安排2 2名，则不同的安排方案种数为名，则不同的安排方案种数为_ 练习题练习题分清排列、组合、等分的算法区别分清排列、组合、等分的算法区别示例示例 (1)(1)(1)(1)今有今有今有今有10101010件不同奖品件不同奖品件不同奖品件不同奖品, , , ,从中选从中选从中选从中选6 6 6 6件分给甲一件件分给甲一件件分给甲一件件分给甲一件, , , ,乙二件和丙三件乙二件和丙三件乙二件和丙三件乙二件和丙三件, , , ,有多少种分法有多少种分法有多少种分法有多少种分法? ? ? ? (2) (2) (2) (2

47、) 今有今有今有今有10101010件不同奖品件不同奖品件不同奖品件不同奖品, , , , 从中选从中选从中选从中选6 6 6 6件分给三人件分给三人件分给三人件分给三人, , , ,其中其中其中其中1 1 1 1人一件人一件人一件人一件1 1 1 1人二件人二件人二件人二件1 1 1 1人三件人三件人三件人三件, , , , 有多少种分法有多少种分法有多少种分法有多少种分法? ? ? ?(3) (3) (3) (3) 今有今有今有今有10101010件不同奖品件不同奖品件不同奖品件不同奖品, , , , 从中选从中选从中选从中选6 6 6 6件分成三份件分成三份件分成三份件分成三份, , ,

48、 ,每份每份每份每份2 2 2 2件件件件, , , , 有多少种分法有多少种分法有多少种分法有多少种分法? ? ? ? 解：（1） （2）(3) (1) (1) (1) (1)今有今有今有今有10101010件不同奖品件不同奖品件不同奖品件不同奖品, , , ,从中选从中选从中选从中选6 6 6 6件分成三份件分成三份件分成三份件分成三份, , , , 二二二二份各份各份各份各1 1 1 1件件件件, , , ,另一份另一份另一份另一份4 4 4 4件件件件, , , , 有多少种分法有多少种分法有多少种分法有多少种分法? ? ? ? (2) (2) (2) (2)今有今有今有今有10101

49、010件不同奖品件不同奖品件不同奖品件不同奖品, , , ,从中选从中选从中选从中选6 6 6 6件分给甲乙丙三件分给甲乙丙三件分给甲乙丙三件分给甲乙丙三人人人人, , , ,每人二件有多少种分法每人二件有多少种分法每人二件有多少种分法每人二件有多少种分法? ? ? ?解解: (1)(2)练习题练习题先选后排问题先选后排问题排列组合混合问题先选后排策略排列组合混合问题先选后排策略示例示例. .有有5 5个不同的小球个不同的小球, ,装入装入4 4个不同的盒内个不同的盒内, , 每盒至少装一个球每盒至少装一个球, ,共有多少不同的装法共有多少不同的装法. .解解: :第一步从第一步从5 5个球中

50、选出个球中选出2 2个组成复合元共个组成复合元共 有有_种方法种方法. .再把再把5 5个元素个元素( (包含一个复合包含一个复合 元素元素) )装入装入4 4个不同的盒内有个不同的盒内有_种方法种方法. .根据分步计数原理装球的方法共有根据分步计数原理装球的方法共有_解决排列组合混合问题解决排列组合混合问题, ,先选后排是最基本先选后排是最基本的指导思想的指导思想. .此法与此法与相邻元素捆绑策略相似吗?练习题练习题一个班有一个班有6 6名战士名战士, ,其中正副班长各其中正副班长各1 1人人现从中选现从中选4 4人完成四种不同的任务人完成四种不同的任务, ,每人每人完成一种任务完成一种任务

51、, ,且正副班长有且只有且正副班长有且只有1 1人人参加参加, ,则不同的选法有则不同的选法有_ _ 种种1921923 名医生和名医生和 6 名护士被分配到名护士被分配到 3 所所学校为学生体检学校为学生体检,每校分配每校分配 1 名医生名医生和和 2 名护士名护士,不同的分配方法共有多不同的分配方法共有多少种少种?先选后排问题的处理方法先选后排问题的处理方法解法解法1:先组队后分校先组队后分校(先分堆后分配先分堆后分配) 1.为支援西部开发为支援西部开发,有有3名教师去银川市名教师去银川市三所学校任教三所学校任教,每校分配每校分配1人人,不同的分不同的分配方法共有配方法共有_种种(用数字作

52、答用数字作答).改为改为4名教师？名教师？改为改为5名教师？名教师？练习题练习题2.有甲、乙、丙三项任务有甲、乙、丙三项任务,甲需甲需2人承人承担担,乙、丙各需乙、丙各需1人承担人承担.从从10人中选人中选派派4人承担这三项任务人承担这三项任务,不同的选法不同的选法共有多少种共有多少种?练习题练习题1 1 1 1、有甲、乙、丙三项工程，甲需要、有甲、乙、丙三项工程，甲需要、有甲、乙、丙三项工程，甲需要、有甲、乙、丙三项工程，甲需要 2 2 2 2 人承担，人承担，人承担，人承担，乙、丙各需乙、丙各需乙、丙各需乙、丙各需 1 1 1 1 人承担，从人承担，从人承担，从人承担，从 10 10 10

53、 10 人中选派人中选派人中选派人中选派 4 4 4 4 人承担这人承担这人承担这人承担这三项任务，不同的承担方法共有三项任务，不同的承担方法共有三项任务，不同的承担方法共有三项任务，不同的承担方法共有_种；种；种；种；2 2 2 2、某办公室有、某办公室有、某办公室有、某办公室有 5 5 5 5 人办公，现要排一个周轮值表，人办公，现要排一个周轮值表，人办公，现要排一个周轮值表，人办公，现要排一个周轮值表，每人至少一天，其中甲不能在周六和周日，且甲肯定每人至少一天，其中甲不能在周六和周日，且甲肯定每人至少一天，其中甲不能在周六和周日，且甲肯定每人至少一天，其中甲不能在周六和周日，且甲肯定值两

54、天，则不同的排表方式有值两天，则不同的排表方式有值两天，则不同的排表方式有值两天，则不同的排表方式有_种；种；种；种；3 3 3 3、 学校决定下周对高一年级进学校决定下周对高一年级进学校决定下周对高一年级进学校决定下周对高一年级进行教学情况抽测。决定基础科抽两门，行教学情况抽测。决定基础科抽两门，行教学情况抽测。决定基础科抽两门，行教学情况抽测。决定基础科抽两门，文科、理科各抽一门，技能科（音、文科、理科各抽一门，技能科（音、文科、理科各抽一门，技能科（音、文科、理科各抽一门，技能科（音、体、美、信）抽一门。则可能有体、美、信）抽一门。则可能有体、美、信）抽一门。则可能有体、美、信）抽一门。

55、则可能有种抽取方法。种抽取方法。种抽取方法。种抽取方法。基础训练基础训练练练 习习 ：（不对号入座问题）：（不对号入座问题）（1 1 1 1）（）（）（）（2004200420042004湖北）将标号为湖北）将标号为湖北）将标号为湖北）将标号为1 1 1 1，2 2 2 2，3 3 3 3，10101010的的的的10101010个球放入标号为个球放入标号为个球放入标号为个球放入标号为1 1 1 1，2 2 2 2，3 3 3 3，10101010的的的的10101010个盒子中，个盒子中，个盒子中，个盒子中，每个盒内放一个球，恰好有每个盒内放一个球，恰好有每个盒内放一个球，恰好有每个盒内放一

56、个球，恰好有3 3 3 3个球的标号与其所在盒子个球的标号与其所在盒子个球的标号与其所在盒子个球的标号与其所在盒子的标号不一致的放入方法有的标号不一致的放入方法有的标号不一致的放入方法有的标号不一致的放入方法有_种种种种（2 2 2 2）编号为）编号为）编号为）编号为1 1 1 1、2 2 2 2、3 3 3 3、4 4 4 4、5 5 5 5的五个球放入编号为的五个球放入编号为的五个球放入编号为的五个球放入编号为1 1 1 1、2 2 2 2、3 3 3 3、4 4 4 4、5 5 5 5的五个盒子里，至多有的五个盒子里，至多有的五个盒子里，至多有的五个盒子里，至多有2 2 2 2个对号入座

57、的个对号入座的个对号入座的个对号入座的情形有情形有情形有情形有_种种种种109直接法：直接法：直接法：直接法：间接法：间接法：间接法：间接法：注意区别注意区别“恰好恰好”与与“至少至少”从从从从6 6 6 6双不同颜色的手套中任取双不同颜色的手套中任取双不同颜色的手套中任取双不同颜色的手套中任取4 4 4 4只，其中恰好有一双只，其中恰好有一双只，其中恰好有一双只，其中恰好有一双同色的手套的不同取法共有（同色的手套的不同取法共有（同色的手套的不同取法共有（同色的手套的不同取法共有（ ） (A) 480(A) 480(A) 480(A) 480种（种（种（种（B B B B）2402402402

58、40种种种种 （C C C C）180180180180种种种种 （D D D D）120120120120种种种种小结：小结：小结：小结：“ “恰好有一个恰好有一个恰好有一个恰好有一个” ”是是是是“ “只有一个只有一个只有一个只有一个” ”的意思。的意思。的意思。的意思。“ “至至至至少有一个少有一个少有一个少有一个” ”则是则是则是则是“ “有一个或一个以上有一个或一个以上有一个或一个以上有一个或一个以上” ”，可用分类讨，可用分类讨，可用分类讨，可用分类讨论法求解，它也是论法求解，它也是论法求解，它也是论法求解，它也是“ “没有一个没有一个没有一个没有一个” ”的反面，故可用的反面，故

59、可用的反面，故可用的反面，故可用“ “排排排排除法除法除法除法” ”。解：解：练习练习 从从6双不同颜色的手套中任取双不同颜色的手套中任取4只，其中至只，其中至少有一双同色手套的不同取法共有少有一双同色手套的不同取法共有_种种解：解：对于条件比较复杂的排列组合问题对于条件比较复杂的排列组合问题, ,不易用不易用公式进行运算公式进行运算, ,往往利用穷举法或画出树状往往利用穷举法或画出树状图会收到意想不到的结果图会收到意想不到的结果. .练习题练习题1.1.同一寝室同一寝室4 4人人, ,每人写一张贺年卡集中起来每人写一张贺年卡集中起来, ,2.2. 然后每人各拿一张别人的贺年卡，则四然后每人各拿一张别人的贺年卡，则四张张3.3. 贺年卡不同的分配方式有多少种？贺年卡不同的分配方式有多少种？(9种种)2.2.给图中区域涂色给图中区域涂色, ,要求相邻区要求相邻区 域不同色域不同色, ,现有现有4 4种可选颜色种可选颜色, ,则则 不同的着色方法有不同的着色方法有_种种213457272谢谢观赏！2020/11/554