2019届二轮复习逻辑、计数原理与组合数学案（全国通用）

2019届二轮复习逻辑、计数原理与组合数学案（全国通用）

第十五讲 逻辑、计数原理与组合数 一、知识方法拓展 1、 排列组合常用的解法有：运用两个基本原理（加法、乘法原理）；特殊元素（位置）优先考虑；捆绑法；插空法；隔板法；排除法；机会均等法；转化法。‎ 2、 证明组合恒等式的常用方法有：赋值法；母函数法；构造组合模型法。‎ 3、 几个基本组合恒等式：；；；；；（范德蒙公式）。‎ 4、 错位排列问题：设集合，所有元素的一种全排列，满足，则称这样的排列为错位全排列。用表示错位全排列的总数，则。‎ 5、 不尽相异的个元素的全排列：在个元素中，有个元素相同，又另有个元素相同，…，一直到另有个元素相同，且，这个元素的全排列叫做不尽相异的个元素的全排列。不难得到，此全排列数计算公式为：‎ 6、 从个元素里取个元素的环排列：从个不同元素中任取个元素按照圆圈排列，这种排列叫做从个元素里取个元素的环排列。如果元素之间的相对位置没有改变，它们就是同一种排列。把一个个元素的环在个不同的位置拆开，即得个不同的线排列。由于个不同元素中任取个元素的排列方法种，所以个不同元素中任取个元素的环排列方法有种。特别地，个不同元素的环排列方法有（种）。‎ 注：排列数，有些地方也记为。‎ 1、 一次不定方程的非负整数解的个数等于（或）；正整数解的个数等于（或）。‎ 二、热身练习 ‎1、（09复旦）设有个不同颜色的球，放入个不同的盒子中，要求每个盒子至少有一个球，则不同的放法有（ ）种。‎ ‎（A） （B） （C） （D）‎ ‎【详解】可采用特殊元素法，一个盒子中需要放两个球，即，剩下个球与个盒子全排列，即，选D。‎ ‎2、（复旦）三边均为整数，且最大边长为11的三角形，共有（ ）个。‎ ‎（A）20 （B）26 （C）30 （D）36‎ ‎【详解】设另外两边为，且，列举可得可取共66个，去掉重复的，即36个，选D。‎ ‎3、（复旦）在集合中任选两个数作为椭圆方程中的和，则能组成落在矩形区域内的椭圆个数是（ ）‎ ‎（A）70 （B）72 （C）80 （D）88‎ ‎【详解】由题意得，只需，即有8种选择，有9种选择，共计种可能，选B。‎ ‎4、（10同济）若多项式，则 。‎ ‎【详解】易知等式右边的系数为，则等式右边的系数为，即。‎ 三、真题精讲 例1（11卓越）数列共有11项，，且，。满足这种条件的不同数列的个数为（ ）。‎ ‎（A）100 （B）120 （C）140 （D）160‎ ‎【详解】由可知，后一项在前一项的基础上加1或减1，而，即从第1项到第11项这共10次运算中，最终结果是加4，即10次运算中7次加1，剩下3次为减1，故满足条件的不同数列的个数为，选B。‎ 例2（上海交大）在的展开式中，项的系数是多少？‎ ‎【解析】本题为三项式展开，与平时接触的二项式有所差距，故可以考虑通过转化为二项式再进行运算，或者利用二项式展开的原理分析三项式展开的法则。‎ ‎【详解】方法一：，其中只有和中含有的因式，即，，所以项的系数为。‎ 方法二：，其中且，则当，即或时成立，得的系数为。‎ 例3、（复旦）求证：。‎ ‎【解析】组合数与二项式定理息息相关，本题出现，可以从次方的二项式定理入手，也可以建立应用模型，将问题转化为模型，用实际情况解决。‎ ‎【详解】方法一：可视为中的系数，而左式中组合数的下标都为，可视为，即其中的系数为 ‎，故原命题得证。‎ 方法二：建立应用模型：一个袋子中有个小球，其中一半为红球，一半为白球，则从这个袋子中取出个球，可能出现的情况有几种？‎ 易知取出的红球与白球个数和为，而红球的可能情况有0，1，…，，白球则为，…，1，0，则取出的情况可以是，即，也可以直接写为从个小球中取出个，即，故得证。‎ 例4、（2012华约）甲、乙、丙、丁等七人排成一排，要求甲在中间，乙、丙相邻，且丁不在两端，则不同的排法共有多少种？‎ ‎【解析】本题为典型的特殊元素法求解排列组合问题，关键在于分类按同一变量，详尽、不重复即可。即可以按乙、丙位置讨论，也可以按丁的位置讨论。‎ ‎【详解】将从左到右的位置记为1~7号位置，则甲必须在4号位，排好乙、丙、丁三人后还余下三人全排列即可。‎ 解法一：若乙丙捆绑（种方法），当乙丙在1、2号位时，丁有3、5、6三种选择；当乙丙在2、3号位时，丁有5、6两种选择；当乙丙在5、6号位时，丁有2、3两种选择；当乙丙在6、7号位时，丁有2、3、5三种选择；故共有种。‎ 解法二：当丁在2号位时，乙丙有5、6或6、7两种选择；当丁在3号位时，乙丙有1、2或5、6或6、7三种选择；当丁在5号位时，乙丙也有三种选择；当丁在6号位时，乙丙有两种选择；故共有种选择。‎ 例 5、排球单循环赛，南方球队比北方球队多9支，南方球队总得分是北方球队的9倍。求证：冠军是一支南方球队（胜得1分，败得0分）。‎ ‎【解析】本题为排列组合相关的应用题，关键在于建立合适的数学模型。其中球队数量未知，为表达其关系，可设北方球队支，则南方球队支。为证明冠军是一支南方球队，转化为代数关系，即北方球队的最高分低于南方球队最高分的最小可能值，由此便可入手。‎ ‎【详解】设北方球队支，则南方球队支，则共有场比赛，即共分；则南方球队总得分为分，北方球队总得分为分；‎ 南方球队内部间比赛得分为，北方球队内部间比赛得分为；‎ 由于南方、北方队伍的总得分分别大于或等于其内部总得分，即：‎ ‎，又有，得，代入验证各种得分是否为自然数，可得。‎ ‎1、当时，南方球队得分189，内部得分105；北方球队得分21，内部得分15。‎ 而北方任一支球队内部得分不会超过5分（每支球队内部只比5场比赛），而北方球队胜南方球队的得分为，即北方任一支球队的得分最高不超过分；而南方球队有15支，，即平均得分大于11分，故至少有一支球队得分大于11分，即冠军在南方球队中。‎ ‎2、同理，当时，冠军也在南方球队中。‎ 综上得证。‎ 例6、（2012华约）有个学生在一个班级，他们要参加乒乓球双打比赛，班里先举行了热身赛。这个学生，两两互为搭档，恰好都参加了一次热身赛。请你写出的所有可能的值并写出其中一个比赛安排方案。‎ ‎【解析】首先，个学生中，两两互为搭档共产生组搭档，而由于恰好只参加一次比赛，即共比了场比赛，为使比赛场数为整数，易得或，其中。下面要对于及的情况分别证明正确性，由于取值的离散性，可以考虑采用数学归纳法证明。‎ ‎【详解】的所有可能的值为或，其中。‎ ‎（1）用数学归纳法证明时，可给出满足题意的比赛方案：①当时，，将四位选手分别用表示，则如下安排比赛即可：AB与CD，AC与BD，AD与BC。‎ ②假设时结论成立，则时，假设这位选手为，而后位选手可以由假设安排出合题意的比赛，只剩下A、B、C、D之间比赛及A、B、C、D与之间的比赛。‎ A、B、C、D之间比赛可按照第一步进行，A、B、C、D与之间的比赛可以安排为与，与，与，与，……，这样就满足要求了，最后将这些比赛总计起来，就是满足要求的位选手之间的比赛了。‎ 由数学归纳法，结论证毕。‎ ‎（2）同理，用数学归纳法证明时，可给出满足题意的比赛方案。‎ 综上所述，的所有可能的取值是或。‎ 四、重点总结 本讲的考查重点有两个，1、组合数恒等式；2、排列组合应用题。而这两个知识点的主要难点在于对题目中的恒等式或实际问题建立起相关的排列组合模型，在模型中利用所学的数学知识解题。这部分的特点是并没有过多的“新知识”，而是重在于知识灵活运用的能力，需要锻炼强大的理解力。‎ 五、强化训练 A组 ‎1、（09华南理工）在的展开式，的系数为（ ）‎ ‎（A） （B） （C） （D）‎ ‎【详解】易知的系数为 ‎ 故选A。‎ ‎2、（复旦）在二项式的展开式中，若前3项的系数成等差数列，则展开式中有理项的项数为（ ）‎ ‎（A）2 （B）3 （C）4 （D）5‎ ‎【详解】易知或1（舍），则，若是有理项，只需是的倍数即可，故可取，共3项，故选B。‎ ‎3、（复旦）5个不同元素排成一列，规定不许排第一，不许排第二，不同的排法共有（ ）‎ ‎（A）64种 （B）72种 （C）78种 （D）84种 ‎【详解】当排第一时，有种方法；当不排第一时，，共种，故选C。‎ ‎4、（复旦）设是由三个不同元素所组成的集合，且是的子集族，满足性质：空集和属于，并且中任何两个元的交集和并集还属于。问所有可能的的个数为（ ）‎ ‎（A）29 （B）33 （C）43 （D）59‎ ‎【详解】可以T的元素个数来讨论，若T为二元集，则只有1个；若T为三元集，有共6个；若T为四元集，有等共9个；若T为五元集，有等共6个；若T为六元集，有等共6个；若T为七元集，有0个；若T为八元集，即包含所有子集，即1个，共计29个，故选A。‎ ‎5、（复旦）将一个四棱锥的每个顶点染上一种颜色，并使一条棱的两端点异色，若只有五种颜色可供使用，则不同的染色方法的总数为（ ）‎ ‎（A）120 （B）260 （C）340 （D）420‎ ‎【详解】共有5个顶点，若用五种颜色，则种；若用4种颜色，共有种；若用3种颜色，则必有一个侧面确定下来，剩下两点也能够确定，故共有种，故共有420种方法，选D。‎ ‎6、（复旦）求在十进制中最后4位 。‎ ‎【详解】，易得末尾4位为，即。‎ ‎7、10人围圆桌而坐，如果甲、乙两个中间相隔4个，有多少种坐法？‎ ‎【详解】甲固定座好，则乙有两种坐法，其他8人全排列，共有种坐法。‎ ‎8、（08交大）通信工程中常用元数组表示信息，其中或。设，表示和中相对应的元素不同的个数。‎ ‎（1），问存在多少个5元数组，使得；‎ ‎（2），问存在多少个5元数组，使得；‎ ‎（3）令，，求证：。‎ ‎【详解】（1）；（2）；（3）设中对应项同时为0的有个，同时为1的有个，则不同的项共有项，而，即，而，得证。‎ ‎9、（复旦）设，计算：‎ ‎（1）的不同取值个数；‎ ‎（2）的所有不同取值的积与和。‎ ‎【详解】（1）易知由组成，故有个不同取值；‎ ‎（2）易知中出现1个2和2个2的可能性是相同的，均为次，同理可得，出现1个、2个、3个3的可能性也相同，均为18次，出现1、2、3、4、5个5均为12次，所以的所有不同取值的积为；和为。‎ B组 ‎1、（2012北约）求证：对任意的正整数，必可表示成的形式，其中。‎ ‎【详解】‎ ‎，‎ ‎，‎ 则，‎ ‎，‎ 则，即当时，；‎ 当时，，则得证。‎ ‎2、（2012北约）在1，2，…，2012中取一组数，使得任意两数之和不能被其差整除，最多能取多少个数？‎ ‎【详解】此题是组合与数论的综合题，将1~2012分成三组数，分别被3除余0、1、2，‎ ‎，‎ ‎，‎ ‎，‎ 后面两组元素最多，如，任意两数之差都是3的倍数，而两数之和被3除的余数为2，显然不能被3整除，显然符合；若取672个数，则必有两个数之差小于3，若为1，则显然可整数两数之和，若为2，则两数同奇同 偶，2能够整除两数之和，综上，至多能选取671个数。‎ ‎3、（08交大）世界杯预选赛中，中国、澳大利亚、卡塔尔和伊拉克被分在A组，进行主客场比赛。规定每场比赛胜者得三分，平局各得一分，败者不得分。比赛结束后前两名可以晋级。‎ ‎（1）由于4支队伍均为强队，每支队伍至少得3分。于是 甲专家预测：中国队至少得10分才能确保出线；‎ 乙专家预测：中国队至少得11分才能确保出线。‎ 问：甲、乙专家哪个说的对？为什么？‎ ‎（2）若不考虑（1）中条件，中国队至少得多少分才能确保出线？13分 ‎【详解】（1）乙专家说的对，若中国队得10分，可能会出现其余三队12分、10分、3分的情况，因此中国队无法确保晋级；‎ 而中国队若得了11分而无法晋级，则必为第三名，而第一、二名不少于11分，而第四名不少于3分。12场比赛在无平局情况下只有36分，前三名11分、最后一名3分，而11分则意味着出现平局，则出现矛盾，故乙专家说的对。‎ ‎（2）若12分，可能出现如下情况：‎ 澳 澳 中 中 卡 卡 伊 伊 总分 澳 ‎3‎ ‎0‎ ‎3‎ ‎0‎ ‎3‎ ‎3‎ ‎12‎ 中 ‎0‎ ‎3‎ ‎0‎ ‎3‎ ‎3‎ ‎3‎ ‎12‎ 卡 ‎0‎ ‎3‎ ‎3‎ ‎0‎ ‎3‎ ‎3‎ ‎12‎ 伊 ‎0‎ ‎0‎ ‎0‎ ‎0‎ ‎0‎ ‎0‎ ‎0‎ 仍然无法晋级。而13分则必能出线，因为若13分为第三名，则前三名则已达39分，超过最大了36分，矛盾，即13分确保出线。‎ ‎4、（09北大）某次考试共有333名学生做对了1000道题，做对3道及以下为不及格，6道及以上为优秀，考场中每人做对题目数不全同奇偶。问：不及格者与优秀者哪个多？‎ ‎【详解】设不及格有人，优秀有人，其余有人，假设，‎ 若，则每个人都至少做对了4题，即至少做对了，矛盾；‎ 若，则至少做对了 ‎，矛盾；‎ 若，则由于333是奇数，得，至少共做对了，当且仅当所有不及格者都对了0道，所有优秀者都恰对了6道，其他人都恰对了4道（且），此时同时为偶，矛盾，故假设不成立，则，故不及格。‎ ‎5、（10清华特色）长为的木棒（为整数）可以锯成长为整数的两段，要求任何时刻所有木棒中的最小者严格小于最短者长度的2倍。例如长为4的木棒可以锯成两段，而长为7的木棒第一次可以锯成，第二次可以再将长为4的木棒锯成，这时三段不能再锯。问：长为30的木棒至多可以锯成多少段？‎ ‎【详解】最小长度最多2段，否则若有3段，则任两段之和都不小于两倍最小长度，矛盾。‎ 至多可为6段：3012、188、10、126、6、8、105、5、6、6、84、4、5、5、6、6。‎ 若可为7段，则最大的一段若超过6，则最短的至少为4，那么总长度不小于31了，矛盾。故最大的一段不超过6.显然，最大的一段不小于5.‎ （1） 最大一段为5，则最小一段不小于3，而总和为30的情况只有：‎ ‎3、3、4、5、5、5、5；3、4、4、4、5、5、5；4、4、4、4、4、5、5（与最小长度至多2段矛盾）‎ ‎1）第一种情况，，剩4、5、5、5、5、5、6，第二步只能，剩5、5、5、5、6、9，与最小长度至多2段矛盾；‎ ‎2）第二种情况，，剩4、4、5、5、5、7，第二步只能，剩5、5、5、7、8，与最小长度至多2段矛盾。‎ （2） 最大一段为6，则最小一段不小于4，情况有4、4、4、4、4、4、6，与最小长度至多2段矛盾。‎ 所以，无法锯成7段。‎ 而若要锯成超过7段，必经历7段，无法实现，故至多6段。‎