排列组合之排列与组合

排列组合山东省实验中学宁华老师信息竞赛课件引例•（1）从1、2、3这3个数中任取2个数的排列有哪些？•（2）从1、2、3这3个数中任取2个数的组合有哪些？山东省实验中学宁华老师信息竞赛课件解答•（1）从1、2、3这3个数中任取2个数的排列有哪些？•共6种排列：•12，21•13，31•23，32•排列数记作：•（2）从1、2、3这3个数中任取2个数的组合有哪些？•共3种组合：•12，13，23•组合数记作：P=632C=332山东省实验中学宁华老师信息竞赛课件排列和排列数•(1)排列：从n个不同元素中，任取m(m≤n)个元素，按照一定的顺序排成一列，叫做从n个不同元素中取出m个元素的一个排列。•从排列的定义可知，如果两个排列相同，不仅这两个排列的元素必须完全相同，而且排列的顺序必须完全相同，这就告诉了我们如何判断两个排列是否相同的方法。山东省实验中学宁华老师信息竞赛课件•(2)排列数：从n个不同元素中取出m(m≤n)个元素的所有排列的个数，记作。•排列数公式：=n(n-1)(n-2)…(n-m+1)=•当m=n时，称为全排列。全排列数公式为：=n(n-1)(n-2)…3·2·1＝n！PnnPnmPnmn!(n-m)!山东省实验中学宁华老师信息竞赛课件组合和组合数•(1)组合：从n个不同元素中，任取m(m≤n)个元素并成一组，叫做从n个不同元素中取出m个元素的一个组合。•从组合的定义知，如果两个组合中的元素完全相同，不管元素的顺序如何，都是相同的组合；只有当两个组合中的元素不完全相同时，才是不同的组合。山东省实验中学宁华老师信息竞赛课件•(2)组合数：从n个不同元素中取出m(m≤n)个元素的所有组合的个数，记作。•组合数公式：mnCCnmn!m!(n-m)!mnPmmPn(n-1)(n-2)...(n-m+1)m!mnC=故山东省实验中学宁华老师信息竞赛课件组合数性质•性质1：•性质2：•证明：mnnmnCC111mnmnmnCCC)1(0nC山东省实验中学宁华老师信息竞赛课件排列与组合•排列与元素的顺序有关，组合与顺序无关。如2，3，1与2，1，3是两个排列，而2，3，1与2，1，3是一个组合。•从n个不同元素中，任取m(m≤n)个元素，“按照一定的顺序排成一列”与“不管怎样的顺序并成一组”这是有本质区别的。山东省实验中学宁华老师信息竞赛课件解排列组合问题的常用方法•一、运用两个基本原理•二、特殊元素（位置）优先•三、捆绑法•四、插入法•五、排除法•六、机会均等法•七、转化法•八、隔板法•……山东省实验中学宁华老师信息竞赛课件一、运用两个基本原理•加法原理和乘法原理是解排列组合应用题的最基本的出发点，可以说对每道应用题我们都要考虑在记数的时候进行分数或分步处理。山东省实验中学宁华老师信息竞赛课件加法原理和分类计数法•1．加法原理•2．分类的要求每一类中的每一种方法都可以独立地完成此任务；两类不同办法中的具体方法，互不相同(即分类不重)；完成此任务的任何一种方法，都属于某一类(即分类不漏)。山东省实验中学宁华老师信息竞赛课件乘法原理和分步计数法•1．乘法原理•2．合理分步的要求任何一步的一种方法都不能完成此任务，必须且只须连续完成这n步才能完成此任务；各步计数相互独立；只要有一步中所采取的方法不同，则对应的完成此事的方法也不同。山东省实验中学宁华老师信息竞赛课件•用1,2,3,4,5,6这六个数字能组成多少个每一位数字都不同的六位数？•解：从左到右每一位填一个数字，可分6步完成：•第1步：填左边第一位，有6种填法；•第2步：填左边第一位，有5种填法；•……•第6步：填最右边一位，有1种填法。•所以，根据乘法原理，共有6*5*4*3*2*1=720个。例山东省实验中学宁华老师信息竞赛课件•解法2：此题即求1，2，3，4，5，6的全排列数，所以N=720!666P山东省实验中学宁华老师信息竞赛课件•n个人参加某项资格考试，能否通过，有多少种可能的结果？•解法1：用分类记数的原理。（加法原理）没有人通过，有种结果；1个人通过，有种结果；……；n个人通过，有种结果。所以一共有种可能的结果。CCCnnnnn012Cn0Cn1nnC例山东省实验中学宁华老师信息竞赛课件•解法2：用分步记数的原理。（乘法原理）第一个人有种可能，第二个人，……，第n个人也是这样，所以一共有2*2*…*2=2n种可能的结果。通过与不通过两也是这样山东省实验中学宁华老师信息竞赛课件•一个三位密码锁，每位上的数字都从0,1,2,……,9十个数字中选择。•（1）若各位上的数字允许重复，则可以设置多少种密码？•（2）首位数字不为0呢？•（3）首位数字为0呢？•（1’）若各位上的数字不允许重复呢？例山东省实验中学宁华老师信息竞赛课件•解：•（1）按密码位数,从左到右依次设置第一位、第二位、第三位，需分为三步完成：第一步，m1=10；第二步，m2=10；第三步，m3=10。根据乘法原理,共可以设置N=10×10×10=1000种密码。山东省实验中学宁华老师信息竞赛课件•问：若设置四位、五位、六位、……密码,各位数字可以重复，则密码数分别有多少种呢？•答：它们的密码种数依次是104,105,106,……种。山东省实验中学宁华老师信息竞赛课件•（2）首位数字不为0的密码数是N=9×10×10=900种。•（3）首位数字是0的密码数是N=1×10×10=100种。•由此可以看出,首位数字不为0的密码数与首位数字是0的密码数之和等于密码总数(各位允许重复的情况)。山东省实验中学宁华老师信息竞赛课件•（1’）解：•法1：按密码位数,从左到右依次设置第一位、第二位、第三位，需分为三步完成：第一步，m1=10；第二步，m2=9；第三步，m3=8。根据乘法原理,共可以设置N=10×9×8=720种密码。•法2：此题即求从10个数字中选3个的排列数，所以N=7208*9*10310P山东省实验中学宁华老师信息竞赛课件二、特殊元素（位置）优先•例：从0，1，……，9这10个数字中选取5个不同数字组成5位的偶数，共有多少个？山东省实验中学宁华老师信息竞赛课件•解：可分为两类：•第一类：个位填0，有个；•第二类：个位不填0且万位不能填0，分三步：第一步：填个位第二步：填万位第三步：填其他位所以第二类共有个；•所以一共可以得到个偶数。•注：0，2，4，6，8是特殊元素，元素0更为特殊，首位与末位是特殊的位置。CCP4181831377638181449PCCPC41C81P83P94山东省实验中学宁华老师信息竞赛课件例•8人站成两排，每排4人，甲在前排，乙不在后排的边上，一共有多少种排法？•解：分三步：•第一步：先排甲，有种排法。•第二步：再排乙，有种排法，•第三步：再排其余的人，又有种排法，•所以一共有种排法。PPP41516614400P41P51P66山东省实验中学宁华老师信息竞赛课件三、捆绑法•例：8人排成一排，甲、乙必须分别紧靠站在丙的两旁，有多少种排法？•解：•先把甲、乙、丙先排好，有种排法；•再把这三个人“捆绑”在一起看成是一个，与其余5个人，总共相当于6个排成一排，有种排法；•所以一共有种排法。P22P6614406622PP山东省实验中学宁华老师信息竞赛课件四、插入法•例：排一张有8个节目的演出表，其中有3个小品。小品节目不能排在第一个，也不能有两个小品排在一起。有几种排法？•解：•先排5个不是小品的节目，有种排法；•它们之间以及最后一个节目之后一共有5个空隙，将3个小品插入进去，有种排法，•所以一共有种排法。•注：捆绑法与插入法一般适用于有如上述限制条件的排列问题。P55P5372003555PP山东省实验中学宁华老师信息竞赛课件五、排除法•例：求以一个长方体的顶点为顶点的四面体的个数。•解：•从8个点中取4个点，共有种，•其中取出的4个点共面的有种，•所以符合条件的四面体的个数为48C6612C841258山东省实验中学宁华老师信息竞赛课件例•100件产品中有3件是次品，其余都是正品。现在从中取出5件产品，其中含有次品，有多少种取法？山东省实验中学宁华老师信息竞赛课件•解法1——分类，加法原理：•含有1件次品：•含有2件次品：•含有3件次品：•所以符合题意的取法种数为：49713*CC山东省实验中学宁华老师信息竞赛课件39723*CC29733*CC297333972349713***CCCCCC•解法2——排除法：•从100件产品中取5件产品，有种取法，•从不含次品的97件中取出5件产品有种取法，•所以符合题意的取法有种。C1005597C5975100CC山东省实验中学宁华老师信息竞赛课件例•8个人站成一排，其中A与B、A与C都不能站在一起，一共有多少种排法？•解：•无限制条件有种排法。•A与B或A与C在一起各有种排法，•A、B、C三人站在一起且A在中间有种排法，•所以一共有种排法。P88PP2277PP22662160026622772288PPPPP山东省实验中学宁华老师信息竞赛课件六、机会均等法•例：10个人排成一队，其中甲一定要在乙的左边，丙一定要在乙的右边，不一定相邻，一共有多少种排法？•解：•甲、乙、丙三人排列一共有种排法，•在这6种排法中各种排列顺序在10个人的所有排列中出现的机会是均等的，而6种排列中满足条件的只有1种，•因此符合题设条件的排法种数为166048001010P6山东省实验中学宁华老师信息竞赛课件•用1，4，5，x四个数字组成四位数，所有这些四位数中的数字的总和为288，求x。•解：•若x不为0，一共可以得到个四位数。因为1，4，5，x出现的机会是均等的，即在每一个四位数里都出现一次，所以有：解得x=2。•若x为0，一共可以得到个四位数。而此时18*(1+4+5)≠288所以x不可能为0。288)541(24x2444P18例山东省实验中学宁华老师信息竞赛课件七、转化法•例：从1、2、3、……、20这二十个数中任取三个不同的数组成等差数列，这样的不同等差数列有________个。•分析：首先要把复杂的生活背景或其它数学背景转化为一个明确的排列组合问题。•设a,b,c成等差，∴2b=a+c,可知b由a,c决定；•又∵2b是偶数，∴a,c同奇或同偶，即：从1，3，5，……，19或2，4，6，8，……，20这十个数中选出两个数进行排列，由此就可确定等差数列，因而本题答案为•注意：本题是排列问题不是组合问题。1802210P山东省实验中学宁华老师信息竞赛课件•一个楼梯共10级台阶，每步走1级或2级，要求8步恰好走完，一共有多少种走法？•解：•设走1级的步数为x，走2级的步数为y，则有x+2y=10且x+y=8，解得x=6，y=2，即必须有6步是每步走1级，有2步每步走2级。•记每步走1级台阶为A，每步走2级台阶为B，•则原问题就相当于在8个格子中选2个填写B。其余的填写A，这是一个组合问题，所以一共有种走法。C8228例山东省实验中学宁华老师信息竞赛课件例•分析：对实际背景的分析可以逐层深入（一）从M到N必须走八步，其中向上走三步，向右走五步。（二）每一步是向上还是向右，决定了不同的走法。（三）事实上，当把向上的步骤决定后，剩下的步骤只能向右。•从而，任务可叙述为：从八个步骤中选出三步是向上走的走法数，∴本题答案为MN某城市有4条东西街道和6条南北的街道，街道之间的间距相同，如图。若规定只能向东或向北两个方向沿街道前进，则从M到N有多少种不同的走法?5638C山东省实验中学宁华老师信息竞赛课件八、隔板法•例：20个相同的球分给3个人，允许有人不取，但必须分完，有多少种分法？•解：•将20个球排成一排，一共有21个空隙，将两个隔板插入这些空隙中（两个隔板可以插在同一空隙中），规定由隔板分成的左、中、右三部分球分别分给3个人，则每一种隔法对应了一种分法，于是分法的总数为：•注：本题可转化成求方程x+y+z=20的非负整数解的个数。231121221C