高中数学论文：排列组合中两个分配问题的解法和应用.doc

排列组合中两个分配问题的解法和应用 在排列和组合问题中常有分配问题，此类问题常因分配的物品种类是否相同，分配的物品数量是否平均，分配的物品接受对象是否有序等各种因素使得此类问题显得非常灵活，有时也显得比较难，比如分配中的保底分配和重复现象。本文就这两个问题作一个探讨。引例：有4件奖品，要求全部奖给3个学生，且每人至少一件。问题（1）：若4件奖品相同，则有多少种不同的分配方法？问题（2）：若4件奖品各不相同，则有多少种不同的分配方法？分析：问题（1）：奖品分定后的结果是：其中的一人有2件奖品，另两人各有一件奖品，故可如此考虑，先每人发一件奖品，因奖品相同所以仅一个方法，然后再把剩余的一件分给三个人中的一个，根据分步计数原理有n=种不同分法。 问题（2）解法一：按照上述思路，在每人发一件时因分配的物品不同有种不同方法，再把剩余的一件分给3个人中的一个有种方法，根据分步计数原理得不同的分配方法有种。 问题（2）解法二：奖品分配完毕将有2件成组，另2件各成一组共3组分给3个同学，根据分步计数原理得共有不同的分配方法种。 此时产生一个问题，同一个问题在两个不同的思路之下出现两个不同的答案。仔细探究原来解法一的结果中产生了重复，比如三个同学分别为甲、乙、丙，奖品为a、b、c、d，其中甲同学是分得2件奖品的同学，现先在发奖品的时候甲分得a，乙分得b，丙分得c，剩余的d在这一步恰好分给甲，如此最后甲得a、d，乙得b，丙得c；另外在发奖品的时候甲分得d，乙分得b，丙分得c，剩余的a在这一步恰好分给甲,如此最后也是甲得a、d，乙得b，丙得c。这两个过程对解法一而言是不同的结果，但事实上最后结果是一样的，原因在于上述分步分配的做法人为地把两个无序的结果产生了顺序，故需除以两件物品因先后分配而产生的种排列顺序以消除重复才能得正确结果。问题（1）推广：问题（1）的分配类型称为“相同物品的保底分配问题”，上述解法在碰到物品数和人数增多时直接分配将出现很多的情况，问题将很难解决。例1、 有100件相同的奖品，分给20个学生，要求将奖品全部分完，而且每人至少一件，问共有多少种不同的分配方法？分析：此时每人发一件后剩余的80件奖品在20个学生中出现的情况很多，再也不可能进行正面直接解决了，此时我们可引进挡板法，即将100件奖品排成一列产生99个间隙（不包括两端），在这99个间隙中选19个插进19个挡板把这100个奖品分成20份分给20个学生共有种不同的分配方法。对上述问题所采用的方法我们称之为挡板法，这种挡板法能非常方便地解决相同物品的保底分配问题。问题（1）推广的应用： 例2：不定方程的正整数解有多少组？解：将“7”分成7个1，每个“1”看成一个元素，、看成四个不同的盒子，现将7个1排成一列如图“1 1 1 1 1 1 1”，此时产生8个间隙（包括两端），、表示四个挡板插入其中的间隙之中，最左侧间隙必不插挡板，最右侧间隙必插挡板，而且规定：每相邻两个挡板之间的数字之和是右侧挡板对应的的值，于是不定方程的正整数解与用四个挡板插入的方法之间建立起一一对应的关系，则上述问题就转化为相同物品的保底分配问题，于是不定方程的正整数解共有组。例3：有10个相同的小球及分别标有“1”、“2”、“3”号标签的盒子，现要将这10个小球放进这3个盒子，要求每个盒子放进的小球数不小于相应的盒子标签，问共有多少种不同的放法？分析：此例的问题在于保底的小球数不再是相等的一个，因此解决此问题的关键在于如何把保底数转化为相等且都是一个，因为小球是相同的，故只要事先在“1”号盒子中不放小球。“2”号盒子中放进1个小球，“3”号盒子中放进2个小球（此时已用了3个小球），然后再放其他的小球，此时问题已转化为7个相同的小球放进3个盒子，每个盒子至少一个，用挡板法解得共有种不同放法。问题（2）推广：问题（2）中用法一求解时因前后两次分配物品时人为地对无序分配问题产生先后顺序导致重复的产生，其实产生重复的原因还有一种，比如分组过程中遇到若干个组组中的元素相同时，此时会因人为地对无组别问题产生组别而导致重复的产生。例4、分别标有1、2、3、4、5、6、7、8、9、10数字的10个小球分成3组，其中的两个组各4个小球，另一个组2个小球，问不同的分组方法有几种？分析：若答案为，则因其中有两组的小球数都是4个而产生了重复，比如用选的一组是1、2、3、4号球，用选的一组是5、6、7、8号球，最后选的一组是9、10号球为情况之一；另外用选的一组是5、6、7、8号球，用选的一组是1、2、3、4号球，最后选的一组是9、10号球又为情况之一，在上述所给的答案是两种不同的分组方法，但其实这只是一种分组方法，最后都是1、2、3、4号球成组，5、6、7、8号球成组，9、10号球成组，重复产生的原因是其中有两个组的元素个数相同，可以互相置换而产生重复现象。上述答案相当于给无组别的分组问题产生了人为的组别而导致重复的产生，要消除重复需将所得结果再除以元素相同的组数的全排列即，故正确答案为种。这类问题称为“平均分配问题”。针对上述“平均分配问题”中重复现象产生的原因，要消除重复现象的附加条件有两种。一种是组中有部分元素是确定的，比如上述例4中要求1、2号球必须同组，则分两类：第一类：1、2号球同在其中一个含4个元素的组中，得不同的分组方法有：种；第二类：1、2号球同在其中含2个元素的组中，得不同的分组方法有：种；根据分类计数原理得共有不同的分组方法：种。在第一类中因两个含4个元素的组中有一个组的两个元素即1、2号球是确定的，“平均分配”过程中的重复也因此而消失（因为1、2号球是确定元素，不会被另一个含4个元素的组置换而产生重复现象）；而第二类中因两个含4个元素的组仍是可以互相置换的，所以重复现象仍然存在，故仍需除以以消除重复。消除重复的另一种附加条件是分组后把物品再分给不同的对象，比如上述例4中把分好的三组小球再分给甲、乙、丙3个学生，则在上述分析的基础上再乘以即得不同的分法有种。但若考虑先用取得两个小球再用分给三个学生中的一个，再用和各取出4个小球依次分给另两个学生，然后按分步计数原理得不同的分配方法共有种，此时因分出的小球是依次给三个学生，他们依次拿走小球后丙用分得9、10号球，甲用分得1、2、3、4号球，乙用分得5、6、7、8号球和丙用分得9、10号球，甲用分得5、6、7、8号球，乙用分得1、2、3、4号球，是两种不同的结果，因接受物品的对象不同“平均分配”过程中的重复现象也随之而消失。问题（2）推广的应用： 例5、有包括甲、乙两个强队的8个球队，现分成两组，每组4个球队，求甲、乙两个强队分在同一组的概率。解：此为等可能事件概率，其中，故所求概率为此例中重复现象在求n的过程中因两个组的元素相同（平均分配）而产生了，而在求m的过程中因一个组的部分元素是确定（不可置换）而消除了，在上述分析之下应该能比较容易理解了。小结：排列组合问题是高中数学的重要内容，也是历年高考必考的知识点之一，同时它又具有与实际联系密切，应用性、趣