《排列组合--插板法、插空法、捆绑法29171.pdf》由会员分享，可在线阅读，更多相关《排列组合--插板法、插空法、捆绑法29171.pdf（6页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、排列组合问题插板法(分组)、插空法（不相邻）、捆绑法（相邻）插 板 法 （m 为空的数量）【基本题型】有 n 个相同的元素，要求分到不同的 m 组中，且每组至少有一个元素，问有多少种分法？图中“”表示相同的名额，“”表示名额间形成的空隙，设想在这几个空隙中插入六块“挡板”，则将这 10 个名额分割成七个部分，将第一、二、三、七个部分所包含的名额数分给第一、二、三七所学校，则“挡板”的一种插法恰好对应了 10 个名额的一种分配方法，反之，名额的一种分配方法也决定了档板的一种插法，即挡板的插法种数与名额的分配方法种数是相等的，【总结】需满足条件：n 个相同元素，不同个 m 组，每组至少有一个元素，
2、则只需在 n 个元素的 n-1个间隙中放置 m-1 块隔板把它隔成 m 份即可,共有种不同方法。注意：这样对于很多的问题，是不能直接利用插板法解题的。但，可以通过一定的转变，将其变成符合上面 3 个条件的问题，这样就可以利用插板法解决，并且常常会产生意想不到的效果。【基本解题思路】将 n 个相同的元素排成一行，n 个元素之间出现了（n-1）个空档，现在我们用（m-1）个“档板”插入（n-1）个空档中，就把 n 个元素隔成有序的 m 份，每个组依次按组序号分到对应位置的几个元素（可能是 1 个、2个、3 个、4 个、.），这样不同的插入办法就对应着 n 个相同的元素分到 m 组的一种分法，这种借
3、助于这样的虚拟“档板”分配元素的方法称之为插板法。【基本题型例题】【例 1】共有 10 完全相同的球分到 7 个班里，每个班至少要分到一个球，问有几种不同分法？解析：我们可以将 10 个相同的球排成一行，10 个球之间出现了 9 个空隙，现在我们用 6 个档板”插入这 9个空隙中，就“把 10 个球隔成有序的 7 份，每个班级依次按班级序号分到对应位置的几个球（可能是 1 个、2 个、3 个、4 个），这样，借助于虚拟“档板”就可以把 10 个球分到了 7 个班中。【基本题型的变形（一）】题型：有 n 个相同的元素，要求分到 m 组中，问有多少种不同的分法？解题思路：这种问题是允许有些组中分到
4、的元素为“0”，也就是组中可以为空的。对于这样的题，我们就首先将每组都填上 1 个，这样所要元素总数就 m 个，问题也就是转变成将（n+m）个元素分到 m 组，并且每组至少分到一个的问题，也就可以用插板法来解决。【例 2】有 8 个相同的球放到三个不同的盒子里，共有（）种不同方法.A35 B28 C21 D45 解答：题目允许盒子有空，则需要每个组添加 1 个，则球的总数为 8+31=11，此题就有 C（10，2）=45（种）分法了，选项 D 为正确答案。【基本题型的变形（二）】题型：有 n 个相同的元素，要求分到 m 组，要求各组中分到的元素至少某个确定值 S（s1，且每组的 s 值可以不同
5、），问有多少种不同的分法 解题思路：这种问题是要求组中分到的元素不能少某个确定值 s，各组分到的不是至少为一个了。对于这样的题，我们就首先将各组都填满，即各组就填上对应的确定值 s 那么多个，这样就满足了题目中要求的最起码的条件，之后我们再分剩下的球。这样这个问题就转变为上面我们提到的变形（一）的问题了，我们也就可以用插板法来解决。【例 3】15 个相同的球放入编号为 1、2、3 的盒子内，盒内球数不少于编号数，有几种不同的放法？解析：编号 1：至少 1 个，符合要求。编号 2：至少 2 个：需预先添加 1 个球，则总数-1 编号 3：至少 3 个，需预先添加 2 个，才能满足条件，后面添加一
6、个，则总数-2 则球总数 15-1-2=12 个放进 3 个盒子里 所以 C（11，2）=55（种）【例】10 个学生中，男女生各有 5 人，选 4 人参加数学竞赛。（1）至少有一名女生的选法种数为_。（2）A、B 两人中最多只有一人参加的选法种数为_ 解法1：10 名中选4 名代表的选法的种类：C排除4名参赛全是男生：C4 (排除法)CC4=205 解法 2：选 1 女生时，选 2 个女生时，选 3、4 个女生时的选法，分别相加 （2010 年国考真题）某单位订阅了 30 份学习材料发放给 3 个部门，每个部门至少发放 9 份材料。问一共有多少种不同的发放方法（）解析：每个部门先放 8 个，
7、后面就至少放一个，三个部门则要先放 83=24 份，还剩下 30-24=6 份来放入这三个部门，且每个部门至少发放 1 份，则 C（5,2）=10 插 空 法 插空法就是对于解决某几个元素要求不相邻的问题时，先将其他元素排好，再将所指定的不相邻的元素插入它们的间隙或两端位置。首要特点就是不相邻。下面举例说明。一.数字问题【例】把1，2，3，4，5组成没有重复数字且数字1，2不相邻的五位数，则所有不同排法有多少种 解析：本题直接解答较为麻烦，因为可先将3，4，5三个元素排定，共有种排法，然后再将1，2插入四个空位共有种排法，故由乘法原理得，所有不同的五位数有 二.节目单问题【例】在一张节目单中原
8、有六个节目，若保持这些节目的相对顺序不变，再添加进去三个节目，则所有不同的添加方法共有多少种 解析：-o-o-o-o-o-o-六个节目算上前后共有七个空位，那么加上的第一个节目则有种方法；此时有七个节目，再用第二个节目去插八个空位有种方法；此时有八个节目，用最后一个节目去插九个空位有种方法。由乘法原理得，所有不同的添加方法为：。三.关灯问题【例】一条马路上有编号1，2，3，4，5，6，7，8，9的九盏路灯，为了节约用电，可以把其中的三盏灯关掉，但不能同时关掉相邻两盏或三盏，则所有不同的关灯方法有多少种 解析：如果直接解答须分类讨论，故可把六盏亮着的灯看作六个元素，然后用不亮的三盏灯去插七个空位
9、（用不亮的3盏灯去插剩下亮的6盏灯空位，就有7个空位）共有种方法，因此所有不同的关灯方法为种。四.停车问题【例】停车场划出一排12个停车位置，今有8辆车需要停放，要求空位置连在一起，不同的停车方法有多少种 解析：先排好8辆车有种方法，要求空位置连在一起（剩下4个空位在一起，来插入8辆车，有9个空位可以插），将空位置插入其中有种方法。所以共有种方法。五.座位问题【例】3个人坐在一排8个椅子上，若每个人左右两边都有空位，则坐法的种类有多少种 解法：先拿出5个椅子排成一排，在5个椅子中间出现4个空，再让3个人每人带一把椅子去插空，于是有种。捆 绑 法 解答：根据题目要求，则其中一个盒子必须得放 2 个，其他每个盒子放 1 个球，所以从 6 个球中挑出 2 个球看成一个整体，则有26C，这个整体和剩下 4 个球放入 5 个盒子里，则有55A。方法是26C55A