隔板法在排列组合中的应用技巧.pdfVIP

解题思想方法 隔板法在排列组合中的应用技巧 ■湖北 　　张红兵 在排列组合中, 对于将不可分辨的球装入到可以分辨的盒子中而求装入方法数 的问题, 常用隔板法. 例 1 　求方程 x + y + z = 10 的正整数解的个数. 将 10 个球排成一排, 球与球之间形成 9 个空隙, 将两个隔板插入 ( ) 这些空隙中 每空至多插一块隔板 , 规定由隔板分成的左 、中、右三部 ( ) 分的球数分别为 x 、y 、z 之值 如下图 . 则隔法与解的个数之间建立了 2 ( ) 一一对立关系, 故解的个数为 C = 36 个 . 实际运用隔板法解题时, 在确定球数 、如 9 何插隔板等问题上形成了一些技巧. 下面举例说明. 技巧一 :添加球数用隔板法. 例 2 　求方程 x + y + z = 10 的非负整数解的 个数. 注意到 x 、y 、z 可以为零, 故上题解法中的限定“每空至多插一块 隔板”就不成立了, 怎么办呢 ? 只要添加三个球, 给 x 、y 、z 各一个球. 这样原问题就转化为求 x + y + z = 13 的正整数解的个数了, 故解的个 2 ( ) 数为 C12 = 66 个 . 本例通过添加球数, 将问题转化为如例 1 中的典型隔板法问题. 技巧二 :减少球数用隔板法. 例 3 　将 20 个相同的小球放入编号分别为 1 , 2 , 3 , 4 的四个盒子中, 要求每个盒 子中的球数不少于它的编号数, 求放法总数. 解法 1 :先在编号 1,2 , 3 ,4 的四个盒子内分别放 0 , 1, 2 , 3 个球, 剩下 14 个球, 有 1 种 3 ( ) 方法;再把剩下的球分成 4 组,每组至少 1 个, 由例 1 知方法有 C = 286 种 . 13 解法 2 :第一步先在编号 1 , 2 , 3 , 4 的四个盒子内分别放 1 , 2 , 3 , 4 个球, 剩下 10 个 球, 有 1 种方法; 第二步把剩下的 10 个相同的球放入编号为 1 , 2 , 3 , 4 的盒子里, 由例 3 ( ) 2 知方法有 C13 = 286 种 . 8 在上述同学们提出的疑问中, 分子 C18 表示将 18 个人分成两组, 其中一组 8 人, 另一组 10 人, 属于“分成甲、乙两组”的类型, 具有指向性; 而 C10 表示将 20 个人平均 20 ( ) 分成两组, 不具有指向性. 责任编辑 　朱 　宁 ( )