专题17构造法模型和递推模型例1．如图所示，将方格纸中每个小方格染三种颜色之一，使得每种颜色的小方格的个数相等.若相邻两个小方格的颜色不同，称他们的公共边为“分割边”，则分割边条数的最小值为A．33 B．56 C．64 D．78【答案】B【解析】记分隔边的条数为，首先将方格按照按图分三个区域，分别染成三种颜色，粗线上均为分隔边，将方格的行从上至下依次记为，列从左至右依次记为，行中方格出现的颜色数记为，列中方格出现的颜色个数记为，三种颜色分别记为，对于一种颜色，设为含有色方格的行数与列数之和，定义当行含有色方格时，，否则，类似的定义，计算得到，再证明，再证明对任意均有，最后求出分隔边条数的最小值.【详解】记分隔边的条数为，首先将方格按照按图分三个区域，分别染成三种颜色，粗线上均为分隔边，此时共有56条分隔边，即，其次证明：，将将方格的行从上至下依次记为，列从左至右依次记为，行中方格出现的颜色数记为，列中方格出现的颜色个数记为，三种颜色分别记为，对于一种颜色，设为含有色方格的行数与列数之和，定义当行含有色方格时，，否则，类似的定义，所以，由于染色的格有个，设含有色方格的行有个，列有个，则色的方格一定再这个行和列的交叉方格中，从而，所以①，由于在行中有种颜色的方格，于是至少有条分隔边，类似的，在列中有种颜色的方格，于是至少有条分隔边，则②③下面分两种情形讨论，(1)有一行或一列所有方格同色，不妨设有一行均为色，则方格的33列均含有的方格，又色的方格有363个,故至少有11行有色方格，于是④由①③④得，(2)没有一行也没有一列的所有方格同色,则对任意均有，从而，由式②知：，综上，分隔边条数的最小值为56.故选：B.【点睛】本题主要考查染色问题，考查计数原理，考查分析推理能力，是一道难度极大的题目.例2．从1，2，3，…，20中选取四元数组，满足，则这样的四元数组的个数是A． B． C． D．【答案】C【解析】通过假设，分析得到满足的的个数，从而确定出四元数组的个数.【详解】因为，记，因为，所以，记，因为，所以，记，因为，所以，记，因为，记，所以，所以四元数组的个数，即为满足条件的的个数，又因为且，所以的个数为：（看成个排成一列，会形成个空位，插入个隔板隔开，形成个数），则四元数组的个数为，故选：C.【点睛】本题考查排列组合的综合应用，其中涉及到数字排列的变换以及隔板法的运用，对学生的分析与转化能力要求较高，难度较难.例3．几只猴子在一棵枯树上玩耍，假设它们均不慎失足下落，已知：（1）甲在下落的过程中依次撞击到树枝A，B，C；（2）乙在下落的过程中依次撞击到树枝D，E，F；（3）丙在下落的过程中依次撞击到树枝G，A，C；（4）丁在下落的过程中依次撞击到树枝B，D，H；（5）戊在下落的过程中依次撞击到树枝I，C，E,则这九棵树枝从高到低不同的顺序共有（       ）A．23 B．24 C．32 D．33【答案】D【解析】【分析】先判断出，按顺序排在前四个位置中的三个位置，，，且一定排在后四个位置，然后分排在前四个位置中的一个位置与不排在前四个位置中的一个位置两种情况讨论，利用分类计数加法原理可得结果.【详解】不妨设代表树枝的高度，五根树枝从上至下共九个位置，根据甲依次撞击到树枝；乙依次撞击到树枝；丙依次撞击到树枝；丁依次撞击到树枝；戊依次撞击到树枝可得，在前四个位置，，，且一定排在后四个位置，（1）若排在前四个位置中的一个位置，前四个位置有4种排法，若第五个位置排C,则第六个位置一定排D，后三个位置共有3种排法，若第五个位置排D，则后四个位置共有4种排法，所以I排在前四个位置中的一个位置时，共有种排法；（2）若不排在前四个位置中的一个位置，则按顺序排在前四个位置，由于，所以后五个位置的排法就是H的不同排法，共5种排法，即若不排在前四个位置中的一个位置共有5种排法，由分类计数原理可得，这9根树枝从高到低不同的次序有种.故选：D.【点睛】本题主要考查分类计数原理与分步计数原理及排列组合的应用，属于难题.例4．贾同学、王同学、文同学三人在操场踢球,每次传球,传球者将球随机将传给另外两位同学之一,足球最开始在文同学脚下,则:①次传球之后,共有___________种可能的传球方法;②次传球之后,足球回到文同学脚下的传球方法有___________种.【答案】        【解析】【详解】每次传球有两种方法，所以次传球之后,共有种可能的传球方法;设次传球之后,足球回到文同学脚下的传球方法为种.则2，即因为点睛：构造法求数列通项：(1)为常数）,构造等比数列；(2),构造等差数列例5．一只蚂蚁从一个正四面体的顶点出发，每次从一个顶点爬行到另一个顶点，则蚂蚁爬行五次还在点的爬行方法种数是__________．【答案】【解析】方法一：根据题意，蚂蚁第一次爬行可以到的任何一点，再利用第二次爬行到与不到进行分类计算，依次计算即可；方法二：设从点出发爬行次仍在点的爬行方法种数为，由题意得递推关系，进而可得结论.【详解】解法一：第一次爬行可以到的任何一点，第二次爬行分到与不到，对于第二次不到的第三次爬行再分到与不到．爬行方法总数为（种）．解法二：设从点出发爬行次仍在点的爬行方法种数为，则，，，，，．（亦可由递推式从第二项递推出第五项的值）故答案为：.【点睛】本题主要考查了计数原理的应用，构造数列，利用递推关系解决问题，属于中档题.例6．将圆周等分于点，在以其中每三点为顶点的三角形中，含有圆心的三角形个数为__________．【答案】【解析】【详解】任取一个分点记为P，然后将其余个分点这样标志，自P点后，逆时针方向的连续n个点依次记为，顺时针方向的连续n个点依次记为．先考虑以P为顶点且含有圆心的三角形，如图，显然这种三角形的另两个顶点必须一个属于点集，而另一个属于点集．且这种，含有圆心当且仅当．现计算符合条件的三角形个数：当时，j可取值，共计k个值．因此这种含有圆心的个数为，当点P取遍个位置，共得个三角形，由于每个三角形有三个顶点，故每个三角形重复计算了三遍，因此符合条件的三角形个数为．故答案为：.例7．已知集合，记集合H的非空子集为，且记每个子集中各元素的乘积依次为，则的值为____________【答案】【解析】【分析】造出函数，即为所求.【详解】设十个元素为..则即为函数展开式中所有项数之和；因为，所以．故答案为：.【点睛】本题主要考查的集合子集的判定，构造函数求解，属于难题．本题的关键是根据二项定理的推导过程构造出函数，这种转化思想是本题的难点．例8．设集合，选择A的两个非空子集B和C，要使C中最小的数大于B中的最大数，则不同的选择方法有________；【答案】【解析】【分析】分类讨论集合中的最大元素，利用集合的非空子集的个数的求法把所有满足题意的情况求出来即可得出结果.【详解】由题意得：当集合中的最大元素为时，满足题意的集合共有1个，对应的集合共有个，即满足题意的共有个；当集合中的最大元素为时，满足题意的集合共有个，对应的集合共有个，即满足题意的共有个；当集合中的最大元素为时，满足题意的集合共有个，对应的集合共有个，即满足题意的共有个；当集合中的最大元素为时，满足题意的集合共有个，对应的集合共有个，即满足题意的共有个；当集合中的最大元素为时，满足题意的集合共有个，对应的集合共有个，即满足题意的共有个；综上：满足题意的不同的选择方法有：，故答案为：.【点睛】本题主要考查了分步计数原理，集合的子集个数问题以及等比数列的前项和公式，考查分类讨论的数学思想，属于较难题．例9．的展开式中的系数为______.【答案】-6480【解析】【分析】，利用二项式定理得到，再展开，计算得到答案.【详解】，展开式的通项为：，取，则，的展开式的通项为：，取，得到，故的系数为.故答案为：.【点睛】本题考查了二项式定理的应用，意在考查学生的计算能力和应用能力.例10．如图所示是竖直平面内的一个“通道游戏”，图中竖直线段和斜线都表示通道，并且在交点处相遇．若有一条竖直线段的为第一层，第二条竖直线段的为第二层，以此类推，现有一颗小球从第一层的通道向下运动，在通道的交叉处，小球可以落入左右两个通道中的任意一个，记小球落入第层的第个竖直通道（从左向右计）的不同路径数为．（1）求，，的值；（2）猜想的表达式（不必证明），并求不等式的解集．【答案】（1），，；（2），不等式的解集为.【解析】【分析】（1）根据题意得出，，且可求出，，以及；（2）根据可得出，然后得出的表达式，从而得出不等式的解集.【详解】（1）由题意可得，，且.，；（2）由可推得，不等式即为，，，，，.解不等式，可得的可能取值有、、、、、.所以，不等式的解集为.【点睛】本题考查杨辉三角性质的应用，考查组合数的应用以及组合不等式的求解，解题的关键就是要找出递推公式，逐项计算即可，考查运算求解能力，属于中等题.例11．图中竖直线段和斜线段都表示通道，并且在交点处相遇，若竖直线段有一条的为第一层，有两条的为第二层，以此类推，竖直线段有条的为第层，每一层的竖直通道从左到右分别称为第1通道、第2通道，……，现在有一个小球从入口向下（只能向下，不能向上）运动，小球在每个交点处向左到达下一层或者向右到达下一层的可能性是相同的．小球到达第层第通道的不同路径数称为，如小球到达第二层第1通道和第二层第2通道的路径都只有一种情况，因此，.求：（1），，；（2），以及小球到达第5层第2通道的概率；（3）猜想，并证明；（4）猜想（不用证明）．【答案】（1）1，2，1；（2）4，；（3）；（4）【解析】【分析】（1）小球到达第三层第1通道和第三层第2通道的路径、第三层第3通道的路径的情况一一算出即可；（2）小球到达第五层第2通道的情况数是，且每一个分叉处小球落入那一个通道的概率是相同的，根据独立重复试验的概率公式得到结果；（3）根据小球到达第层第2通道的情况数是，推出具有一般性的结论；（4）根据题意知小球到达第层第3通道的情况数是，推出具有一般性的结论．【详解】（1）由题意知，小球到达第三层第1通道的情况数只有一种，∴；小球到达第三层第2通道的情况数只有二种，∴；小球到达第三层第3通道的情况数只有一种，∴；（2），且每一个分叉处小球落入那一个通道的概率是相同的，根据独立重复试验的概率公式得小球到达第5层第2通道的概率为：，（3）猜想（），∵本图中通道的不同路径数正是杨辉三角数，根据杨辉三角数可知：∴第行的第2个二项式系数为；（4）由（3）可知，根据杨辉三角数，小球到达第层第3通道的情况数为，所以猜想小球到达第层第3通道的情况数：（）．【点睛】本题主要考查杨辉三角数，考查独立重复试验的概率公式，考查归纳推理，属于中档题.例12．考查所有排列，将每种排列视为一个元有序实数组，设且，设为的最大项，其中.记数组为.例如，时，；时，.若数组中的不同元素个数为2.（1）若，求所有元有序实数组的个数；（2）求所有元有序实数组的个数.【答案】（1）11；（2）【解析】【分析】（1）数组中的不同元素个数为2，故为1，2，3中的的任意一个，根据4的位置讨论即可得到有序实数组的个数；（2）数组中的不同元素个数为2，为1，2，中的的任意一个，则数，只能在之后，而在和之间只能出现1，2，中的某些数，设，根据计数原理以及排列组合知识即可得到当时，数组的个数，进而当从1变化到时，即可求出元有序实数组的全部个数．【详解】（1）因为数组中的不同元素个数为2，所以为1，2，3中的任意一个，即4只能为或或.当时，则是1，2，3的任意一个排列，总数有个；当时，则是1，2，3的一个排列，且，故为或或，总数有3个；当时，则是1，2，3，的任意一个排列，且，故为或，总数有2个；综上，有序实数组的个数为，（2）因为数组中的不同元素个数为2，所以为中的任意一个.当时，数在中必须位于之后，而在与之间只能出现中的某些数，所以只能作出现.当时，可为从中任意选出个元素的排列，而则为其余个元素的全排列.所以与相对应的排列个数为：.所以所有元有序实数组的个数记为，则【点睛】本题考查对数列新定