4.4　排列与组合的关系

在本章前面学习了通过计数将所有情况都列出来的方法。下面开始研究排列与组合。根据本章开篇给出的定义，排列是从给定个数的元素中取出指定个数的元素进行排序。组合则是指从给定个数的元素中仅仅取出指定个数的元素，不考虑排序。可以看出，排列与组合的区别就是看问题是否和顺序有关，有关就是排列，无关就是组合。

4.4.1　排列

在实际生活中常遇到这样的问题，就是要把一些事物排在一起，构成一列，计算有多少种排法，这就是排列问题。

在排列的过程中，结果不仅与参加排列的元素有关，而且与各元素所在的先后顺序也有很重要的关系。

1．有多少种车票？

例如：在北京（南）与上海（虹桥）之间的高速动车G3/G4，途经南京（南），开通这条线路的高速动车共需要准许多少种不同的车票？

分析这个问题，可以用枚举法解决，3个城市之间的火车票有下面6种方式：

如果不用枚举法，注意到要准备的火车票的种类不仅与所选的两个城市有关，而且与这两个城市作为起点站、到达站的顺序有关，所以，要考虑共准备多少种不同的火车票，就要在3个城市之间每次取出两个，按照起点站、到达站的顺序排列。即，需要分为两步来进行操作：

（1）确定起点站，在3个城市中，任取一个为起点站，共有3种选法。

（2）确定到达站，每次确定了1个起点站后，只能从剩下的两个城市之中选出到达站，因此就只有两种选法。

对于这种分步完成的任务，根据乘法原理，可计算出需要准备的火车票种类：

为叙述方便，我们把研究对象（如上例中的火车站点）看作为元素，那么上面的问题就是在3个不同的元素中取出两个，按照一定的顺序排成一列的问题。

我们把每一种排法叫做一个排列（如“北京（南）——南京（南）”就是一个排列），把所有排列的个数叫做排列数。

那么上例中求火车票种类数量的问题就是求排列数的问题。可以看出，求排列数的问题，可以通过乘法原理进行快速计算。

既然知道了可以通过乘法原理来解决这个问题，那么对更复杂的情况也可以方便地解决了。例如，已知从北京（西）到广州（南）这条高速动车G7/9一共有6个站，那么这列高速动车共需要准备多少种不同的车票？

如果用枚举法，则可能需要写出很长一串站名了，先将6个站分别作为起点站，再将剩下的5个站作为到达站。显然，这种方式太繁琐了。

根据我们前面推导出的规律，可以用乘法原理解决这个问题，分两步，第1步在6个站点中取1个作为起点站（有6种可能）。第2步，在剩下的5个站点中选一个作为到达站（有5种可能），因此需准备的车票种类数量有：

2．旗语

由于火车票中只有起点站和到达站两个数据，只需要两个步骤即可完成，根据乘法原理，只需要将这两步中可选择站点的数量相乘即可得到车票种类数量。在实际生活中还经常遇到更复杂的情况。

我们来研究一个更复杂的例子：旗语。旗语在古代是一种主要的通信方式，现在是世界各国海军通用的语言。不同的旗子，不同的旗组表达着不同的意思。现假设两只船之间约定用5面颜色各异（由红、黄、蓝、白、绿）的旗帜来传递信息，将这5面旗帜放在船头固定位置。当这种5面旗帜按不同颜色排列时分别表达不同的信息，则这两只船之间通过5色旗能传递多少种含义不同的信息？

分析：用字母R表示红色、Y表示黄色、B表示蓝色、W表示白色、G表示绿色，则5种颜色的旗子可排列成如图4-12所示的不同形式。

图4-12

图4-12中的排列是按以下方法来处理的（共分5步，分别设置5种颜色旗帜的放置位置）：

（1）从5种颜色的旗帜中取1面旗放在第1个位置，有5种取法。

（2）从剩下的4种颜色的旗帜中取1面旗放在第2个位置，有4种取法。

（3）从剩下的3种颜色的旗帜中取1面旗放在第3个位置，有3种取法。

（4）从剩下的2种颜色的旗帜中取1面旗放在第4个位置，有2种取法。

（5）只剩下1种颜色的旗帜，直接放在第5个位置，只有1种取法。

