排列与组合-PPT课件.ppt

排列组合复习排列组合复习 1基本原理组合排列排列数公式组合数公式组合数性质应用问题 知识结构网络图：知识结构网络图：2两个原理的区别与联系两个原理的区别与联系做一件事或完成一项工作的方法数做一件事或完成一项工作的方法数各类间相互独立各类间相互独立每一类都每一类都 直接完成直接完成各步间相互联系各步间相互联系依次完成每一步后依次完成每一步后间接完成间接完成完成一件事，有完成一件事，有n n类办法，类办法，在第一类办法中有在第一类办法中有m m1 1种不同的方法，种不同的方法，在第二类办法中有在第二类办法中有m m2 2种不同的方法种不同的方法，在第在第n n类办法中有类办法中有m mn n种不同的方法，种不同的方法，那么完成这件事共有那么完成这件事共有 N=mN=m1 1+m+m2 2+m+m3 3+m mn n种不同的方法种不同的方法完成一件事，需要分成完成一件事，需要分成n n个步骤，个步骤，做第一步有做第一步有m m1 1种不同的方法，种不同的方法，做第二步有做第二步有m m2 2种不同的方法种不同的方法，做第做第n n步有步有m mn n种不同的方法，种不同的方法，那么完成这件事共有那么完成这件事共有 N=mN=m1 1m m2 2m m3 3m mn n 种不同的方法种不同的方法.“步步”与与“步步”间连续间连续“类类”与与“类类”间间既不重复也不遗漏既不重复也不遗漏3例：例：(1)4(1)4封信投入封信投入3 3 个信箱，不同的投信方法有个信箱，不同的投信方法有多少种？多少种？(2)(2)在所有两位数中，个位数字大于十位数字的在所有两位数中，个位数字大于十位数字的有多少个？有多少个？解：（解：（1 1）分四步，依次把每一封信投入）分四步，依次把每一封信投入信箱有信箱有3 3种方法，由分步计数原理共有：种方法，由分步计数原理共有：(2)(2)按十位数字是按十位数字是1 1，2 2，3 37 7，8 8共分成共分成8 8类满足条件的两位数分别有类满足条件的两位数分别有8 8、7 7、6 6、5 5、4 4、3 3、2 2、1 1个。由分类计数原理个。由分类计数原理共有：共有：8+7+6+5+4+3+2+1=368+7+6+5+4+3+2+1=36（个）（个）法法2 2：用所有非零数字组成的两位数个数减去：用所有非零数字组成的两位数个数减去个位数和十位数相等的两位数个数，再除以个位数和十位数相等的两位数个数，再除以2.2.即即4排列和组合的区别与联系排列和组合的区别与联系从从n n个不同元素中取出个不同元素中取出m m个元个元素，按一定的顺序排成一列素，按一定的顺序排成一列从从n n个不同元素中取出个不同元素中取出m m个元个元素，并成一组素，并成一组所有排列的个数所有排列的个数,记为：记为：所有组合的个数，记为：所有组合的个数，记为：5有有条条件件的的排排列列组组合合问问题题有有条条件件的的排排列列组组合合问问题题 例例:七个家庭一起外出旅游，若其中四家是一个男孩，三家是一个女孩，现将这七个小孩站成一排照相留念。a)若三个女孩要站在一起，有多少种不同的排法？解：将三个女孩看作一人与四个男孩排队，有 种排法，而三个女孩之间有 种排法，所以不同的排法共有：（种）。捆捆 绑绑 法法6有有条条件件的的排排列列问问题题 七个家庭一起外出旅游，若其中四家是男孩，三家是女孩，现将这七个小孩站成一排照相留念。b)若三个女孩要站在一起，四个男孩也 要站在一起，有多少种不同的排法？不同的排法有：（种）说一说说一说捆绑法一般适用于 问题的处理。相邻相邻7有有条条件件的的排排列列问问题题 七个家庭一起外出旅游，若其中四家是男孩，三家是女孩，现将这七个小孩站成一排照相留念。c)若三个女孩互不相邻，有多少种不同的排法？解：先把四个男孩排成一排有 种排法，在每一排列中有五个空档（包括两端），再把三个女孩插入空档中有 种方法，所以共有：（种）排法。8有有条条件件的的排排列列问问题题 七个家庭一起外出旅游，若其中四家是男孩，三家是女孩，现将这七个小孩站成一排照相留念。c)若三个女孩互不相邻，有多少种不同的排法？插插 空空 法法9大家有疑问的，可以询问和交流大家有疑问的，可以询问和交流可以互相讨论下，但要小声点可以互相讨论下，但要小声点可以互相讨论下，但要小声点可以互相讨论下，但要小声点10有有条条件件的的排排列列问问题题 七个家庭一起外出旅游，若其中四家是男孩，三家是女孩，现将这七个小孩站成一排照相留念。d)若三个女孩互不相邻，四个男孩也互不相邻，有多少种不同的排法？不同的排法共有：（种）说一说说一说插空法一般适用于 问题的处理。互不相邻互不相邻11B有有条条件件的的排排列列问问题题 七个家庭一起外出旅游，若其中四家是男孩，三家是女孩，现将这七个小孩站成一排照相留念。e)若其中的A小孩必须站在B小孩的左边，有多少种不同的排法？BAA解：A在B左边的一种排法必对应着A在B右边的一种排法，所以在全排列中，A在B左边与A在B右边的排法数相等，因此有：排法。（种）12有有条条件件的的排排列列问问题题 七个家庭一起外出旅游，若其中四家是男孩，三家是女孩，现将这七个小孩站成一排照相留念。e)若其中的A小孩必须站在B小孩的左边，有多少种不同的排法？BA对对 应应 法法更更多多对应法适用于有几个特殊元素对应法适用于有几个特殊元素_问题问题顺序固定顺序固定13互不相邻问题互不相邻问题相邻问题剩余组分类少剩余组分类少顺序固定问题分组问题逆向思考作作业业141.有有1212名划船运动员名划船运动员,其中其中3 3人只会划左舷人只会划左舷,4,4人只会划右舷人只会划右舷,其它其它5 5人既会划左舷人既会划左舷,又会划右又会划右舷舷,现要从这现要从这1212名运动员中选出名运动员中选出6 6人平均分在人平均分在左右舷参加划船比赛左右舷参加划船比赛,有多少种不同的选法有多少种不同的选法?综合练习综合练习分析：按划左舷人选分类：分析：按划左舷人选分类：1.从只会划左舷的从只会划左舷的3 人中选人中选3 人划左舷，再从剩下的人划左舷，再从剩下的9人中选人中选3个划右舷个划右舷:2.从左右舷都会划的从左右舷都会划的5人中选人中选 3人划左舷，再从剩下会划右舷的人划左舷，再从剩下会划右舷的6人中选人中选3个划右舷个划右舷:故，参赛选手的选法共有：故，参赛选手的选法共有：作作业业152.求方程 的正整数解的组数。分析：分析：（隔板法）（隔板法）将将8写成写成8个个1，排成一排，排成一排，8个个1中间有中间有7个空个空档，用档，用3块隔板放入空档，使块隔板放入空档，使8个个1 被分成被分成4段，每段内段，每段内1的个数的个数恰好对应方程的一组正整数解。恰好对应方程的一组正整数解。解：方程的正整数解组数为：解：方程的正整数解组数为：163.甲、乙两自然数的最大公约数为720，问甲、乙两自然数的公约数共有多少个？分析：求公约数就是最大公约数分析：求公约数就是最大公约数720的所有的所有约数。分解质因数约数。分解质因数，得：，得：，约数可看成是从质因数中取出部分或全部，约数可看成是从质因数中取出部分或全部的乘积。的乘积。所以，所以，甲、乙两自然数的公约数共有甲、乙两自然数的公约数共有 个个第第1步因数步因数2的取法有：的取法有：0个、个、1个、个、2个、个、3个、个、4个共个共5种方法，第种方法，第2步因数步因数3的取法有：的取法有：0个、个、1个、个、2个共个共3种，第种，第3步因数步因数5的取法的取法有：有：0个、个、1个，由乘法原理，共有：个，由乘法原理，共有：17作业 解解18