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

排列组合问题——插板法(分组)、插空法(不相邻)、捆绑法(相邻)插板法(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),适用插板法,c92=36 下面通过几道题目介绍下插板法的应用 e二次插板法 例8:在一张节目单中原有6个节目,若保持这些节目相对次序不变,再添加3个节目,共有几种情况?-o-o-o-o-o-o-三个节目abc 可以用一个节目去插7个空位,再用第二个节目去插8个空位,用最后个节目去插9个空位 所以一共是c71×c81×c91=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份,每个班级依次按班级序号分到对应位置的几个球(可能是1个、2个、3个、4个),这样,借助于虚拟“档板”就可以把10个球分到了7个班中。    【基本题型的变形(一)】题型:有n个相同的元素,要求分到m组中,问有多少种不同的分法?解题思路:这种问题是允许有些组中分到的元素为“0”,也就是组中可以为空的。对于这样的题,我们就首先将每组都填上1个,这样所要元素总数就m个,问题也就是转变成将(n+m)个元素分到m组,并且每组至少分到一个的问题,也就可以用插板法来解决。  【例2】有8个相同的球放到三个不同的盒子里,共有()种不同方法. :题目允许盒子有空,则需要每个组添加1个,则球的总数为8+3×1=11,此题就有C(10,2)=45(种)分法了,选项D为正确答案。【基本题型的变形(二)】题型:有n个相同的元素,要求分到m组,要求各组中分到的元素至少某个确定值S(s>1,且每组的s值可以不同),问有多少种不同的分法?解题思路:这种问题是要求组中分到的元素不能少某个确定值s,各组分到的不是至少为一个了。对于这样的题,我们就首先将各组都填满,即各组就填上对应的确定值s那么多个,这样就满足了题目中要求的最起码的条件,之后我们再分剩下的球。这样这个问题就转变为上面我们提到的变形(一)的问题了,我们也就可以用插板法来解决。【例3】15个相同的球放入编号为1、2、3的盒子内,盒内球数不少于编号数,有几种不同的放法?解析:编号1:至少1个,符合要求。编号2:至少2个:需预先添加1个球,则总数-1编号3:至少3个,需预先添加2个,才能满足条件,后面添加一个,则总数-2则球总数15-1-2=12个放进3个盒子里所以C(11,2)=55(种)【例】10个学生中,男女生各有5人,选4人参加数学竞赛。(1)至少有一名女生的选法种数为_______________。(2)A、B两人中最多只有一人参加的选法种数为___________解法1:10名中选4名代表的选法的种类:C104,排除4名参赛全是男生:C54(排除法)C104----C54=205解法2:选1女生时,选2个女生时,选3、4个女生时的选法,分别相加真题(2010年国考真题)某单位订阅了30份学****材