根据乘法原理可得：

即，5色旗有120种排列，可表示120种不同的信息。

3．排列的数学表示

根据上面的例子，对排列进行归纳总结，可得到以下规律：

一般地，从n个不同的元素中任取出m个（m≤n）元素，按照一定的顺序排成一列，叫做从n个不同元素中取出m个元素的一个排列。

由排列的定义可以看出，如果两个排列相同，不仅表示这两个排列中的元素完全相同，而且各元素的先后顺序也一样。如果两个排列的元素不完全相同，或者各元素的排列顺序不完全一样，则表示是两个不同的排列。

从n个不同元素中取出m个（m≤n）元素的所有排列的个数，叫做从n个元素中取出m个元素的排列数，在数学里将其记为：

那么，上面这个排列的表示该怎么计算呢？

根据前面的两个例子可以归纳出如下计算步骤：

（1）先排第一个位置上的元素，可以从n个元素中任选一个，有n种不同的选法。

（2）排第2个位置上的元素。这时，由于第一个位置已用去了1个元素，只剩下（n－1）个不同的元素可供选择，共有（n－1）种不同的选法。

（3）排第3个位置上的元素，有（n－2）种不同的选法；

……

第m步：排第m个位置上的元素。由于前面已经排了（m－1）个位置，用去了（m－1）个元素。这样，第m个位置上只能从剩下的[n－（m－1）]＝（n－m＋1）个元素中选择，有（n－m＋1）种不同的选法。

因此，根据乘法原理，可列出排列数的计算公式如下：

这里，m≤n，且等号右边从n开始，后面每个因数比前一个因数小1，共有m个因数相乘。

例如，对前面关于旗语的例子进行修改，因为用5面5色旗可以表示120种状态，含义太多，旗手也可能记不住这么多状态的含义，也用不了这么多种状态。现在进行精简，仍然使用5色旗，但是每次只用3面旗帜，求这种方式的旗帜组合能表示出多少种不同的含义？

根据前面总结的规律，可用以下算式来进行计算：

如果从5色旗中选4面旗，可以表示多少种不同的含义呢？

可以看出，将5面旗帜全部用上和只用4面旗帜，得到的排列数完全相同。这是由于，把前4面旗帜选定之后，就只剩最后那一面旗帜，也就没办法选择了。因此，最后一面旗帜用不用已经无所谓了。

从排列的计算公式也可看出，若从n个元素中选择n个元素进行排列，可得到以下计算公式：

可以看出，这就相当于是计算n的阶乘了。

若从n个元素中选择n－1个元素进行排列，可得到以下计算公式：

可以看出：

所以，在上面旗语的例子中，从5色旗中选择4面旗帜就可以表示出最多的状态数量了。

4.4.2　组合

日常生活中有很多“分组”问题，例如，在体育比赛中，把参赛队分为几个组（这时分在同一组中的队友之间的位置顺序并不重要），这种“分组”问题，就是我们下面将要讨论的组合问题，这里，我们将着重研究有多少种分组方法的问题。

1．有多少种票价？

仍然来看火车票的问题。

在前面计算排列数的例子中，我们已经知道在北京（南）与上海（虹桥）之间的高速动车G3/G4，途经南京（南），开通这条线路的高速动车会有6种不同车票。现在要求这些火车票共有几种价格（假设相同两站之间往返票价相同）？

由于往返票价格相同，这时，从“北京（南）”到“南京（南）”的车票价格与从“南京（南）”到“北京（南）”的票价相同。

因此，求有多少种价格的问题实际上就是计算从3个城市中取两个城市，有多少种不同的取法，即这时只与考虑的两个城市有关而与两个城市的顺序无关。

通过枚举法可求出有以下3种票价：

这是通过枚举法推导出来的数量，如果要计算的车站数量增多，用这种枚举方法显然就不方便了。

那么，有没有办法通过公式进行计算呢？

我们来推导一下。要计算车票价格的种类可按以下方式考虑：

（1）仍然按“排列”的方式计算出有多少种排列数。

（2）剔除重复计数的部分。

到这里，重点就是该怎么计算重复部分了。

