“隔板法”解决排列组合问题(课件)

巧用隔板法解排列组合题徐帮利 临沂市第二中学解决排列组合问题的方法很多,从解题形式来看,可分为直接法和间接法两种;根据具体问题情景又有：相邻问题“捆绑法”;不相邻问题“插空法”;特殊定位“优限法”(优先排列受限制的位置或元素);同元问题“隔板法”等.这里我们重点看一下“隔板法”.“隔板法”适用于相同元素的分配问题,如投球进盒、名额或指标的分配、部分不定方程的整数解的组数等,解决时通常设计一个问题情景,构造一个隔板模型,将复杂的问题简单化,抽象的问题具体化,从而实现解题的目的.下举例述之.例1.某运输公司有7个车队,每个车队的车多于4辆,现从这7个车队中抽出10辆车,且每个车队至少抽1辆,组成一个运输队,则不同的抽法有（ ）种.A.84B.120C.63D.301解析:此题若使用其它方法,则需要分类,都比较麻烦,若用“隔板法”,则就轻而易举了.首先将10辆车排好,这样形成9个空,从这9个空中选6个,插入隔板,即将这10辆车分成7份,每一种插法对应一种抽法,故共有6984C =种不同的抽法.所以选A.例2.方程123410x x x x +++=共有多少组正整数解?解析:此题乍看上去,好象思路不太好找,那就只好列举了(麻烦啊！).殊不知,巧构隔板模型,即可化繁为简.将10个完全相同的小球排成一列,形成9个空,从中选3个,插入隔板,将球分成4份,每一种插法所得4份球的各份的数目,分别对应1234x x x x 、、、,即为原方程的一组正整数解.故原方程组共有3984C =组不同的整数解.例3．将10个相同的小球放入编号为1,2,3的三个盒子中,每个盒子中所放的球数不少于其编号数,问不同的放法有多少种?解析:由于条件要求每个盒子中所放的球数不少于其编号数,我们不妨先“找平了”,即先在第1,2,3个盒中各放0,1,2个球.问题即转化为求:将7个相同的小球放入编号为1,2,3的三个盒子中,每个盒中至少1个球的不同放法.将7个小球排成一排,形成6个空,从中选2个,插入隔板,把球分成三组,放入对应的盒子里,每一种插法,对应一种放法,故共有2615C =种不同的放法.强化训练:1.将10本完全相同的书,分给4名同学,每人至少一本,共有多少种不同的分法?答案: 3984C=种.2.方程1220100x x x++⋅⋅⋅+=共有多少组正整数解？答案:1999C组.。

