|
在上一讲中，我们主要介绍了与顺序有关的计数问题排列（Permutations），这一讲的重点是介绍与顺序无关的计数问题组合（Combinatorics）。 所谓组合，指的是从互不相同的n个物品中，不必按照顺序取出r个。组合问题与顺序无关。 还是从简单的例子开始说起： 例1：开明小学要从学校六年级演讲兴趣小组的5位学生中选出2位代表学校参加全市的演讲比赛，请问会有几种组合方式？ 最简单的方法就是把五个同学用A、B、C、D、E来表示，看看有多少种可能性。接下来当然要用上枚举法，或者叫穷举法。枚举也是要讲究方法的，否则最后会变得一团糟。 因为最终是选出2个同学去参加演讲比赛，所以我通过在两个□里填字母来罗列所有的可能性。先是把A放在第一个□里，然后用B、C、D、E与A进行搭配；接着把B放在第一个□里，然后用A、C、D、E与B进行搭配；……以此类推。如下图所示： 这是所有的可能性：5×4＝20种，但我们发现，在这个问题里，AB的组合与BA的组合其实是一回事，因此，我们要去掉其中一半的组合可能性。 因此，此题正确完整的计算应该是：5×4÷2＝10种。这就是按照组合公式计算的数学含义： 例2：假如我们在订购披萨时，共有8种配料（凤尾鱼、大蒜、菠萝、香肠、意大利腊肠、蘑菇、橄榄和青椒）可供选择，如果恰好选择3种配料，共有多少种不同的选择方法？ 这个问题是让我们在8种配料里面选3种，那么我们有三次选择的机会：第一次，我们要在全部的8种配料里选择1种；第二次，我们要在剩下的7种配料里面选1种；第三次，我们要在第二次选剩下的6种配料里再选择一种。因此，我们就有8×7×6种配料组合的可能性。 但是问题来了，假如我们把这8种配料进行1~8编号，我们有可能出现第一次选1号配料，第二次选2号配料，第三次选3号配料；也可能出现第一次选2号配料，第二次选1号配料，第三次选3号配料；还有可能出现第一次选3号配料，第二次选2号配料，第三次选1号配料；……。也就是说，每选择的3种配料，都会出现重复，因为我们最终关注的是这3种配料的组合里面有哪3种配料，而不关心先选和后选的顺序问题。对于3种配料而言，就相当于有3×2×1＝6种可能性是重复计算的。这里，不熟悉排列问题的朋友可以用ABC三个字母尝试一下各种顺序的可能性，我就不展开了。因此，对于这个8选3的组合问题而言，最终的可能性就是：8×7×6÷6＝56种。 细心的读者朋友可能已经注意到，我特意没有将8×7×6的结果计算出来，因为最后的乘以6可以与后面的除以6进行抵消。这也是我经常和同学们提醒的：在计算过程中，先不要急着把每一部分的结果算出来，当整体的算式列出来以后，再观察是否有可以相互抵消的简便运算。 请同学们计算了一下：从5位学生中选出3位代表学校参加演讲比赛，请问会有几种组合方式；如果从8种配料里选择5种配料，共有多少种不同的选择方法？ 经过计算，同学们可以发现：从5位学生中选出3位代表学校参加演讲比赛的组合数量居然和从5位学生中选出2位代表学校参加演讲比赛的组合数量是相同的，都是10种（5×4×3÷6）；从8种配料里选择5种配料可能的选择方法居然也是与从8种配料里选择3种配料可能的选择方法相同的，都是56种（8×7×6×5×4÷120）。 这意味着什么意思呢？这就是在排列组合问题中常见的：在m个不同物品中选n个物品的组合可能性，与在m个不同物品中选m－n个物品的组合可能性是相同的，即： 但是，很多同学只知道这个是对的，并不明白为何是对的。虽然高年级同学明白如何通过代数推导证明这是对的，但我总觉得无法用通俗的语言来进行表达是一种缺憾。 其实道理很简单。以例1来说，我们从5个同学里面选2人去参加演讲比赛，从另外一个面来说，就意味着我们要从5个同学里面选3人不去参加演讲比赛，而选3人不去参加演讲比赛与选3人去参加演讲比赛，在数学方法上我们是完全相同的。这就用最简单的语言解释了前面所提到的：在m个不同物品中选n个物品的组合可能性，与在m个不同物品中选m－n个物品的组合可能性是相同的。也就是说，这其实就是同一个问题的两个面，或者说是两个角度而已。 例3：有一只小蜗牛，要从下面方格左下角的A点爬到右上角的B点，它只能往前或者往上爬，请问：小蜗牛从A点爬到B点有多少种路线？ 这个题目如果我们单纯地进行枚举的话，是一件非常麻烦的事情，而且缺乏一般性。当然，题目里的方格并不多，全部列举出来也花费不了非常多的时间。但是，就像我一直强调的那样，解数学题，最重要的不是为了那个答案，而是我们可以从题目本身学到什么。枚举法虽然有时也需要点技巧，但毕竟不是什么思想性很强的方法，不是我们应该提倡的。那么，这个问题应该如何思考呢？ 经过多次尝试和仔细观察，我们不难发现，由于题目要求小蜗牛只能向前或者向上，那么无论哪种方式，小蜗牛要达到终点，必须爬8次，其中5次向前（横向）和3次向上（纵向）。 这是一个非常关键的发现，于是问题就变为了在8次里面选5次向前或者在8次里面选3次向上的组合问题了。答案就是：（8×7×6×5×4）÷（5×4×3×2×1）＝（8×7×6×5×4）÷120＝56种；或者是，（8×7×6）÷（3×2×1）＝（8×7×6）÷6＝56种。 这个解答的扩展性就不是枚举法所能给予我们的了，我们可以一般性地扩展到更加复杂的方格图中去。如果我们深入学习下去就会知道，这个结论与著名的帕斯卡三角形（(Pascal’s Triangle，也叫贾宪三角或者杨辉三角）有关。后面会有专门的文章介绍帕斯卡三角形。 例4：数一数下图有几个三角形？ 同样，我们一个一个地数也是可以得到答案的，但显然比较糟糕，而且答案只是针对特殊问题，缺乏一般性。所以，在这个问题上，枚举法同样不是什么好方法。 经过仔细观察，我们可以发现，无论什么形状的三角形，都可以归结为图中的三个点和三条直线组成。在这个问题里，一共出现了12个点和7条直线。于是问题就进一步转化为从12个点里选3个点组成三角形或者从7条直线中选3条组成三角形的问题了。我们只要通过计算全部的可能性，然后减去不可能的情况，就能得到结果。 我们先来看“从12个点里选3个点组成三角形”这个角度。全部的可能性就是：（12×11×10）÷（3×2×1）＝220个。然后减去任意直线上的3个点组成三角形的可能性即可，这个也容易计算。问题麻烦的是，假如不是在一条直线上的点（见下图），似乎毫无规律可寻。在全部12选3的可能性中已经被计算在里面，但我们很难将其排除。这样，这个选点的角度就走不下去了。 再来看“从7条直线中选3条组成三角形”这个角度。先计算全部的可能性：（7×6×5）÷（3×2×1）＝35个。然后计算从大三角形三个角A、B、C所射出来的直线，从角A出来4条线，任何3条线都不可能组成一个三角形，因此可能性有：（4×3×2）÷（3×2×1）＝4个；从角B和角C分别出来3条线，每个角所对应的三条线都不可能组成一个三角形，因此可能性只有2×1＝2个。因此，最后的答案就是：35－4－2＝29个。这个思考问题的角度就具有很强的一般性了，可以推广到更加复杂的情况。 读者朋友们可以试试看，用这个思路数一数下面的图形有多少个矩形？提示一下，可以从矩形的四条边切入。
例5：求不定方程x＋y＋z＝20有多少组正整数解？ 善于枚举法的同学很快就能枚举出全部的可能性，即：1＋2＋3＋…＋18＝（1＋18）×18÷2＝171组。枚举的逻辑很简单，如图所示：
那么，假如我们仔细观察，能发现什么呢？如果我们把x、y、z所对应的数字看成是圈圈的话，那么问题是不是可以想象成20个圈圈中间的19个间隔中找2个位置插入“＋”呢？如图所示：
…… 这样，我们就把问题转化为在19个间隔中选两个间隔的组合问题了。因此，答案就是：（19×18）÷（2×1）＝171组。想明白了问题的关键所在，解答就变得非常之简单了。 例6：请问，诸如123或者579这种每个数位上的数字依次递增的三位数有多少个？ 解法1：这个问题假如没有学过任何的组合数学知识，最直接的方法就是枚举。 满足递增条件的三位数中，最小的是123。先保持百位和十位不变，个位发生变化，123到129一共有7个这样的三位数；然后考虑百位依旧不变，十位由2变为3，最小的是134，那么134到139有6个这样的三位数；……；百位不变，十位最大可以是8，那么这样的三位数只有1个，即189。这样，百位是1的递增三位数一共就有：7＋6＋5＋4＋3＋2＋1＝28个。 现在让百位发生变化，由1变为2，则最小的递增三位数是234。用上面的方法递推，很快我们就可以发现，百位为2的递增三位数一共有：6＋5＋4＋3＋2＋1＝21个。同理，百位为3的递增三位数个数为：5＋4＋3＋2＋1＝15个；百位为4的递增三位数个数为：4＋3＋2＋1＝10个；百位为5的递增三位数个数为：3＋2＋1＝6个；百位为6的递增三位数个数为：2＋1＝3个；百位为7的递增三位数个数为：1个。因此，符合递增条件的三位数个数就是：28＋21＋15＋10＋6＋3＋1＝84个。 解法2：那么，这个问题是否可以换个角度思考呢？当然！假如我们仔细观察，就可以发现两个重要的规律：一、在所有符合递增条件的三位数中，不存在0这个数字；二、所有符合递增条件的三位数中的数字，都是从1到9这九个数字中选出来的三个，并且没有重复。 有同学可能会说：这不是废话嘛，这么明显的规律大家都看到了！但恰恰就是这么显而易见的规律，才是这个问题的关键。没有数字0，选择的范围是1到9这9个数字。问题的本质于是变成了在这9个数字中选出3个来的组合问题，即:9×8×7÷3!＝84个。这个与我们枚举出来的答案完全一样，但非常之简单。 例7：请问，诸如321或者863这种每个数位上的数字依次递减的三位数有多少个？ 明白了上面一个问题的思想，我们就很容易得到这个问题的答案了。很多人会想当然地认为答案是一样的。其实不然，递减和递增最大的区别是0是可以存在的。于是，问题就变为了从0到9这10个数字中选出3个的组合问题了，即:10×9×8÷3!＝120个。 理解了递增和递减的情况，我们再来一点变化。 例8：请问，诸如7542103689或者3210456789这种每个数位上的数字先依次递减再依次递增的十位数有多少个？ 假如说前两个我们至少还可以用枚举法的话，那么这个问题要怎么解决呢？很多人看到这个问题都会不由自主地提出这样一个疑问：我们根本不知道数字0会出现在这十位数中的哪个位置啊！确实，先递减再递增的十位数，要比前面的递减或者递增的三位数复杂一些。但是，这个问题其实也不是那么难解决。 我们细心观察，就可以发现，数字0是不能出现在两端的，否则就无法满足先递减再递增这个条件。数字0只能出现在这个十位数的中间，当然不见得非要是正中间。聪明的朋友想到了一种解答方法，那就是分类考虑：9个数字选1个放在0的左边，选2个放在0的左边，选3个放在0的左边，……，选8个放在0的左边。左边的选完之后，右边永远只有一种递增的情况，无需再考虑。因此，答案就是：
能不能把问题想的再简单一点呢？我们发现，对于除了数字0之外的其他9个数字，在这个问题中其实都有一个共性的地方：每一个数字不是在0的左边，就是在0的右边。那么对于任何一个非零的自然数而言，其实都面临2个选择。于是就存在2的9次方个满足条件的十位数。 善于计算的小朋友可能会说：老师，你的答案不对啊，2的9次方是512，和前面我们得到的答案510不一样啊！其实，问题的关键就在2的9次方还包含了两种特殊的情况，就是1到9这9个数字全部在0的左边和全部在0的右边这两种不符合题目条件的情况，要从512中减去2，得到510。
最后，再提醒大家一下，所谓的组合问题就是与顺序无关的那些计数问题。 小结： 一、组合计数是一门非常有趣的课程，对于思维能力的训练有极大的帮助，而且不涉及复杂的数学知识，只要会加减乘除基本运算即可入门； 二、解数学题最终并不是为了那个答案，而是为了得到一般性的结论，这样才能做到举一反三、触类旁通！ 是的，排列组合问题既没有复杂的公式，也没有套路，只有洞见和思维。简单又粗暴，充满了暴力美学！这就是我一直喜欢给孩子们讲解组合数学的一个重要原因。我们学习数学，最重要的就是学校思维方式，而不是做一个只会刷题的解题机器！ 下一讲我们将会去探索和挑战更加复杂的排列和组合问题。 |
|
|
