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

排列组合问题插板法(分组)、插空法(不相邻)、捆绑法（相邻)插板法(为空得数量)【基本题型】有个相同得元素,要求分到不同得组中,且每组至少有一个元素,问有多少种分法?图中“”表示相同得名额,“”表示名额间形成得空隙,设想在这几个空隙中插入六块“挡板”,则将这1 个名额分割成七个部分,将第一、二、三、七个部分所包含得名额数分给第一、二、三七所学校,则“挡板”得一种插法恰好对应了10 个名额得一种分配方法,反之,名额得一种分配方法也决定了档板得一种插法,即挡板得插法种数与名额得分配方法种数就是相等得，【总结】需满足条件:n个相同元素，不同个m组，每组至少有一个元素，则只需在n个元素得n个间隙中放置1块隔板把它隔成m份即可,共有种不同方法。注意：这样对于很多得问题，就是不能直接利用插板法解题得。但,可以通过一定得转变,将其变成符合上面3个条件得问题,这样就可以利用插板法解决,并且常常会产生意想不到得效果。插板法就就是在n个元素间得(n-1)个空中插入若干个(b）个板，可以把n个元素分成(+)组得方法、应用插板法必须满足三个条件：(1)这个元素必须互不相异(）所分成得每一组至少分得一个元素(3） 分成得组别彼此相异举个很普通得例子来说明把10个相同得小球放入3个不同得箱子,每个箱子至少一个,问有几种情况?问题得题干满足条件(1)(2),适用插板法,c9=36下面通过几道题目介绍下插板法得应用e 二次插板法例8 ：在一张节目单中原有6个节目,若保持这些节目相对次序不变,再添加3个节目，共有几种情况?-o o -o - o o - 三个节目abc可以用一个节目去插7个空位,再用第二个节目去插8个空位，用最后个节目去插9个空位所以一共就是c7 1 1 1=504种【基本解题思路】将个相同得元素排成一行，n个元素之间出现了(n1)个空档,现在我们用（m-1)个“档板”插入（-1）个空档中,就把n个元素隔成有序得m份,每个组依次按组序号分到对应位置得几个元素(可能就是1个、2个、3个、个、),这样不同得插入办法就对应着n个相同得元素分到组得一种分法,这种借助于这样得虚拟“档板”分配元素得方法称之为插板法。【基本题型例题】【例1】共有10完全相同得球分到个班里,每个班至少要分到一个球，问有几种不同分法？解析:我们可以将1个相同得球排成一行,10个球之间出现了9个空隙,现在我们用6个档板”插入这个空隙中,就“把1个球隔成有序得7份，每个班级依次按班级序号分到对应位置得几个球(可能就是1个、2个、3个、4个),这样，借助于虚拟“档板”就可以把10个球分到了个班中。【基本题型得变形（一)】题型:有n个相同得元素,要求分到组中，问有多少种不同得分法？解题思路：这种问题就是允许有些组中分到得元素为“0”,也就就是组中可以为空得。对于这样得题,我们就首先将每组都填上1个,这样所要元素总数就m个,问题也就就是转变成将(m)个元素分到组,并且每组至少分到一个得问题，也就可以用插板法来解决。 【例2】有个相同得球放到三个不同得盒子里,共有（)种不同方法、 35 .28C.21 D.45解答:题目允许盒子有空,则需要每个组添加1个,则球得总数为8+3=11,此题就有(10,）=（种）分法了，选项为正确答案。【基本题型得变形(二)】题型：有n个相同得元素,要求分到m组,要求各组中分到得元素至少某个确定值S(1,且每组得s值可以不同）,问有多少种不同得分法?解题思路:这种问题就是要求组中分到得元素不能少某个确定值,各组分到得不就是至少为一个了。对于这样得题,我们就首先将各组都填满,即各组就填上对应得确定值s那么多个,这样就满足了题目中要求得最起码得条件,之后我们再分剩下得球。这样这个问题就转变为上面我们提到得变形（一)得问题了,我们也就可以用插板法来解决。【例3】1个相同得球放入编号为1、2、得盒子内,盒内球数不少于编号数,有几种不同得放法?解析:编号1:至少1个，符合要求。编号2:至少2个：需预先添加1个球,则总数-编号3：至少3个,需预先添加个,才能满足条件,后面添加一个,则总数-2则球总数1-1-2=2个放进3个盒子里所以C(11，2)=55（种)【例】0 个学生中,男女生各有5 人,选4 人参加数学竞赛。(1)至少有一名女生得选法种数为_。(2)、 两人中最多只有一人参加得选法种数为_解法1:0 名中选 名代表得选法得种类:C10, 排除名参赛全就是男生:C4 (排除法)104 -C54=205解法2:选1女生时,选个女生时,选、4个女生时得选法,分别相加（21年国考真题)某单位订阅了30份学习材料发放给3个部门,每个部门至少发放9份材料。问一共有多少种不同得发放方法？() A、 B、9 C、 、12 解析：每个部门先放8个,后面就至少放一个,三个部门则要先放83=24份，还剩下3-24=份来放入这三个部门,且每个部门至少发放1份，则(5,2)10插空法插空法就就是对于解决某几个元素要求不相邻得问题时,先将其她元素排好,再将所指定得不相邻得元素插入它们得间隙或两端位置。首要特点就就是不相邻。下面举例说明。一、数字问题【例】把，2，3,4,5组成没有重复数字且数字1,不相邻得五位数,则所有不同排法有多少种?解析:本题直接解答较为麻烦,因为可先将3,4,5三个元素排定,共有种排法,然后再将1，2插入四个空位共有种排法,故由乘法原理得,所有不同得五位数有二、 节目单问题【例】在一张节目单中原有六个节目,若保持这些节目得相对顺序不变,再添加进去三个节目,则所有不同得添加方法共有多少种？解析：-o- - -o o - o六个节目算上前后共有七个空位,那么加上得第一个节目则有种方法；此时有七个节目,再用第二个节目去插八个空位有种方法;此时有八个节目,用最后一个节目去插九个空位有种方法。由乘法原理得，所有不同得添加方法为：。三、关灯问题【例】一条马路上有编号1，2,3,4,5,6,7,得九盏路灯,为了节约用电,可以把其中得三盏灯关掉,但不能同时关掉相邻两盏或三盏,则所有不同得关灯方法有多少种？解析:如果直接解答须分类讨论,故可把六盏亮着得灯瞧作六个元素,然后用不亮得三盏灯去插七个空位(用不亮得盏灯去插剩下亮得6盏灯空位,就有个空位）共有种方法,因此所有不同得关灯方法为种。四、 停车问题【例】停车场划出一排12个停车位置,今有8辆车需要停放,要求空位置连在一起，不同得停车方法有多少种？解析:先排好8辆车有种方法，要求空位置连在一起（剩下4个空位在一起,来插入辆车,有9个空位可以插)，将空位置插入其中有种方法。所以共有种方法。五、 座位问题【例】3个人坐在一排8个椅子上,若每个人左右两边都有空位,则坐法得种类有多少种?解法:先拿出5个椅子排成一排，在5个椅子中间出现个空,再让3个人每人带一把椅子去插空,于就是有种。捆绑法解答:根据题目要求,则其中一个盒子必须得放2个,其她每个盒子放1个球,所以从6个球中挑出个球瞧成一个整体,则有,这个整体与剩下4个球放入5个盒子里,则有。方法就是排列组合中得解题方法之插板法 一、基础理论: 插板就是一个无形得东西即板子,它不能代表一个元素,它区别于插空法。插板法就是用于解决“相同元素”分组问题。判断插板法得题目主要瞧题干中得两个词语:相同元素至少为1,如果有这样两个词语一般此题就可以直接插板进行解题。 引例说明:春节前单位慰问困难职工,将10份相同得慰问品分给6名职工，每名职工至少要分得1份慰问品,分配方法共有：A、84种B、126种C、1种D、22种【分析】此题第一眼给人得感觉就是能用列举法进行分类解题,但就是细一思考分类得情况太多了,不易计算，因为想用插板法解题一般就是分两类或三类。而插板法就可以使这种为题迎刃而解。利用无形得板子把其分割开来。【解析】“10份慰问品相同且每人至少得1份”,满足插板法得两个前提相同元素至少为1，故可直接使用插板法。将份慰问品依次排成一条直线,我们用插板得形式把慰问品分给6名职工,中间形成个空,插上第1个板子,则第一个板子之前得分给第一名职工,在后面又插了一个板子，表示第个板子与第2个板子之间得分给第二名职工,依次类推,因为要分给个人,所以要插5个板子，第5个板子之后得分给第六名职工,所以只要板子固定了,那么每名职工分几份慰问品就固定了。 所以10分慰问品中间形成了9个空；分给6个人,插入个板;共有=126种分配方法。 注：估计有得同学会问，为什么第一个慰问品之前得位置与最后一个慰问品之后得位置不能放板子。其实原因在于“每名员工至少分1份慰问品”，如果在第一个慰问品之前得位置放板子那么第一名职工就一份分不到了，如果在最后一个慰问品之后得位置放板子那么最后一名职工就一份分不到了。二、真题举例: 例、假设x、y、就是三个非零自然数，且有xy+z=36,则共有多少组满足条件得解? 、700B、65C、630、55【分析】此题可以瞧做就是36块糖排成一排,即元素相同;由于x、y、z就是非零自然数，即至少为1,问题:x+y+z36,顺便瞧成3个人来分这6块糖。满足插板法应用条件。 【解析】根据题意,36块糖内部形成35个空位，分给三个人,需要插两个板子,故有=595种,而一种分法对应着一组解,如x=1，=，z=3,就就是一组解。共有595组解。因此,选D。 例2、将1本没有区别得图书分到编号为1、2、3得图书馆,要求每个图书馆分得 图书数量不小于其编号数,问共有多少种不同得分法?() 、12B、15C、0D、5 【分析】根据题意，“10本没有区别得图书”即相同元素,“要求每个图书馆分得 图书数量不小于其编号数“即1号图书馆至少分1本,2号图书馆至少分两本,3号图书馆至少分3本,分析完题意之后发现似乎不满足插板法得前提条件至少为，类似得这种题目我们只需要适当变形就可利用插板法解题。【解析】1号图书馆至少分1本,已经满足至少为,不用变形。而2号图书馆至少分两本,所以可从10本中取出一本先给2号图书馆。而3号图书馆至少分3本,可以从10本中取出两本书给3号图书馆,所以在给出一本与两本，那么还剩下7本,现在号,2号，3号图书馆至少在发放一本书就可以满足了,那么此时就可以用插板法解题。 所以答案就是=1小结:题目中一般有相同元素,至少为什么,此题都可用插板法解题,所以大家要不断熟悉插板法得应用。 三、插板法与列举法得对比例3、10个名额分配到八个班，每班至少一个名额，问有多少种不同得分配方法? A、种、种、种D、42种【答案】B 【列举法】先每个班级分一个名额,然后剩下两个名额,如果两个名额分到一个班级里面则有,如果两个名额分到两个班级里面则有种分法,则共有828=36、 【插板法】0个名额个空，插入7个板,共有种分配方法。 例4、某单位订阅了30份学习材料发放给3个部门,每个部门至少发放份材料。问一共有多少种不同得发放方法？()A、C、10D、12【答案】C 【列举法】每个部门得材料数分布情况不同得分法种数 (9,9,12)3种 (9,10,1)种 (10,10,1）1种 所以共有3+6+1=0种。 【插板法】个部门每个部门先发8份,让其满足插板法,2083=,计算:。小结：通过例与例来瞧,列举法可以叫做排列组合得通法,但就是遇到个别得题目必要时也要用插板法。