隔板法在解排列组合问题中的应用隔板法又称隔墙法、插板法是处理名额分配、相同物体的分配等排列组合问题的重要方法，本文将将通过例题将这种方法作以介绍，供同学们学习时参考.一、将n 件相同物品（或名额）分给m 个人（或位置），允许若干个人（或位置）为空的问题例1将20个大小形状完全相同的小球放入3个不同的盒子，允许有盒子为空，但球必须放完，有多少种不同的方法？分析：本题中的小球大小形状完全相同，故这些小球没有区别，问题等价于将小球分成三组，允许有若干组无元素，用隔板法.解析：将20个小球分成三组需要两块隔板，将20个小球及两块隔板排成一排，两块隔板将小球分成三块，从左到右看成三个盒子应放的球数，每一种隔板与球的排法对应一种分法.将20个小球和2块隔板排成一排有22个位置，先从这22个位置中取出两个位置放隔板，因隔板无差别，故隔板之间无序，是组合问题，故隔板有222C 种不同的放法，再将小球放入其他位置，由于小球与隔板都无差别，故小球之间无序，只有1种放法，根据分步计数原理，共有222C ×1=231种不同的方法.点评：对n 件相同物品（或名额）分给m 个人（或位置），允许若干个人（或位置）为空的问题,可以看成将这n 件物品分成m 组，允许若干组为空的问题.将n 件物品分成m 组，需要1m -块隔板，将这n 件物品和1m -块隔板排成一排，占1n m +-位置，从这1n m +-个位置中选1m -个位置放隔板，因隔板无差别，故隔板之间无序，是组合问题，故隔板有11m n m C -+-种不同的方法，再将物品放入其余位置，因物品相同无差别，故物品之间无顺序，是组合问题，只有1种放法，根据分步计数原理，共有11m n m C -+-×1=11m n m C -+-种排法,因1m -块隔板将n 件相同物品分成m 块，从左到右可以看成每人所得的物品数，每一种隔板与物品的排法对应于一种分法，故有11m n m C -+-种分法.二、将n 件相同物品（或名额）分给m 个人（或位置），每人（或位置）必须有物品问题例2将20个优秀学生名额分给18个班，每班至少1个名额，有多少种不同的分配方法？分析：本题是名额分配问题，用隔板法.解析：将20个名额分配给18个班，每班至少1个名额，相当于将20个相同的小球分成18组，每组至少1个，将20个相同的小球分成18组，需要17块隔板，先将20个小球排成一排，因小球相同，故小球之间无顺序，是组合，只有1种排法，再在20个小球之间的19个空档中，选取17个位置放隔板，因隔板无差别，故隔板之间无序，是组合问题，故隔板有1719C 种不同的放法，根据分步计数原理，共有1719C 种不同的方法，因17块隔板将20个小球分成18组，从左到右可以看成每班所得的名额数，每一种隔板与小球的排法对应于一种分法，故有11m n m C -+-种分法.点评：：对n 件相同物品（或名额）分给m 个人（或位置），每个人（或位置）必须有物品问题,可以看成将这n 件物品分成m 组，每组不空的问题.将n 件物品分成m 组，需要1m -块隔板，将这n 件物品排成一排，因物品无差别，故物品之间无顺序，是组合问题，只有1种排法，再在这n 件物品之间的1n -空档中选取1m -个位置放隔板，占1n m +-位置，从这1n m +-个位置中选1m -个位置放隔板，因隔板无差别，故隔板之间无序，是组合问题，故隔板有11m n C --种不同的放法，根据分步计数原理，共有1×11m n C --=11m n C --种不同排法,因1m -块隔板将n 件相同物品分成m 块，从左到右可以看成每人所得的物品数，每一种隔板与物品的排法对应于一种分法，故有11m n C --种分法.对相同物品分配问题，注意某若干组能否为空，能为空和不能为不空，方法不同，要体会和掌握.。

隔板法解决排列组合问题Document number：NOCG-YUNOO-BUYTT-UU986-1986UT“隔板法”解决排列组合问题（高二、高三）排列组合计数问题，背景各异，方法灵活，能力要求高，对于相同元素有序分组问题，采用“隔板法”可起到简化解题的功效。

对于不同元素只涉及名额分配问题也可以借助隔板法来求解,下面通过典型例子加以解决。

例1、（1）12个相同的小球放入编号为1，2，3，4的盒子中，问每个盒子中至少有一个小球的不同放法有多少种（2）12个相同的小球放入编号为1，2，3，4的盒子中，问不同放法有多少种（3）12个相同的小球放入编号为1，2，3，4的盒子中要求每个盒子中，要求每个盒子中的小球个数不小于其编号数，问不同的方法有多少种解：（1）将12个小球排成一排，中间有11个间隔，在这11个间隔中选出3个，放上“隔板”，若把“1”看成隔板，则如图00隔板将一排球分成四块，从左到右可以看成四个盒子放入的球数，即上图中1，2，3，4四个盒子相应放入2个，4个，4个，2个小球，这样每一种隔板的插法，就对应了球的一种放法，即每一种从11个间隔中选出3个间隔的组合对应于一种放法，所以不同的放法有311C=165种。

（2）法1：（分类）①装入一个盒子有144C=种；②装入两个盒子，即12个相同的小球装入两个不同的盒子，每盒至少装一个有2141166C C=种;③装入三个盒子，即12个相同的小球装入三个不同的盒子，每盒至少装一个有32411C C=220种;④装入四个盒子，即12个相同的小球装入四个不同的盒子，每盒至少装一个有311165C=种;由加法原理得共有4+66+220+165=455种。

