《简单计数问题》-ppt课件.ppt

1.4 简单计数问题简单计数问题 课件课件 2 组合应用题的解法组合应用题的解法(1)(1)无限制条件的组合应用问题的解法步骤为：无限制条件的组合应用问题的解法步骤为：组合应用问题组合应用问题(2)(2)有限制条件的组合应用问题的解法有限制条件的组合应用问题的解法常用解法有：直接法，间接法可将条件视为特殊元素或常用解法有：直接法，间接法可将条件视为特殊元素或特殊位置，一般地按从不同的位置选取元素的顺序分步，特殊位置，一般地按从不同的位置选取元素的顺序分步，或按从同一位置选取的元素个数的多少分类或按从同一位置选取的元素个数的多少分类 分类时关键是确定分类标准，并且自始至终分类时关键是确定分类标准，并且自始至终应按同一标准进行，谨防应按同一标准进行，谨防“重复重复”和和“遗漏遗漏”【例例1 1】有有1212名划船运动员，其中人只会划左舷，人只名划船运动员，其中人只会划左舷，人只会划右舷，其余人左右舷都会划，现要从这会划右舷，其余人左右舷都会划，现要从这1212名运动员名运动员中选出人平均分配在左、右舷划船参加比赛，共有多少中选出人平均分配在左、右舷划船参加比赛，共有多少种不同的选法？种不同的选法？【审题指导审题指导】选出的人应有人会划左舷，另人会划选出的人应有人会划左舷，另人会划右舷，可按只会划左舷的人参加人数的多少分类考虑，右舷，可按只会划左舷的人参加人数的多少分类考虑，但应注意左右舷都会划的人的安排但应注意左右舷都会划的人的安排【规范解答规范解答】设集合设集合A A 只会划左舷的只会划左舷的3 3人人，B B 只会划右只会划右舷的舷的4 4人人，C C 既会划左舷又会划右舷的既会划左舷又会划右舷的5 5人人 先分类，以集合先分类，以集合A A为基准，划左舷的为基准，划左舷的3 3个人中，有以下几类情个人中，有以下几类情况：况：A A中有中有3 3人；人；A A中有中有2 2人；人；C C中有中有1 1人；人；A A中有中有1 1人，人，C C中有中有2 2人；人；C C中有中有3 3人人.第第类，划左舷的人已选定，划右舷的人可以在类，划左舷的人已选定，划右舷的人可以在BCBC中选中选3 3人，即有人，即有 种选法种选法.因是分步问题，所以有因是分步问题，所以有第第类，划左舷的人在类，划左舷的人在A A中选中选2 2人，有人，有 种选法，在种选法，在C C中选中选1 1人，有人，有 种选法，划右舷的在种选法，划右舷的在BCBC中剩下的中剩下的8 8个人中选个人中选3 3人，有人，有 种选法种选法.因是分步问题，所以有因是分步问题，所以有 种选法种选法.类似地，第类似地，第类，有类，有第第类有类有因为是分类，所以一共有因为是分类，所以一共有84+840+1 050+20084+840+1 050+2002 174(2 174(种种)选法选法 分组与分配问题分组与分配问题1.1.分组问题常见形式及处理方法分组问题常见形式及处理方法(1)(1)非均匀不编号分组非均匀不编号分组(不平均分组不平均分组)n n个不同元素分成个不同元素分成m m组，第组，第k k组的元素个数用组的元素个数用m mk k(1k(1kn)n)表示表示.每组元素数目均不相同，且不考虑各组间的顺序，不管是每组元素数目均不相同，且不考虑各组间的顺序，不管是否分尽，分法种数为：否分尽，分法种数为：(2)(2)均匀不编号分组均匀不编号分组(部分平均分组部分平均分组)将将n n个不同元素分成不编号的个不同元素分成不编号的m m组，假定其中组，假定其中r r组元素个数相组元素个数相等，不管是否分尽，其分法种数为等，不管是否分尽，其分法种数为 (其中其中A A为非均匀不编为非均匀不编号分组中分法数，即号分组中分法数，即(1)(1)中的中的A)A)，如果再有，如果再有k k组均匀分组应组均匀分组应再除以再除以(3)(3)非均匀编号分组非均匀编号分组n n个不同元素分成个不同元素分成m m组，各组元素数目均不相等，且考虑各组，各组元素数目均不相等，且考虑各组间的顺序，其分法种数为组间的顺序，其分法种数为A(AA(A为非均匀不编号分组中的分为非均匀不编号分组中的分法数，即法数，即(1)(1)中的中的A).A).(4)(4)均匀编号分组均匀编号分组n n个不同元素分成个不同元素分成m m组，其中组，其中r r组元素个数相同且考虑各组间组元素个数相同且考虑各组间的顺序，其分法种数为的顺序，其分法种数为 (A(A为非均匀不编号分组中的为非均匀不编号分组中的分法数，即分法数，即(1)(1)中的中的A).A).2.2.分配问题分配问题将将n n个元素按一定要求分给个元素按一定要求分给m m个人，称为分配问题个人，称为分配问题.分组问题分组问题和分配问题是有区别的，前者组与组之间只要元素个数相和分配问题是有区别的，前者组与组之间只要元素个数相同是不可区分的，而后者则即使两人元素个数相同，但因同是不可区分的，而后者则即使两人元素个数相同，但因人不同，仍然是可区分的，对于这类问题必须遵循先分组人不同，仍然是可区分的，对于这类问题必须遵循先分组后排列的原则后排列的原则.分配问题是指把元素分给指定的目标，其实分配问题是指把元素分给指定的目标，其实质是先分组，再排序质是先分组，再排序【例例2 2】有有6 6本不同的书本不同的书(1)(1)分成三份：分成三份：每份本，有多少种不同的分法？每份本，有多少种不同的分法？份本，另份各本，有多少种不同的分法？份本，另份各本，有多少种不同的分法？份本，份本，份本，有多少种不同的分法份本，份本，份本，有多少种不同的分法？(2)(2)分给甲、乙、丙人：分给甲、乙、丙人：甲得本，乙得本，丙得本，有多少种不同的分法甲得本，乙得本，丙得本，有多少种不同的分法？人本，人本，人本，有多少种不同的分法人本，人本，人本，有多少种不同的分法？每人本，有多少种不同的分法？每人本，有多少种不同的分法？人本，另人各本，有多少种不同的分法？人本，另人各本，有多少种不同的分法？【审题指导审题指导】对于对于(1)(1)，只要求分成三部分，不排列，与顺，只要求分成三部分，不排列，与顺序无关；对于序无关；对于(2)(2)，是分配问题，谁分得哪部分有区别，与，是分配问题，谁分得哪部分有区别，与顺序有关解答顺序有关解答(1)(1)可考虑有多少种组合即可，解答可考虑有多少种组合即可，解答(2)(2)可可先分组，再分配先分组，再分配【规范解答规范解答】(1)(1)先在本书中任取本作为一份，有先在本书中任取本作为一份，有种不同的取法，再从余下的本书中任取本作为一份，有种不同的取法，再从余下的本书中任取本作为一份，有 种不同的取法，最后把余下的种不同的取法，最后把余下的2 2本书都取出作为一份，有本书都取出作为一份，有 种不同的取法，所以共有种不同的取法，所以共有 种取法，但是这样每种取法，但是这样每种取法对应的是一个排列，总体来讲相当于对三个元素进行种取法对应的是一个排列，总体来讲相当于对三个元素进行了全排列，如了全排列，如“先取先取abab，再取，再取cdcd，最后取，最后取efef”与与“先取先取cdcd，再取再取abab，最后取，最后取efef”，对应的分法是同一种组合，这里共进，对应的分法是同一种组合，这里共进行了行了 次，故分成三份，每份次，故分成三份，每份2 2本，共有本，共有共有共有 种分法种分法.共有共有 种分法种分法.(2)(2)先从先从6 6本书中任取本书中任取1 1本分给甲，有本分给甲，有 种给法，再从余种给法，再从余下的下的5 5本书中任取本书中任取2 2本，分给乙，有本，分给乙，有 种给法，最后把余下种给法，最后把余下的的3 3本书给丙，有本书给丙，有 种给法，故共有种给法，故共有 种不同的种不同的分配方法分配方法.甲、乙、丙甲、乙、丙3 3人谁得人谁得1 1本，谁得本，谁得2 2本，谁得本，谁得3 3本，不确定，本，不确定，可考虑先分组，后分配，故共有：可考虑先分组，后分配，故共有：种分法种分法.同理，有同理，有 种分法种分法.共有共有 种分法种分法.【例例】1212个篮球队中有个篮球队中有3 3个强队，将这个强队，将这1212个队任意分成个队任意分成3 3个个组组(每组每组4 4个队个队)，则，则3 3个强队恰好被分在同一组的分法有个强队恰好被分在同一组的分法有_种种【审题指导审题指导】本题属于分组问题，个强队分在同一组，本题属于分组问题，个强队分在同一组，即个强队与其余个队中的任意一个队进行组合，于是即个强队与其余个队中的任意一个队进行组合，于是分步考虑即可分步考虑即可【规范解答规范解答】先安排强队分法，再考虑其他，先安排强队分法，再考虑其他，3 3个强队恰好个强队恰好被分在同一组分法有被分在同一组分法有 种种答案：答案：315315 排列组合的综合应用排列组合的综合应用 解决排列组合应用题的步骤和方法解决排列组合应用题的步骤和方法(1)(1)一般步骤一般步骤把具体问题化归为排列或组合问题；把具体问题化归为排列或组合问题；通过分析确定运用两个计数原理；通过分析确定运用两个计数原理；分析题目条件，避免重复或遗漏；分析题目条件，避免重复或遗漏；列出式子，准确计算列出式子，准确计算.(2)(2)常用方法常用方法相邻元素归并法相邻元素归并法(又称捆绑法又称捆绑法)；相离元素插空法；相离元素插空法；定位元素优先安排法；定位元素优先安排法；有序分配依次分组法有序分配依次分组法;多元素不相容情况分类法；多元素不相容情况分类法；交叉问题集合法；交叉问题集合法；混合问题先组合后排序法；混合问题先组合后排序法；“至少至少”、“至多至多”问题间接排除法问题间接排除法.【例例3 3】已知已知1010件不同产品中有件不同产品中有4 4件是次品，现对它们进行件是次品，现对它们进行一一测试，直到找出所有次品为止一一测试，直到找出所有次品为止.(1)(1)若恰在第若恰在第5 5次才测试到第一件次品，第十次才找出最后次才测试到第一件次品，第十次才找出最后一件次品，则不同的测试方法有多少种？一件次品，则不同的测试方法有多少种？(2)(2)若恰在第若恰在第5 5次测试后，就找到了所有次测试后，就找到了所有4 4件次品，则这样的件次品，则这样的不同测试方法有多少种？不同测试方法有多少种？【审题指导审题指导】1010件产品中有件次品，若恰在第次测试件产品中有件次品，若恰在第次测试到件次品，第十次才找出最后件次品，说明前次测到件次品，第十次才找出最后件次品，说明前次测出的均为正品，第次测到的是件次品，第至第出的均为正品，第次测到的是件次品，第至第9 9次测次测出件次品；若在第次测试后就找到了件次品，说明出件次品；若在第次测试后就找到了件次品，说明前次测出件次品，第次测到的是最后件次品本前次测出件次品，第次测到的是最后件次品本题属于排列组合的综合应用问题，解答时注意将问题合理题属于排列组合的综合应用问题，解答时注意将问题合理转化，直接分步解决即可转化，直接分步解决即可【规范解答规范解答】(1)(1)先排前次测试，只能取正品，有先排前次测试，只能取正品，有 种种不同测试方法，再从不同测试方法，再从4 4件次品中选在第件次品中选在第5 5和第和第1010的位置上进的位置上进行测试，有行测试，有 (种种)测法，再排余下测法，再排余下4 4件的测试位置，件的测试位置，有有 种测试方法种测试方法.所以共有不同排法所以共有不同排法 =103 680=103 680(种种).).(2)(2)第第5 5次测试恰为最后一件次品，另次测试恰为最后一件次品，另3 3件在前件在前4 4次中出现，次中出现，从而前从而前4 4次有一件正品出现，所以共有不同次有一件正品出现，所以共有不同测试方法测试方法【典例典例】(12(12分分)将个编号为将个编号为1 1，2 2，3 3，4 4的四个小球放入的四个小球放入个编号为个编号为1 1，2 2，3 3，4 4的盒子中，则恰好有一个空盒的投的盒子中，则恰好有一个空盒的投放方法有多少种？放方法有多少种？【审题指导审题指导】恰好有一个空盒，即其中个盒子放球，且恰好有一个空盒，即其中个盒子放球，且一个盒子投放球，另两个盒子各放一球解答本题可先一个盒子投放球，另两个盒子各放一球解答本题可先分组后分配，也可逐一分配分组后分配，也可逐一分配【规范解答规范解答】方法一：先将个小球按方法一：先将个小球按,分为三组，分为三组，有有 种分法，种分法，分分再将三组小球投入个盒子中，有再将三组小球投入个盒子中，有 种不同的投放方种不同的投放方法，法，1010分分故共有故共有 种投放方法种投放方法1212分分方法二：先取个球中的个方法二：先取个球中的个“捆绑捆绑”在一起，有在一起，有 种选种选法，法，3 3分分把它与其余个小球，共个元素分别放入个盒子的把它与其余个小球，共个元素分别放入个盒子的个中，有个中，有 种放法，种放法，6 6分分故共有故共有 种投放方法种投放方法1212分分【误区警示误区警示】对解答本题时易犯的错误具体分析如下：对解答本题时易犯的错误具体分析如下：1.1.从从4 4名男生、名男生、3 3名女生中各选出名女生中各选出2 2名组成研究性学习小组，名组成研究性学习小组，并从选出的并从选出的4 4人中再选定人中再选定1 1人当组长，则不同选法的种数是人当组长，则不同选法的种数是()()(A)(A)(B)(B)(C)(D)(C)(D)【解析解析】选选C.C.分三步：先从分三步：先从4 4名男生中任选名男生中任选2 2名，有名，有 种不种不同选法，再从同选法，再从3 3名女生中任选名女生中任选2 2名，有名，有 种不同选法，最后种不同选法，最后从选出的从选出的4 4人中任选人中任选1 1人当组长，有人当组长，有 种不同选法，种不同选法，所以共有所以共有 种不同选法种不同选法,故选故选C.C.2.2.用用1 1、2 2、3 3这三个数字组成四位数，规定这三个数字必须这三个数字组成四位数，规定这三个数字必须使用，但相同的数字不能相邻，以这样的方式组成的四位使用，但相同的数字不能相邻，以这样的方式组成的四位数有数有()()(A)9(A)9个个 (B)18(B)18个个(C)12(C)12个个 (D)36(D)36个个【解析解析】选选B.B.相同的数字可以是相同的数字可以是1 1，2 2，3 3三种情况，当相同三种情况，当相同数字中间隔一个数字时，数字中间隔一个数字时，种情况；相同数字中间隔种情况；相同数字中间隔两个数字时，有两个数字时，有 种情况，由分类计数原理，四位数的总种情况，由分类计数原理，四位数的总数为：数为：3.3.从从5 5位男教师和位男教师和4 4位女教师中选出位女教师中选出3 3位教师派到位教师派到3 3个班担任个班担任班主任班主任(每班一位班主任每班一位班主任)，要求这，要求这3 3位班主任中男女教师都位班主任中男女教师都要有，则不同的选派方案共有要有，则不同的选派方案共有()()(A)210(A)210种种 (B)420(B)420种种(C)630(C)630种种 (D)840(D)840种种【解析解析】选选B B方法一方法一(直接法直接法)：选出的位教师可以是：选出的位教师可以是“男女男女”、“男女男女”，所以不同的选派方法共有，所以不同的选派方法共有方法二方法二(间接法间接法)：从男女共位教师中选出名教师：从男女共位教师中选出名教师的不同选法有的不同选法有 种，其中都是男教师的选法有种，其中都是男教师的选法有 种，都种，都是女教师的选法有是女教师的选法有 种，所以符合题意的选派方法共种，所以符合题意的选派方法共4.4.将将4 4名大学生分配到名大学生分配到3 3个乡镇去当村官，每个乡镇至少一个乡镇去当村官，每个乡镇至少一名，则不同的分配方案有名，则不同的分配方案有_种种(用数字作答用数字作答)【解析解析】分两步完成：第一步将分两步完成：第一步将4 4名大学生按名大学生按2 2，1 1，1 1分成分成三组，其分法有三组，其分法有 第二步将分好的三组分配到第二步将分好的三组分配到3 3个个乡镇，其分法有乡镇，其分法有 所以满足条件的分配方案有所以满足条件的分配方案有=36=36种种.答案答案:36365.5.要排出某班一天中语文、数学、政治、英语、体育、艺要排出某班一天中语文、数学、政治、英语、体育、艺术术6 6门课各一节的课程表，要求数学课排在前门课各一节的课程表，要求数学课排在前3 3节，英语课节，英语课不排在第不排在第6 6节，则不同的排法种数为节，则不同的排法种数为_(以数字作答以数字作答)【解析解析】先排数学课有先排数学课有 种排法，再排最后一节有种排法，再排最后一节有 种种排法，剩余的有排法，剩余的有 种排法，共有种排法，共有答案答案:2882886.6.某市工商局对某市工商局对3535种商品进行抽样检查，鉴定结果有种商品进行抽样检查，鉴定结果有1515种种假货，先从假货，先从3535种商品中选取种商品中选取3 3种种(1)(1)恰有种假货在内的不同取法有多少种？恰有种假货在内的不同取法有多少种？(2)(2)至少有种假货在内的不同取法有多少种？至少有种假货在内的不同取法有多少种？(3)(3)至多有种假货在内的不同取法有多少种？至多有种假货在内的不同取法有多少种？【解析解析】(1)(1)从从2020种真货中选取种真货中选取1 1件件,从从1515种假货中选取种假货中选取2 2件，有件，有恰有种假货在内的不同取法有恰有种假货在内的不同取法有2 1002 100种种(2)(2)选取选取2 2件假货有件假货有 种，选取件假货有种，选取件假货有 种，共有种，共有选取方法选取方法(3)(3)选取件的种数有选取件的种数有 因此有选取方式因此有选取方式 =6 0906 090种种所以至多有所以至多有2 2种假货在内的不同的取法有种假货在内的不同的取法有6 0906 090种种