隔板法在排列组合中的应用

在排列组合中，通常使用划分方法来解决将无法区分的球装载到可区分的盒子中以找到装载方法的数量的问题。例1。求方程X Y Z=10的正整数解的个数。分析将10个球排成一行，在球之间形成9个间隙，在间隙中插入两个隔板(每个间隙中最多插入一个隔板)，并且由隔板划分的左、中、右部分中的球的数量分别指定为X、Y和Z的值(如下图所示)。然后，在划分方法和解的数量之间建立一对一的对立关系，因此解的数量是C92=36(件)。在用隔板法解决问题时，在确定球的数量和如何插入隔板方面已经形成了一些技巧。下面是一个例子。技能1:用隔板法增加球的数量。例2。求方程X Y Z=10的非负整数解的个数。分析请注意，X、Y和Z可以为零，因此无法建立上述问题的解决方案中“每个空白空间最多插入一个隔板”的限制。我该怎么办？只要加三个球，给x，y和z各一个球。这样，原来的问题就转化为寻找X Y Z=13的正整数解的个数，所以解的个数是C122=66。注释在本例中，通过添加球的数量，该问题被转化为示例1中的典型划分方法问题。技能2:用隔板法减少球的数量：例3。将20个相同的球分别放入编号为1、2、3和4的四个盒子中。要求每个盒子里的球的数量不小于它的数量，并计算球的总数。解决方案1:首先，将0、1、2、3个球分别放入编号为1、2、3、4的四个盒子中，剩下14个球。有一种方法。然后把剩下的球分成4组，每组至少一个。从实施例1已知的方法是C133=286(种)。解决方案2:第一步是将1、2、3、4个球分别放入编号为1、2、3、4的四个盒子中，留下10个球。有一种方法。在第二步中，剩下的10个相同的球被放入编号为1、2、3和4的盒子中。实施例2中已知的方法是C133=286(物种)。评论两种方法都可以减少球的数量，从而将问题转化为示例1和2中的典型问题。技能3:用隔板法依次插入。为了宣传党的十六大精神，一个文艺团体组织了基层宣传和演出。节目表中原本有四个歌舞节目。如果这些程序的相对顺序保持不变，再增加两个草图程序，有多少种不同的排列方式？分析这两个草图程序分别是A和B。首先安排一个节目。根据节目A前后的歌舞节目数量，方法的数量相当于把四个球分成两堆。从实施例2中，C51方法是已知的。完成此步骤后，将有五个程序。考虑到要添加的B程序前后的程序数量，有C61方法。因此，根据逐步计数原理，共有C51* C61(种)。评论为了巧妙地解决这个问题，本主题中要插入的两个分区被一个接一个地插入。要解决排列组合问题，首先我们必须仔细检查这个问题，弄清楚它是属于排列组合，还是排列组合的混合问题。其次，要把握问题的本质特征，灵活运用基本原理和公式进行分析，注意一些策略和方法。这里有一些解决问题的常用方法和策略。有几种相对特殊的方法来解决排列组合问题。下面的例子一一掌握：一、相邻问题绑定法和非相邻问题插值法对于一些元件不相邻的布置问题，可以先布置其他元件，然后将不相邻的元件插入布置的元件和两端的间隙之间。例1如果一个节目表上原来的三个节目的相对顺序保持不变，增加两个新节目，有多少种排列？a20 b . 12 c . 6d . 4答案 a。首先，问题中的三个程序是固定的，有四个空格。因此，当一两个一般来说，同一个元素的分配问题得到了解决，对划分元素的限制非常弱(一般只有要求不等于零)，只需要划分的份额。例2当20台计算机被分配到18个村庄，每个村庄至少需要一台计算机时，有多少种分配方法？公元前190年至公元前171年至公元153年答案 b。分析本主题的思想是插入板：将17块板随机插入到C(20台计算机中形成的19个空间，从而将它们分成18个部分，因此总共有：C(19，17)=C (19，2)=171种。三、特殊位置和特殊元素优先法限制排列和组合问题中的特殊元素或特殊位置是首选。例2六名运动员中有四名被选中参加4100米接力赛。有多少种比赛方案是A不参加第一和第四棒的？公元前120年，公元前240年，公元180年答案 b。分析方法1:特殊位置优先方法：首先填充第一个杆，第一个杆有5个元素可供选择，然后第四个杆有4个元素可供选择；那么第二个小节有4个元素可供选择，第三个小节有3个元素可供选择。有5443=240种。方法2:特殊元素优先方法：首先考虑元素a的位置在第一类中，有A(5，4)=120种排球方法中的一种不参加比赛；在第二类中，只有两个位置可供选择，所以有两种排球方法。剩下的5个人占据3个位置，A(5，3)=60种占据方法，因此有260=120个方案。因此，有120，120=240个竞争方案。四、逆向思维方法对于更复杂的排列组合问题，我们必须从前面直接学习间接方法。取出一个立方体的8个顶点中的4个，可以形成多少个四面体？公元前70年，64年，61年，58年【答案】d。分析问题的方法数=任意选择的四个点的组合数-共面四个点的方法数，共C (8，4)-12=70-12=58。V.分类对有约束的排列组合问题的解决，应根据要素的性质进行分类，按事件的连续过程逐步进行，保证每一步的独立性，达到一个明确的分类标准，逐级清晰，不重不漏。例3五个人排成一行，其中A不在行首，B不在行尾。不同的行是甲120种乙96种