法2：先给每个小盒装入一个球，题目中给定的12个小球任意装，即16个小球装入4个不同的盒子，每盒至少装一个的装法有315455C =种。

（3）法1：先给每个盒子装上与其编号数相同的小球，还剩2个小球，则这两个小球可以装在1个盒子或两个盒子，共有124410C C +=种。

组合数学隔板法
隔板法
隔板法是组合数学⾥⾯⼀个⾮常重要的解决⼀类问题的⽅法，⼀定要掌握。

⼀类问题：
把 n 个元素分成 b 组的⽅案数，n 个元素相同。

这类问题我们常⽤隔板法解决，即在 n 个元素之间插⼊ b-1 个板，把他们分成 b 组。

分两种：
1、如果分成的每个组都必须有元素的话，那么答案就是 C(n-1,b-1) 。

2、如果组允许为空，那么就不是上⾯那个答案了。

我们先添加 b-1 个虚拟元素进序列中，这样序列就有 n+b-1 个元素了。

答案就是把这 n+b-1 个元素中插⼊ b-1 个隔板（即分成 b 组且不允许组为空）的⽅案数。

（这样就保证最⼤的组中含有 n 个元素，最⼩的为1）这⾥可能有些难理解，画画图，⾃⾏体会。

以上就是⼀些⼊门⼩结（待填坑）。

加油加油加油fighting fighting fighting。

“隔板法”解决排列组合问题排列组合计数问题，背景各异，方法灵活，能力要求高，对于相同元素有序分组问题，采用“隔板法”可起到简化解题的功效。

对于不同元素只涉及名额分配问题也可以借助隔板法来求解,下面通过典型例子加以解决。

所谓隔板法，就是把隔板当成元素，再从元素里选隔板就行例1、（1）12 个相同的小球放入编号为1，2，3，4 的盒子中，问不同放法有多少种？（2）12 个相同的小球放入编号为1，2，3，4 的盒子中，问每个盒子中至少有一个小球的不同放法有多少种？（3）12 个相同的小球放入编号为1，2，3，4的盒子中要求每个盒子中，要求每个盒子中的小球个数不小于其编号数，问不同的方法有多少种？解：（1）本题需要3个隔板，把3个隔板当成3个元素，共15个元素，再从15个元素里选取3个隔板，共有C 153 =455 种（2）首先一个盒子放一小球，还剩8个小球，把8个小球放4个盒子需3个隔板，把3个隔板当成3个元素共11个元素，最后从11个元素里选3个隔板就行了，共有C113 =165 种。

（3）先给每个盒子装上与其编号数相同的小球，还剩2 个小球，2个小球装在4个盒子里需3个隔板，3个隔板看成3个元素，共5个元素，最后从5个元素里选出3个隔板就行了，共有C53=10种913111例 2、（ 1）方程 x 1x 2 x 3 x 4 10 的正整数解有多少组？(2) 方程 x 1x 2 x 3 x 4 10 的非负整数解有多少组？（ 3）方程2x 1 x 2 x 3x 10 3 的非负整数整数解有多少组？解：（ 1）转化为 10 个相同的小球装入4 个不同的盒子， 每盒至少装一个， 有 C 384 种，所以该方程有 84 组正整数解。

（ 2）转化为 10 个相同的小球装入 4 个不同的盒子， 可以有空盒， 先给每个小盒装一个，进而转化为 14 个相同的小球装入4 个不同的盒子， 每盒至少装一个， 有 C3286 种， 所以该方程有 286 组非负整数整数解。

