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

1、一、知识要点预备：二、知识要点：排列组合的基本方法隔板法 排列组合中分配问题，是排列组合中的难点问题，其中涉及到名 额分配或相同物品的分配问题， 适宜采用隔板法， 下面我们就来一起 研究一下这种方法。例 1 10 个优秀指标名额分配给 6 个班级，每个班至少一个， 共有多少种不同的分配方法？解析： 本小题涉及到了名额分配的问题，宜采用隔板法。用 5 个隔板插入10个指标中的9个空隙，即有C：种方法。按照第一个隔 板前的指标数为 1 班的指标，第一个隔板与第二个隔板之间的指标 数为2班的指标依此类推，共有 d 126种分法。例 2 10 个优秀指标名额分配到一、二、三 3 个班，若名额数 不少于

2、班级序号数，共有多少种不同的分配方法？解析： 先拿 3 个指标分配给二班一个，三班两个，然后，问题 就转化为 7 个优秀名额分配个三个班级，每班至少一个。由例 1 可 知，共有 C62 15种不同的分配方法。例 3 研究不定方程 x1 x2 x3 x4 10的正整数解有多少个？解析：该问题可以这样处理：将方程左边的 Xi、xy X3、x看成是 4 个班级得到的名额数， 右边的 10 看成是 10 个名额。这样就相当于 10 个优秀名额分配到 4 个班级，每个班级至少有一个名额，共有多 少种不同的分配方法。这样，本题就转化为里例 1 的形式，所以本 题的答案即为 C93 84。例4研究不定方程x

3、1 x2 x3 x4 10的非负整数解有多少个？解析：本题与上一题的不同点就在于本题求的是非负整数解的 个数，即Xi、X2、X3、X4有可能等于0,所以本题就不能再直接的看成 是例1的名额分配的问题了。但我们可以通过转化将其转化为名额 分配的问题。方程 Xi X2 X3 X4 10 即为 （Xi 1） （X2 1）（X3+I） （X4 1） 14，通过这样的转化形式，Xi 1、X2 1、 X3+I、X4 1就都是正整数了。所以本题的最后答案是G286。对应练习：1.某校准备组建一个由12人组成篮球队，这12个人由8个班 的学生组成，每班至少一人，名额分配方案共 种。2 .有20个不加区别的小球

4、放入编号为1, 2, 3的三个盒子里， 要求每个盒子内的球数不少编号数，问有多少种不同的方法？（C；）3.不定方程X1 X2 X3 L X50 100中不同的整数解有 个。（C999 ）答案：1 . C171330 2 . C：6 120 3 . c9；例析隔板法的应用基础题型：将n个相同元素分给m个不同对象（nm）,每个对象 至少有一个元素，由G-1m-1种方法。解析：本题型可描述为n-1个空中插入m-1块板，共有Cn-1m-1种 方法。此种解法称为隔板法。下面通过几个例题体会一下隔板法的应例1 从 5 个学校选出 8 名学生组成代表团，每校至少有一人的选 法种数是多少？解析：按常规，从 5

5、 个学校选 8 名学生，要考虑 5 个学校人员的 分配，需要分类讨论，太繁琐。逆向思考，假设 8 名学生的代表团已 组建好，现将其返回到 5 个学校，每校至少一人，用“ 0”表示学生，如图， 0 I 00 I 00 I 00 I 0 问题转化为将 8 个学生分成 5 组，每组至少一人，在上图中， 7 个空 档中插入4块隔板即可将其分成5组，故有G4=35种选法。例2 20 个不加区别的小球放入编号为 1 号、2 号、3 号的三个盒 子里，要求每 个盒内的球数不小于盒子的编号数， 问 有多少种放法？解析：先取出 3 个球，其中 1 个球放入 2 号盒内，再将其余的 2 个球放入 3 号盒内。则此

6、题转化为 17 个球放入 3 个不同盒内，每盒 至少一球，有多少种放法？即 16 个空档中插入 2 个隔板即可将其分 成3组，故有Ci62=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展开式合并同类项后，共有几项？（提示：一般项为 axbyczd；x+y+z+m=12（x,y,z,m N）最后谈一点学习体会： 我们平时在解答每一个典型问题后， 不要 立即如释重负地