排列组合的基本方法——隔板法

一、 知识要点预备：二、 知识要点：排列组合的基本方法隔板法 排列组合中分配问题，是排列组合中的难点问题，其中涉及到名额分配或相同物品的分配问题，适宜采用隔板法，下面我们就来一起研究一下这种方法。例1 10个优秀指标名额分配给6个班级，每个班至少一个，共有多少种不同的分配方法？解析：本小题涉及到了名额分配的问题，宜采用隔板法。用5个隔板插入10个指标中的9个空隙，即有种方法。按照第一个隔板前的指标数为1班的指标，第一个隔板与第二个隔板之间的指标数为2班的指标依此类推，共有种分法。例2 10个优秀指标名额分配到一、二、三3个班，若名额数不少于班级序号数，共有多少种不同的分配方法？解析：先拿3个指标分配给二班一个，三班两个，然后，问题就转化为7个优秀名额分配个三个班级，每班至少一个。由例1可知，共有种不同的分配方法。例3 研究不定方程的正整数解有多少个？解析：该问题可以这样处理：将方程左边的看成是4个班级得到的名额数，右边的10看成是10个名额。这样就相当于10个优秀名额分配到4个班级，每个班级至少有一个名额，共有多少种不同的分配方法。这样，本题就转化为里例1的形式，所以本题的答案即为。例4 研究不定方程的非负整数解有多少个？解析：本题与上一题的不同点就在于本题求的是非负整数解的个数，即有可能等于0，所以本题就不能再直接的看成是例1的名额分配的问题了。但我们可以通过转化将其转化为名额分配的问题。方程即为，通过这样的转化形式，、就都是正整数了。所以本题的最后答案是。对应练习：1某校准备组建一个由12人组成篮球队，这12个人由8个班的学生组成，每班至少一人，名额分配方案共 _种 。2有20个不加区别的小球放入编号为1，2，3的三个盒子里，要求每个盒子内的球数不少编号数，问有多少种不同的方法？（）3不定方程中不同的整数解有_个。（）答案：1 2 3例析隔板法的应用基础题型：将n个相同元素分给m个不同对象（nm），每个对象至少有一个元素，由Cn-1m-1种方法。解析：本题型可描述为n-1个空中插入m-1块板，共有 Cn-1m-1种方法。此种解法称为隔板法。下面通过几个例题体会一下隔板法的应用。例1 从5个学校选出8名学生组成代表团，每校至少有一人的选法种数是多少？解析：按常规，从5个学校选8名学生，要考虑5个学校人员的分配，需要分类讨论，太繁琐。逆向思考，假设8名学生的代表团已组建好，现将其返回到5个学校，每校至少一人，用“0”表示学生，如图， 00000000问题转化为将8个学生分成5组，每组至少一人，在上图中，7个空档中插入4块隔板即可将其分成5组，故有C74=35种选法。例2 20个不加区别的小球放入编号为1号、2号、3号的三个盒子里，要求每 个盒内的球数不小于盒子的编号数，问有多少种放法？解析：先取出3个球，其中1个球放入2号盒内，再将其余的2个球放入3号盒内。则此题转化为17个球放入3个不同盒内，每盒至少一球，有多少种放法？即16个空档中插入2个隔板即可将其分成3组，故有C162=120种放法。例3 求方程x+y+z+m+n=50共有多少组正整数解？解析：此题分类不易解决。若用穷举法，未知数太多，不宜入手。若寻找解多元方程的思想，更不可取。不妨转化一下观念：因为求的是正整数解，可看作50个小球放入5个盒子，每个盒子至少一球的放法数，即49个空档中插入4块隔板将其分成5组，所以原题有C494组正整数解。例4 求方程x+y+z+m+n=50共有多少组自然数解？解析：对于此题需要注意与例3的区别，例3求的是正整数解，而此题求的是自然数解，自然数包含着0。所以此题可转化为：50个小球放入5个盒内，可空的放法有多少？对于此题可以先额外的每盒放入一个球，并不影响总的放法数，即本题又转化为55个球放入5个盒内，每盒至少有一球的放法数。故本题结果为C544组自然数解。练习：（a+b+c+d）12展开式合并同类项后，共有几项？（提示：一般项为axbyczdm,x+y+z+m=12(x,y,z,mN+