排列组合——隔板法隔板法就是在n 个元素间的（n-1）个空中插入 若干个（b ）个板，可以把n 个元素分成（b+1）组的方法.应用隔板法必须满足三个条件：（1） 这n 个元素必须互不相异（2） 所分成的每一组至少分得一个元素 (3) 分成的组别彼此相异.【例题解析】例1、把10个相同的小球放入3个不同的箱子，每个箱子至少一个，问有几种情况？（3629=C ）例2、高二年级8个班级协商组成年级篮球队，共需10名队员，每个班级至少要出一名，有多少种不同的 组成方式？分析：将10名队员理解成10个球，排成一列，共形成9个空隙，设想有7个隔板，将排成一列的10个球隔成8段，注意：任意两块隔板不能相邻！故为3679=C 种. 附加：从5个学校选出8名学生组成代表团，每校至少有一人的选法种数是多少？分析：问题转化为将8个学生分成5组，每组至少一人，故有3547=C 种选法.例3、求方程X+Y+Z+W=23的正整数解的个数.分析：我们设想有23个无区别的球排成一列，共形成22个空，可以理解为有3块隔板，将排成一列的球隔成4段，共有1540322=C 个正整数解。

对某些不符合上述隔板法条件的一些问题可以通过一些技巧“转化”为符合条件的隔板问题.〖技巧一：添加球数用隔板法〗例4、求方程X+Y+Z+W=23的非负整数解的个数.分析：注意到x 、y 、z 、w 可以为零，故上题解法中的限定“每空至多插一块隔板”就不成立了，此时只要添加四个球，给x 、y 、z 、w 各一个球。

这样原问题就转化为求X+Y+Z+W=27的正整数解的个数了，故解的个数为2600326=C .例5、20个相同的球分给3个人，允许有人不取，但必须分完，有多少种分法？分析：问题转化为：20个相同的球分给1，2，3编号的盒子，允许有盒为空，但必须分完，有多少种分法？解析：添加3个球，给3个人每人一个，问题转化为：23个相同的球分给3个人，每人至少分一个球，且必须分完，有多少种分法？也就是23个球有22个空隙，2块隔板分成三部分，231222=C 种.评述：这个问题是典型的玻瑟——爱因斯坦（Bose-Einstein ）统计模型：要将k 个相同的球放入n 个不同的盒子,每盒所放球数不限,有多少种不同放法?〖技巧二：减少球数用隔板法〗例6： 将20个相同的小球放入编号分别为1，2，3，4的四个盒子中，要求每个盒子中的球数不少于它的编号数，求放法总数.分析：先在编号1，2，3，4的四个盒子内分别放0，1，2，3个球，剩下14个无区别的球,问题等价于将14个球放入4个编号为1,2,3,4的四个盒子里，每个盒子至少有一个球的问题.剩下14个无区别的球排成一列，共形成13个空，可以理解为有3块隔板，将排成一列的球隔成4段，每段至少1个，有286313=C 种.附加：20个不加区别的小球放入编号为1号、2号、3号的三个盒子里，要求每个盒内的球数不小于盒子的编号数，问有多少种放法？解析：先取出3个球，在编号1，2，3的三个盒子内分别放0，1，2个球。

组合数学-隔板法
这种问题的对象是对同以种物品 n 个完全相同，去放在 m 个不同的盒⼦⾥，问有多少种⽅法？
在这个问题中，还有两种形式的问法：
1 、盒⼦不可以为空
则答案就是 C(n-1, m-1)
2 、盒⼦可以为空
因为隔板法的前提条件是盒⼦不可以为空，所以，为了满⾜这个条件，我们先在每个盒⼦中放如⼀个⼩球，则现在总球为 m+n ,中间有m+n-1 个空隙，所以总的⽅案数是 C(m+n-1, m-1)
问题 2
有 n 个不同的元素，每个元素可以选多次，⼀共选 k 个元素，有多少种选法？例如 n = 3, k = 2 时有 6 种，(1, 1)(1, 2)(1, 3)(2, 2)(2, 3)(3, 3)分析：
设第 i 个元素选取 xi 个，则 x1 + x2 + …… + xn = k 个，问题就可以看成是将 k 放⼊ n 个不同的盒⼦中，盒⼦可以为空，问最终有多少⽅案，典型的隔板法， C(n+k-1, n-1) = C(n+k-1, k)。