排列组合--插板法、插空法、捆绑法

《排列组合--插板法、插空法、捆绑法》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、..-排列组合问题——插板法(分组)、插空法〔不相邻〕、捆绑法〔相邻〕插板法〔m为空的数量〕【基此题型】有n个一样的元素，要求分到不同的m组中，且每组至少有一个元素，问有多少种分法？图中“〞表示一样的名额，“〞表示名额间形成的空隙，设想在这几个空隙中插入六块“挡板〞，那么将这10个名额分割成七个局部，将第一、二、三、……七个局部所包含的名额数分给第一、二、三……七所学校，那么“挡板〞的一种插法恰好对应了10个名额的一种分配方法，反之，名额的一种分配方法也决定了档板的一种插法，即挡板的插法种数与名额的分配方法种数是相等的，【总结】需满足条

2、件：n个一样元素，不同个m组，每组至少有一个元素，那么只需在n个元素的n-1个间隙中放置m-1块隔板把它隔成m份即可,共有种不同方法。注意：这样对于很多的问题，是不能直接利用插板法解题的。但，可以通过一定的转变，将其变成符合上面3个条件的问题，这样就可以利用插板法解决，并且常常会产生意想不到的效果。【根本解题思路】将n个一样的元素排成一行，n个元素之间出现了〔n-1〕个空档，现在我们用〔m-1〕个“档板〞插入〔n-1〕个空档中，就把n个元素隔成有序的m份，每个组依次按组序号分到对应位置的几个元素〔可能是1个、2个、3个、4个、….〕，这

3、样不同的插入方法就对应着n个一样的元素分到m组的一种分法，这种借助于这样的虚拟“档板〞分配元素的方法称之为插板法。【基此题型例题】 【例1】共有10完全一样的球分到7个班里，每个班至少要分到一个球，问有几种不同分法？解析：我们可以将10个一样的球排成一行，10个球之间出现了9个空隙，现在我们用6个档板〞插入这9个空隙中，就“把10个球隔成有序的7份，每个班级依次按班级序号分到对应位置的几个球〔可能是1个、2个、3个、4个〕，这样，借助于虚拟“档板〞就可以把10个球分到了7个班中。    【基此题型的变形〔一〕】题型：有n个一样的元素，要

4、求分到m组中，问有多少种不同的分法？解题思路：这种问题是允许有些组中分到的元素为“0〞，也就是组中可以为空的。对于这样的题，我们就首先将每组都填上1个，这样所要元素总数就m个，问题也就是转变成将〔n+m〕个元素分到m组，并且每组至少分到一个的问题，也就可以用插板法来解决。  【例2】有8个一样的球放到三个不同的盒子里，共有〔〕种不同方法.A．35B．28C．21D．45解答：题目允许盒子有空，那么需要每个组添加1个，那么球的总数为8+3×1=11，此题就有C〔10，2〕=45〔种〕分法了，选项D为正确答案。【基此题型的变形〔二〕】题型：

5、有n个一样的元素，要求分到m组，要求各组中分到的元素至少某个确定值S〔s＞1，且每组的s值可以不同〕，问有多少种不同的分法？解题思路：这种问题是要求组中分到的元素不能少某个确定值s，各组分到的不是至少为一个了。对于这样的题，我们就首先将各组都填满，即各组就填上对应确实定值s那么多个，这样就满足了题目中要求的最起码的条件，之后我们再分剩下的球。这样这个问题就转变为上面我们提到的变形〔一〕的问题了，我们也就可以用插板法来解决。【例3】15个一样的球放入编号为1、2、3的盒子，盒球数不少于编号数，有几种不同的放法？解析：编号1：至少1个，符合

6、要求。编号2：至少2个：需预先添加1个球，那么总数-1编号3：至少3个，需预先添加2个，才能满足条件，后面添加一个，那么总数-2那么球总数15-1-2=12个放进3个盒子里所以C〔11，2〕=55〔种〕..word.zl-..-【例】10个学生中，男女生各有5人，选4人参加数学竞赛。〔1〕至少有一名女生的选法种数为_______________。〔2〕A、B两人中最多只有一人参加的选法种数为___________解法1：10名中选4名代表的选法的种类：C104,排除4名参赛全是男生：C54(排除法)C104----C54=205解法2：

7、选1女生时，选2个女生时，选3、4个女生时的选法，分别相加〔2010年国考真题〕某单位订阅了30份学习材料发放给3个部门，每个部门至少发放9份材料。问一共有多少种不同的发放方法？〔〕A.7B.9C.10D.12解析：每个部门先放8个，后面就至少放一个，三个部门那么要先放8×3=24份，还剩下30-24=6份来放入这三个部门，且每个部门至少发放1份，那么C〔5,2〕=10..word.zl-..-插空法插空法就是对于解决某几个元素要求不相邻的问题时，先将其他元素排好，再将所指定的不相邻的元素插入它们的间隙或两端位置。首要特点就是不相邻。下

8、面举例说明。一.数字问题【例】把1，2，3，4，5组成没有重复数字且数字1，2不相邻的五位数，那么所有不同排法有多少种？解析：此题直接解答较为麻烦，因为可先将3，4，5三个元素排定，共有种排法，然后再将1，