隔板法在排列组合中应用.doc

隔板法在排列组合中的应用在排列组合中,对于将不可分辨的球装入到可以分辨的盒子中而求装入方法数的问题,常用隔板法。+Y+Z=10的正整数解的个数。,分析,将10个球排成一排,球与球之间形成9个空隙,将两个隔板插入这些空隙中(每空至多插一块隔板),规定由隔板分成的左、中、右三部分的球数分别为x、y、z之值(如下图)。则隔法与解的个数之2间建立了一一对立关系,故解的个数为C=36(个)。实际运用隔板法9解题时,在确定球数、如何插隔板等问题上形成了一些技巧。下面举例说明。技巧一:添加球数用隔板法。????????????+Y+Z=10的非负整数解的个数。,分析,注意到x、y、z可以为零,故上题解法中的限定“每空至多插一块隔板”就不成立了,怎么办呢,只要添加三个球,给x、y、z各一个球。这样原问题就转化为求X+Y+Z=13的正整数解的个数了,故解的2个数为C=66(个)。12,点评,本例通过添加球数,将问题转化为如例1中的典型隔板法问题。技巧二:减少球数用隔板法:,2,3,4的四个盒子中,要求每个盒子中的球数不少于它的编号数,求放法总数。解法1:先在编号1,2,3,4的四个盒子内分别放0,1,2,3个球,剩下14个球,有1种方法;再把剩下的球分成4组,每组至少1个,3由例1知方法有C=286(种)。13解法2:第一步先在编号1,2,3,4的四个盒子内分别放1,2,3,4个球,剩下10个球,有1种方法;第二步把剩下的10个相同的球放入3编号为1,2,3,4的盒子里,由例2知方法有C=286(种)。13,点评,两种解法均通过减少球数将问题转化为例1、例2中的典型问题。技巧三:先后插入用隔板法。,一文艺团体下基层宣传演出,准备的节目表中原有4个歌舞节目,如果保持这些节目的相对顺序不变,拟再添两个小品节目,则不同的排列方法有多少种,,分析,记两个小品节目分别为A、B。先排A节目。根据A节目前后的歌舞节1目数目考虑方法数,相当于把4个球分成两堆,由例2知有C种方法。5这一步完成后就有5个节目了。再考虑需加入的B节目前后的节目数,111同理知有C种方法。故由分步计数原理知,方法共有C*C(种)。656,点评,对本题所需插入的两个隔板采取先后依次插入的方法,使问题得到巧妙解决。解答排列组合问题,首先必须认真审题,明确是属于排列问题还是组合问题,或者属于排列与组合的混合问题,其次要抓住问题的本质特征,灵活运用基本原理和公式进行分析,同时还要注意讲究一些策略和方法技巧。下面介绍几种常用的解题方法和策略。解决排列组合问题有几种相对比较特殊的方法。下面通过例题逐个掌握:一、相邻问题---捆绑法不邻问题---插空法对于某几个元素不相邻的排列问题,可先将其他元素排好,再将不相邻元素在已排好的元素之间及两端空隙中插入即可。【例题1】一张节目表上原有3个节目,如果保持这3个节目的相对顺序不变,再添进去2个新节目,有多少种安排方法?【答案】A。【解析】首先,从题中之3个节目固定,固有四个空。所以一、两个新节目相邻的的时候:把它们捆在一起,看成一个节目,此时注意:捆在一起的这两个节目本身也有顺序,所以有:C(4,1)×2=4×2=8种方法。二、两个节目不相邻的时候:此时