在上面计算车票价格的问题中，每张车票需要关注的有两个站点名称，A站到B站和B站到A站的票价是一样的，但在第（1）步的排列中却计算了2次，实际车票价格只有一种。所以，重复计数1次。这样，只需要将第（1）步计算的排列数除以2，就可以得到不同的车票价格数量了。

根据以上推导过程，如果一列火车有10个站点，则这列火车的票价种数为：

2．有多少组旗语？

在上面旗语的例子中，如果不关注各色旗帜的排放顺序，5色旗能有多少种组合呢？

由于不区分各色旗帜的排列顺序，因此，如下面的5种排列其实都只能算是一种组合，因为都是由红（R）、黄（Y）、蓝（B）、白（W）、绿（G）这5种颜色的旗帜组成的。

从图4-12中可看出，图中的120种排列情况中的每种排列都包含5种颜色的旗帜，因此，若用5面5色旗帜只能构成一种组合。

那么，若只取5色旗中的4面旗帜，可以构成多少种组合呢？

根据我们上面推导出的火车票价格种类的方法，同样可以分成两步来计算旗语的组合种类，即：

（1）按“排列”的方式计算出旗语有多少种排列数。

（2）剔除重复计数的部分。

对于第（1）步，计算从5色旗中取4面旗可构成多少排列数，可按以下公式计算：

在第（2）步，需要计算重复计数的部分，将这部分从排列数中剔除，才能得到实际的组合种类数。该如何计算出重复的数据呢？

在这个例子中要计算出重复数，不如计算不同火车票价种类好理解，因为火车票价只需要2个元素，而现在的例子中每一个组合要用4个元素（即4种颜色的旗帜）。

这时可以考虑用先选择4种颜色的旗帜，如选择红（R）、黄（Y）、蓝（B）、白（W），这4种颜色的旗帜按排列的方式可得到如图4-13所示的排列情况，有24种。

图4-13

可以看出，图4-13是枚举的排列数，也可用以下公式计算：

如图4-13所示，这24种排列其实只是一种组合。这样，就可将第（1）步中计算出的排列数120，除以第（2）步中计算出的排列数24，即可得到组合数5。即从5色旗中选择4面旗帜可得到5种不同的组合。

3．组合的数学表示

一般地，从n个不同元素中取出m个（m≤n）元素组成一组不计较组内各元素次序的序列，叫做从n个不同元素中取出m个元素的一个组合。

由组合的定义可以看出，两个组合是否相同，只与这两个组合中的元素有关，而与取到这些元素的先后顺序无关，只有当两个组合中的元素不完全相同时，它们才是不同的组合。

从n个不同元素中取出m个元素（m≤n）的所有组合的个数，叫做从n个不同元素中取出m个不同元素的组合数，记作：

根据前面的两个例子可得出组合数的计算公式：

有了这个公式，就可以方便地计算出从n个元素中选择m个元素的组合数了。

例如，在计算不同火车票价格种类的例子，就是要计算从3个城市中取2个城市的组合数，可使用以下公式进行计算：

而在旗语的例子中，从5色旗中选择4面旗帜共可得到的组合数可用以下公式进行计算：

从5色旗中选择3面旗帜，共可得到多少组合数呢？

由此可见，在n个元素中选择m个元素进行组合，得到的组合数与m有关。m越大组合数反而越小，若m＝n，则组合数为1。

4.4.3　排列与组合的联系

下面再来看看排列与组合的联系吧。以从5色旗中选择3面旗帜为例，来分析排列与组合的关系。

首先来看，如果取3面旗帜，可得到如图4-14所示的排列。这种用所有元素进行的排列称为全排列。

图4-14

接着再来看从5色旗中取3面旗帜的组合情况，如图4-15所示。

将图4-15所示组合的第1个组合中的各色旗帜进行排列，就可得到图4-14所示的排列。若将其余各组合也进行类似的排列，就可得到如图4-16所示的排列效果（中间部分省略了）。

图4-15

在图4-16中，已将排列数与组合数的关系通过算式列出来了，这个算式与上节介绍的组合数计算公式相符。

图4-16

4.4.4　可重排列

在上面介绍的排列是从n个不同的元素中任取出m个（m≤n）元素，按照一定的顺序排成一列。这里选取的元素数量m不能超过n，并且当选取了一个元素之后，这个元素就不能再次被选取了。也就是说，在一个排列中，元素之间的值不会相同。

