在计数问题(一)中我们分析了排列和组合的定义,计算方法以及公式的含义。排列组合的基本定义讲述的是从一列元素中分先后(排列)或不分先后地选出部分元素,其可能的选择方法数。在这一期中我们会更仔细地分析组合的公式的含义,并在此基础上就更复杂的一些概念进行讨论。
我们先来考虑这样一个问题:如图,一个人沿着格子以最短的路线从A点走到B点,有多少种方法?
我们首先要明确的是,以最短路线行走意味着这个人从A走到B的过程中不能向左或向下行进,只能是向上或向右。但向上或向右的顺序可以不同。这里我将此人向上移动用
来表示;向右移动用 来表示。所以,任意一个有两个 和三个 的组合即形成了一种可能的路线。那么计算所有可能的路线数就转化成了计算 的排列数。这里我们发现其只包含两种元素,所以确定了 的位置之后,所有的 的位置也就确定了下来。所以答案可以写成 种。
另外一种计算的方法就是将所有的箭头都看作是不同的,其组合数为
。其中包含了2个相同的元素和3个相同的元素,所以最后的排列数为: 种。
读到这里我们可以先停下来思考一个问题:为何在这个问题中我们既可以用组合公式,也可以用排列公式来计算呢?
问题的关键就在于从哪个角度去分析问题。
和 都是对问题进行分析的结果,在某些问题中,相同的计算公式也可以有不同的解释。可见,如何将计数问题中不同的情况和排列、组合的公式对应起来是一个值得研究的问题。以下总结了一些用到排列组合公式的不同的情景,我们用将小球放入盒子这一操作来说明:
一、 将5个不同的球放入5个不同的盒子中,每个盒子放一个球,有多少种方法。
二、 将5个不同的球放入3个不同的盒子中,有多少种方法。
三、 将3个不同的球放入5个不同的盒子中。有多少种方法。
四、 将3个不同的球放入5个不同的盒子中,每个盒子只能容下一个球,有多少种方法。
五、 将5个相同的球放入3个不同的盒子中,盒子不能是空的,有多少种方法。
六、 将9个相同的球放入3个不同的盒子中,每个盒子至少2个球,有多少种方法。
七、 将5个相同的球放入3个不同的盒子中,有多少种方法。
解释:
一、可以看作是将5个不同的球排成一列,所以是排列问题,结果为
二、 每一个球都有三个不同的选择,而完成这个任务需要五步(依次放5个球),所以是
三、与上一问题类似,结果为
四、可以看作是5个不同的球中选出3个,顺序有关。与问题一类似。结果为
五、这一问题可以使用隔板法。即可以将放入三个盒子这一动作看成是在5个球排成的一列之间插入2个隔板,由于每个盒子中都要有球,所以隔板选择的位置就是5个球形成的4个空档。结果为
六、由于球都是相同的,可以考虑成将三个盒子每一个都放入一个球,剩下的6个放入3个盒子中,每个格子至少放1个,也就转化成了隔板法。所以结果为
七、可以考虑成每个盒子中事先都放入了一个球,然后剩下的5个球随便放入3个不同的格子中。也就转化成了8个球放入3个盒子每个盒子必有球的隔板法。结果为
以上例子可以便于我们分析问题时使用,也可作为一个能否理解排列组合公式的检验。
另外,在一开始的走方格的例子中解释中我们使用了有重复的排列的计数方法。其描述了有重复的已知元素的全排列。如1,1,2,这三个元素的所有不同的排列方法:
种。其还可以应用到有重复的不确定元素的全排列。比如,1,2,3,4这四个数中任选两个(可以是相同的元素)的所有可能的总数。假设我们用 表示选取当前元素,用 表示选择的对象移到下一元素,则在1,2,3,4中选择出2个元素(可重复)这一过程可以使用 的全排列来表示,也即 种。
以上仅是一些对于排列组合问题的简单分析。不足之处请大家包含,有问题的地方也欢迎朋友们批评指正。