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

排列组合问题——插板法（分组）、插空法（不相邻）、捆绑法（相邻）
　 　 　 插 　板 法 （m为空的数量） 　　 　 　　 　　 　　
【基本题型】ﻫ有n个相同的元素，要求分到不同的m组中,且每组至少有一个元素，问有多少种分法？ﻫ
图中“　”表示相同的名额，“ "表示名额间形成的空隙,设想在这几个空隙中插入六块“挡板”，则将这1０ 个名额分割成七个部分，将第一、二、三、……七个部分所包含的名额数分给第一、二、三……七所学校，则“挡板"的一种插法恰好对应了1０ 个名额的一种分配方法，反之，名额的一种分配方法也决定了档板的一种插法,即挡板的插法种数与名额的分配方法种数是相等的，
【总结】
需满足条件:n个相同元素,不同个ｍ组，每组至少有一个元素，则只需在n个元素的n－1个间隙中放置m-1块隔板把它隔成ｍ份即可，共有种不同方法。
注意:这样对于很多的问题,,可以通过一定的转变，将其变成符合上面3个条件的问题,这样就可以利用插板法解决,并且常常会产生意想不到的效果。
插板法就是在ｎ个元素间的（n－1）个空中插入 若干个（ｂ）个板，可以把n个元素分成（b＋1)组的方法。
应用插板法必须满足三个条件：
（1) 这n个元素必须互不相异 ﻫ（2) 所分成的每一组至少分得一个元素 
（3） 分成的组别彼此相异 ﻫ举个很普通的例子来说明 
把１0个相同的小球放入3个不同的箱子，每个箱子至少一个，问有几种情况?
问题的题干满足 条件（1)（２）,适用插板法，c9 2＝36 ﻫ下面通过几道题目介绍下插板法的应用 
e 二次插板法 ﻫ例８ ：在一张节目单中原有6个节目，若保持这些节目相对次序不变,再添加3个节目,共有几种情况？
-o - o - ｏ － o — o － o - 三个节目abc ﻫ可以用一个节目去插７个空位,再用第二个节目去插８个空位，用最后个节目去插9个空位 ﻫ所以一共是 c7 1×c8 １×c9 1=504种
ﻫ
【基本解题思路】ﻫ将n个相同的元素排成一行，ｎ个元素之间出现了（n-１）个空档,现在我们用(ｍ—1)个“档板”插入（n—1）个空档中,就把n个元素隔成有序的m份，每个组依次按组序号分到对应位置的几个元素（可能是1个、2个、3个、4个、….），这样不同的插入办法就对应着n个相同的元素分到m组的一种分法，这种借助于这样的虚拟“档板”分配元素的方法称之为插板法。ﻫ
【基本题型例题】
 【例1】　共有１0完全相同的球分到7个班里,每个班至少要分到一个球,问有几种不同分法？ﻫ解析：我们可以将10个相同的球排成一行，10个球之间出现了９个空隙,现在我们用6个档板”插入这9个空隙中，就“把10个球隔成有序的7份，每个班级依次按班级序号分到对应位置的几个球（可能是
1个、２个、３个、4个），这样，借助于虚拟“档板”就可以把１0个球分到了7个班中。ﻫ    
【基本题型的变形（一）】ﻫ
题型：有n个相同的元素，要求分到m组中，问有多少种不同的分法？ﻫ解题思路：这种问题是允许有些组中分到的元素为“0”，也就是组中可以为空的。对于这样的题，我们就首先将每组都填上1个，这样所要元素总数就m个，问题也就是转变成将（n+ｍ）个元素分到ｍ组，并且每组至少分到一个的问题，也就可以用插板法来解决。  　
【例2】有8个相同的球放到三个不同的盒子里，共有( ）　　Ａ．3５ B．28 C．21 D．4５ﻫ解答:题目允许盒子有空，则需要每个组添加１个，则球的总数为8+3×1=11,此题就有Ｃ(10,2）=45(种）分法了,
【基本题型的变形（二)】ﻫ题型：有n个相同的元素,要求分到ｍ组，要求各组中分到的元素至少某个确定值S(s＞1，且每组的s值可以不同），问有多少种不同的分法？　
ﻫ解题思路：这种问题是要求组中分到的元素不能少某个确定值s,，我们就首先将各组都填满,即各组就填上对应的确定值s那么多个,这样就满足了题目中要求的最起码的条件，之后我们再分剩下的球。这样这个问题就转变为上面我们提到的变形(一）的问题了，我们也就可以用插板法来解决.
ﻫ【例3】1５个相同的球放入编号为１、２、3的盒子内，盒内球数不少于编号数,有几种不同的放法？ﻫ解析:ﻫ编号1：至少1个，符合要求.
编号2：至少２个：需预先添加1个球,则总数－1
编号3：至少3个，需预先添加2个,才能满足条件，后面添加一个，则总数—２
则球总数1５-1—2=1２个放进3个盒子里
所以C（1１,2）=55(种）ﻫ
【例】1０