1.2.2.3-排列与组合习题课

•1．巩固排列、组合的概念，排列数公式，组合数公式以及组合数性质．•2．在解排列、组合综合题时，要注意准确地应用两个基本原理，同时要区分是排列问题还是组合问题．•3．在解排列、组合应用题时，注意利用直接法解题的同时，也要根据问题的实际恰当地利用间接法解题．•本节重点：排列组合的综合应用．•本节难点：分堆与分配问题的区别．•1．解决排列组合的综合应用题时注意以下三点：•(1)仔细审题，判断是排列问题还是组合问题，或者是二者的混合，要按元素的性质分类，按事件发生的过程分步；(2)深入分析，严密周详．注意分清是乘还是加，既不少也不多；(3)对于有限制条件的比较复杂的排列、组合问题，要周密分析，设计出合理的方案，把复杂问题分解成若干简单的基本问题后应用分类加法计数原理或分步乘法计数原理来解决．2．注意分组问题的求法，一般地，设有m·n个元素，平均分成n组，每组m个，则(1)平均分成n组，有Cmmn·Cm(m－1)n·Cm(m－2)n·…·CmmAmm种；(2)平均分成n组，再分配到n个位置，有Cmmn·Cm(m－1)n·Cm(m－2)n·…·Cmm种．•[例1]某校为庆祝2011年国庆节，安排了一场文艺演出，其中有3个舞蹈节目和4个小品节目，按下面要求安排节目单，有多少种方法：•(1)3个舞蹈节目互不相邻；•(2)3个舞蹈节目和4个小品节目彼此相间．•[分析]由题目可获取以下主要信息：•①题目中涉及3个舞蹈、4个小品共7个节目；•②是同类节目互不相邻的问题．•解答本题的第(1)问可以先安排4个小品，然后让3个舞蹈“插空”；第(2)问彼此相间时安排方式只能是小品占1,3,5,7，舞蹈占2,4,6.故分两步，先安排小品，再安排舞蹈，或先安排舞蹈再安排小品．(2)由于舞蹈节目与小品节目彼此相间，故小品只能排在1,3,5,7位，舞蹈排在2,4,6位，安排时可分步进行．方法一：先安排4个小品节目在1,3,5,7位，共A44种排法；再安排舞蹈节目在2,4,6位，有A33种排法，故共有A44·A33＝144(种)排法．方法二：先安排3个舞蹈节目在2,4,6位，有A33种排法；再安排4个小品节目在1,3,5,7位，共A44种排法，故共有A33·A44＝144(种)排法．•[点评]元素相邻和不相邻问题的解题策略限制条件解题策略元素相邻通常采用“捆绑”法，即把相邻元素看做一个整体参与其他元素排列元素不相邻通常采用“插空”法，即先考虑不受限制的元素的排列，再将不相邻元素插在前面元素排列的空当中•A、B、C、D、E五人站成一排，如果A、B必须相邻，且B在A的右边，那么不同排法的种数有()•A．60B．48C．36D．24•[答案]D•[解析]将A与B看作一个元素，与其它3人排队共有A＝24种排法，A在B的左边只有一种情形．∴选D.[点评]①此题中去掉“A与B必须相邻”的条件时，∵A在B左边与A在B右边的情形一样多，故有12A55＝60种．②若将“A与B相邻”改为A与B不相邻，则有排法12A24·A33＝36种.•[例2]有6本不同的书按下列分配方式分配，问共有多少种不同的分配方式？•(1)分成1本、2本、3本三组；•(2)分给甲、乙、丙三人，其中一个人1本，一个人2本，一个人3本；•(3)分成每组都是2本的三组；•(4)分给甲、乙、丙三人，每个人2本；•(5)6本相同的书放到4个不同的盒子中，每个盒子至少放一本书．•[分析]由题目可获取以下主要信息：•①第(1)(3)题是分组问题，第(2)(4)题是将6本书分配给甲、乙、丙三个人；②第(2)题未说明甲、乙、丙三人谁得1本，谁得2本，谁得3本．解答本题，可先理清事件是否与顺序有关，再依题意求解．[解析](1)分三步：先选一本有C16种选法，再从余下的5本中选两本有C25种选法；最后余下的三本全选有C33种选法．由分步乘法计数原理知，分配方式共有C16·C25·C33＝60(种)．(2)由于甲、乙、丙是不同的三个人，在(1)题的基础上，还应考虑再分配问题，因此，分配方式共有C16·C25·C33·A33＝360(种)．(3)先分三步，则应是C26·C24·C22种方法，但是这里面出现了重复，不妨记六本书为A，B，C，D，E，F，若第一步取了AB，第二步取了CD，第三步取了EF，记该种分法为(AB，CD，EF)，则C26·C24·C22种分法中还有(AB，EF，CD)、(CD、AB、EF)、(CD、EF，AB)、(EF，CD，AB)、(EF，AB，CD)共A33种情况，而且这A33种情况仅是AB，CD，EF的顺序不同，因此，只能作为一种分法，故分配方式有C26·C24·C22A33＝15(种)．(4)在问题(3)的基础上再分配即可，共有分配方式C26·C24·C22A33·A33＝C26·C24·C22＝90(种)．(5)先把6本书并成一排，它们之间有5个空，在5个空中选出3个空放上“隔板”.6本书被分成了4组，4组书的本数也恰好对应一种放书的方法共有C35＝10(种)．•[点评](1)不同元素分组问题的常见形状，有①非均匀不编号分组如例2(1)；②非均匀编号分组如例2(2)；③均匀不编号分组如例2(3)；④均匀编号分组．其中②④为编号分组要考虑各组间的顺序，并且做题时要遵循先分组后排列的原则．•(2)相同元素分组问题可用“隔板法”，但要求每组至少含有一个元素．•在例2的条件下，求下列情况下有多少种不同的分配方式？•(1)2堆各1本，另外一堆4本；•(2)2人各1本，另外一人4本；•(3)分给甲、乙、丙三人，每人至少1本．[解析](1)可一堆一堆地分别取出，即得到C16C15C44.但在分堆过程中，对于各一本的两堆是无区别的，每A22种分法相当于一种分法，所以分堆数为C16C15C44A22＝15(种)．(2)两人各1本，另外一人4本，也即在(1)题的基础上再分配给三人，又有A33种分配方案，所以分配种数为C16C15C44A22·A33＝90(种)．(3)每人至少1本，可以分为三类情况：①“2、2、2型”即例2(4)中的分配情况，有C26C24C22＝90(种)方法；②“1、2、3”即例2(2)中的分配情况，有C16C25C33A33＝360(种)方法．③“1、1、4型”，有C46A33＝90(种)方法．∴一共有90＋360＋90＝540(种)方法．•[例3]10双互不相同的鞋子混装在一只口袋中，从中任意取出4只，试求出现以下结果时各有多少种情况？•(1)4只鞋子恰成两双；•(2)4只鞋子没有成双的．•[分析]由题目可获取以下主要信息：•①(1)说明恰好选了两双；•②(2)说明4只鞋来自4双不同的鞋．解答本题可先确定需几双才能满足题意，再从“双”中取“只”．[解析](1)根据题意只需选出两双鞋，所以有C210＝45(种)情况．(2)方法一：4只鞋若没有成双的，则它们来自于4双鞋；先从10双中取4双，有C410种取法，再从每双中取一只，各有C12种取法，所以由分步乘法计数原理共有C410·C12C12C12C12＝3360(种)情况．方法二：分以下五类：(1)4只左鞋，有C410＝210(种)情况；(2)4只右鞋，有C410＝210(种)情况；(3)3只左鞋，1只右鞋，有C310C17＝840(种)情况；(4)2只左鞋，2只右鞋，有C210C28＝1260(种)情况；(5)1只左鞋，3只右鞋，与(3)同也有840种情况．由分类加法计数原理共有210＋210＋840＋1260＋840＝3360(种)情况．•[分析]此类问题关键在于审清题意，弄明白怎样才算完成了“这件事”，从而设计出缜密的解题步骤．•在例3条件下求出现以下结果时各有多少种情况？•(1)取4只鞋有2只成双，另2只不成双；•(2)取6只鞋，其中3只左鞋，3只右鞋，且只有2只成双．[解析](1)4只鞋有2只成双，另2只不成双，则它们来自于3双鞋．先从10双鞋中取3双，有C310种取法，再确定哪双鞋成双，有C13种方法，最后另外两双鞋中各取一只，各有C12种取法，所以由分步乘法计数原理共有C310C13C12C12＝1440(种)情况．(2)先从10双鞋中取出1双有C110种取法；再从剩余的9双鞋中的9只左鞋中选2只有C29种取法，最后从未取到的7双鞋中的7只右鞋中选2只有C27种取法．所以由分步乘法计数原理共有C110C29C27＝7560(种)情况．•[例4]一只电子蚂蚁在如图所示的网格线上由原点O(0,0)出发，沿向上或向右方向爬至点(m，n)，(m，n∈N*)，记可能的爬行方法总数为f(m，n)，则f(m，n)＝________.[解析]从原点O出发，只能向上或向右方向爬行，记向上为1，向右为0，则爬到点(m，n)需m个0和n个1.这样爬行方法总数f(m，n)是m个0和n个1的不同排列方法数．m个0和n个1共占m＋n个位置，只要从中选取m个放0即可．∴f(m，n)＝Cmm＋n.•[点评]①例如f(3,4)＝C其中0010111表示从原点出发后，沿右右上右上上上的路径爬行．•②抽象建模后就是一个含相同数字的纯粹排列组合问题．•方程x＋y＋z＝12的非负整数解的个数为________．•[答案]91•[解析]把x，y，z分别看作是x个1、y个1和z个1，则共有12个1，问题抽象为12个1和两个十号的一个排列问题．由于x、y、z非负，故允许十号相邻，如1111＋＋11111111表示x＝4，y＝0，z＝8，[phone]＋表示x＝0，y＝12，z＝0等等，•∴不同排法总数为从14个位置中选取2个放十号，•∴方程的非负整数解共有C＝91个．∴填91个．•[例5]有五张卡片，它们的正、反面分别写着0与1,2与3,4与5,6与7,8与9.将其中任意三张并排放在一起组成三位数，共可组成多少个不同的三位数？•[分析]由题意可知①0不能作百位，但0与1在同一卡片上；②每张卡片都有正、反两种可能，解答本题可根据0和1两个特殊值分类，也可利用排除法．[解析]方法一：从0与1两个特殊值考虑，可分为三类：第一类：取0不取1，可先从另四张卡片中选一张作百位，有C14种方法；0可放在后两位，有C12种方法；最后需从剩下的三张中任取一张，有C13种方法；又除含0的那张外，其他两张都有正面或反面两种可能，故此时可得不同的三位数有C14C12C1322(个)；第二类：取1不取0，同上分析可得不同的三位数有C2422A33(个)；第三类：0和1都不取，有不同的三位数C3423A33(个)．综上所述，不同的三位数共有C14C12C1322＋C2422A33＋C3423A33＝432(个)．方法二：任取三张卡片可以组成不同的三位数C3523A33(个)，其中0在百位的有C2422A22(个)，这是不合题意的，故不同的三位数共有C3523A33－C2422A22＝432(个)．•[点评]解排列、组合的综合问题要注意以下几点：(1)认真审题，分清是排列还是组合问题；(2)有多个限制条件的复杂问题，要认真分析确定是分类还是分步．一、选择题1．下列等式中不正确的是()A．n！＝(n＋1)！n＋1B．Amn＝nAm－1n－1C．Amn＝n！(n－m)！D．Am－1n－1＝(n－1)！(m－n)！[答案]D2．已知x、y∈N＋，则Cxn＝Cyn，则x、y的关系是()A．x＝yB．y＝n－xC．x＝y或x＋y＝nD．x≥y•[答案]C[解析]当x＝y时显然成立，因为Cxn＝Cn－xn，故有n－x＝y，故x＋y＝n，故选C.[解析]人数分配上有1,1,3与1,2,2两种方式，若是1,1,3，则有C35C12C11A22×A33＝60(种)，若是1,2,2，则有C15C24C22A22×A33＝90(种)，所以共有150种，选A.•3．5名志愿者分到3所学校支教，每个学校至少去一名志愿者，则不同的分派方法共有•()•A．150种B．180种C．200种D．280种•[答案]A二、填空题4．若A7n－A5nA5n＝89，则n＝________.•[答案]15[解析]原式＝(n－5)(