在现实生活中，还会出现另一种情况，就是在一个排列中，有的元素是相同的。例如，电话号码是由0～9这10个数字排列组成，各位数字有可能重复。如电话号码82608833中数字8出现了3次，数字3出现了2次。

对于这种从n个不同元素中取出m个元素（同一个元素允许重复取出），按照一定的顺序排成一列，叫做n个不同元素的一个m-可重排列。

1．有多少个电话号码？

对于重复排列中排列数的计算，不能再使用前面介绍的方法了。

例如：北京市固定电话号码是由8位数字组成，每位数字可从0～9中任取一个，问北京市固定电话最多可有多少种不同的电话号码？

不考虑电话号码中是否有特殊号码，只按数字进行排列的话，8位数字中每一位数都可以在0～9这10个数码中取一个。

可按以下方法计算电话号码各位的可能情况：

第1位：可取0～9这10个数中的一个，有10种可能；

第2位：可取0～9这10个数中的一个，有10种可能；

第3位：可取0～9这10个数中的一个，有10种可能；

……　……

8位电话号码可分8步分别考虑可能的情况，根据乘法原理可得：

因此，8位数的电话号码有1亿种可能。也就是说，用8位数字可以排列出1亿个电话号码。

注意，在上面的排列中，将各种情况都包含在内，没有考虑一些特殊情况。例如，8位数全部为0，或前7位都为0，只有个位数的（即1位数的电话号码），或者只有2位数电话号码，这些在实际生活中都不存在。

从这个例子可看出，对于可重排列，要计算其排列数，可使用以下公式：

即，n个不同元素的m-可重排列数为n的m次。

2．汽车牌照问题

在国内，民用机动车的牌照号是由多部分组成的，有省的简称，地级市字母代码及5位字符编码组成，如图4-17所示的车牌号为“浙F99999”。

图4-17

如果车牌号后面的5位数只采用数字进行组合，可以有多少个不同的号牌？

根据上面可重排列的计算规则，可得：

即，可有10万个不同的号牌。

对于一个地级市，10万个车牌号明显不够用。为了使每一位车主都能有自己唯一的车牌号，该怎么办呢？

根据可重排列数的计算公式中用到的n和m这两个变量，可有两种解决方案：

第一种方法是增加m的值（即增加车牌号码的位数，由5位数改为6位、7位、甚至8位数），这样就可呈10倍、100倍、1000倍地增加不同的车牌号。

第二种方法则是增加n的值，也同样可增加不同的车牌号。

现实中采用是的第二种方法，在车牌号后5位数中除了使用数字之外，增加使用英文字母。除了英文字母O与数字0，字母I与数字1不易分辨不用之外，使用其余24个大写字母。这样，10个数字加上24个字母，共34个符号，则可得到4千多万个不同的号牌。

可以看到，增加n的值，可显著增多可重排列数。

现在一般一个地级市的机动车拥有量在百万之内（整个北京400万辆左右，分到各区就只有几十万辆了），肯定够用了。一般城市通常最多在车牌号码的5位中使用2位字母，那么，这样会有多少个不同的车牌号码呢？下面分3种情况来计算：

第1种，5位号码全部为0～9的数字，可有10万个不同的车牌号。

第2种，若在5位车牌号码中有一位使用英文字母，其他4位使用数字，可有以下5类情况（字母A表示24个英文字母中的一个，数字0表示0～9中的一个数字）。

每类可得到不同车牌号码数量为：

则5类情况可得到不同车牌号码数量为：

也就是说，第二种车牌号码（即1位英文字母、4位数字）可有120万个不同的号码。

第3种，若在5位车牌号码中有2位使用英文字母，其他3位使用数字，可有以下10类情况（字母A表示24个英文字母中的一个，数字0表示0～9中的一个数字）：

每类可得到不同车牌号码数量为：

则10类情况可得到不同车牌号码数量为：

将以上3种情况中的数值进行累加，即可得到不同车牌号码数量为：

这样，5位车牌号中，有0～2位用英文字母，另5～3位使用数字，可有796万多个不同的号码，足够使用了。