排列组合插板法、插空法、捆绑法.doc

. .
. .word..
排列组合问题——插板法(分组)、插空法〔不相邻〕、捆绑法〔相邻〕
插板法〔m为空的数量〕
【基此题型】有n个一样的元素，要求分到不同的m组中，且每组至少有一个元素，问有多少种分法？
图中“〞表示一样的名额，“〞表示名额间形成的空隙，设想在这几个空隙中插入六块“挡板〞，那么将这10 个名额分割成七个局部，将第一、二、三、……七个局部所包含的名额数分给第一、二、三……七所学校，那么“挡板〞的一种插法恰好对应了10 个名额的一种分配方法，反之，名额的一种分配方法也决定了档板的一种插法，即挡板的插法种数与名额的分配方法种数是相等的，
【总结】需满足条件：n个一样元素，不同个m组，每组至少有一个元素，那么只需在n个元素的n-1个间隙中放置m-1块隔板把它隔成m份即可,共有种不同方法。
注意：这样对于很多的问题，是不能直接利用插板法解题的。但，可以通过一定的转变，将其变成符合上面3个条件的问题，这样就可以利用插板法解决，并且常常会产生意想不到的效果。
插板法就是在n个元素间的〔n-1〕个空中插入假设干个〔b〕个板,可以把n个元素分成〔b+1〕：〔1〕这n个元素必须互不相异 〔2〕所分成的每一组至少分得一个元素 (3) 分成的组别彼此相异 举个很普通的例子来说明 把10个一样的小球放入3个不同的箱子,每个箱子至少一个,问有几种情况?问题的题干满足条件〔1〕〔2〕,适用插板法,c9 2=36 下面通过几道题目介绍下插板法的应用 e 二次插板法 例8 ：在一X节目单中原有6个节目,假设保持这些节目相对次序不变,再添加3个节目,共有几种情况?-o - o - o - o - o - o - 三个节目abc 可以用一个节目去插7个空位,再用第二个节目去插8个空位,用最后个节目去插9个空位 所以一共是 c7 1×c8 1×c9 1=504种
【根本解题思路】将n个一样的元素排成一行，n个元素之间出现了〔n-1〕个空档，现在我们用〔m-1〕个“档板〞插入〔n-1〕个空档中，就把n个元素隔成有序的m份，每个组依次按组序号分到对应位置的几个元素〔可能是1个、2个、3个、4个、….〕，这样不同的插入方法就对应着n个一样的元素分到m组的一种分法，这种借助于这样的虚拟“档板〞分配元素的方法称之为插板法。
【基此题型例题】
 【例1】共有10完全一样的球分到7个班里，每个班至少要分到一个球，问有几种不同分法？解析：我们可以将10个一样的球排成一行，10个球之间出现了9个空隙，现在我们用6个档板〞插入这9个空隙中，就“把10个球隔成有序的7份，每个班级依次按班级序号分到对应位置的几个球〔可