排列和组合基本公式

排列和组合基木公式先从「排列」开始。「排列」的最直观意义，就是给定n个「可区别」(Distinguishable，亦作「相异」)的物件，现把这n个物件的全部或部分排次序，「排列」问题就是求不同排列方式的总数。为了区别这些物件，我们可不妨给每个物件一个编号：1、2...n，因此「排列」问题实际等同于求把数字1、2...n的全部或部分排次序的方式总数。「排列」问题可分为「全排列」和「部分排列」两种，当我们把给定的n个数字1、2...n全部排次序，求有多少种排法时，就是「全排列」问题。我们可以把排序过程分解为n个程序：第一个程序决定排于第一位的数字，第二个程序决定排于第二位的数字...第n个程序决定排于第n位的数字。在进行第一个程序时，有n个数字可供选择，因此有n种选法。在进行第二个程序时，由于在前一程序已选定了一个数字，现在可供选择的数字只剩下n-1个，因此有n-1种选法。在进行第三个程序时，由于在前一程序已选定了一个数字，现在可供选择的数字只剩下n-2个，因此有n-2种选法。如是者直至第n个程序，这时可供选择的数字只剩下1个，因此只有1种选择。由于以上各程序是「各自独立」的，我们可以运用「乘法原理」求得答案为nx(n-1)x(n-2)x...2x1。在数学上把上式简记为n!，读作「n阶乘」(n-factorial)o例题1：把1至3这3个数字进行「全排列」，共有多少种排法？试列出所有排法。答1:共有3!=3x2x1=6种排法，这6种排法为1-2-3；1-3-2；2-1-3；2-3-1；3-1-2；3-2-1。□当然，给定n个数字，我们不一定非要把全部n个数字排序不可，我们也可只抽取部分数字(例如r个，r<n)来排序，并求有多少种排法，这样的问题就是「部分排列」问题。我们可以把「部分排列」问题理解成抽东西的问题。设在某袋中有n个球，每个球都标了编号1、2...n。现从袋中抽r个球出来(抽出来之后不得再放回袋中)，并把球上的数字按被抽出来的顺序记下，这r个数字的序列实际便等同于一个排序。「部分排列」问题的解答跟「全排列」问题非常相似，只不过现在我们是把排序过程分解为r个而非n个步骤。进行第一个程序时，有n个数字可供选择，因此有n种选法。在进行第二个程序时，由于在前一程序已选定了一个数字，现在可供选择的数字只剩下n-1个，因此有n-1种选法。在进行第三个程序时，由于在前一程序已选定了一个数字，现在可供选择的数字只剩下n-2个，因此有n-2种选法。如是者直至第r个程序，这时可供选择的数字只剩下n-r+1个，因此只有n-r+1种选择。最后，运用「乘法原理」求得答案为nx(n-1)x(n-2)x...(n-r+1)。我们可以把上式改写为更简的形式n!/(n-r)!，为什么可以这样改写？这要用到n!的定义和乘法的结合律。举一个简单的例子，由于5!=5x4x3x2x1=5x(4x3x2x1)=5x4!。同样由于5x4x3x2x1=5x4x(3x2x1)，我们又可得5!=5x4x3!。抽象地看，我们可以把n!改写为nx(n-1)!，也可以改写为nx(n-1)x(n-2)!照此类推，我们可以把n!改写为nx(n-1)x(n-2)x...(n-r+1)x(n-r)。由此得n!/(n-r)!=nx(n-1)x(n-2)x...(n-r+1》在「点算组合学」上，一般把上述「部分排列」的解记为P(n,r)。至此我们求得「排列」问题的一条基本公式：P(n,r)=n!/(n-r)!例题2:从1至4这4个数字中抽2个出来排序，共有多少种排法？试列出所有排法。答2:共有P(4,2)=4!/2!=(4x3x2!)/2!=4x3=12种排法。这12种排法是1-2；1-3；1-4；2-1；2-3；2-4；3-1；3-2；3-4；4-1；4-2；4-3。□请注意只要我们定义0!=1(注1)，那么上述公式便也适用于「全排列」的情况。「全排列」其实就是r=n的情况，因此如果把r=n代入以上公式，便得P(n,n)=n!/(n-n)!=n!/0!=n!/1=n!正与前面讨论的结果吻合。接下来笔者介绍「组合」问题。设在某袋中有n个球，每个球都标了编号1、2...n。现从袋中抽r个球出来(抽出来之后不得再放回袋中)，并把球上的数字记下，但无须理会球被抽出的先后次序。由此可见，「组合」问题与「排列」问题的主要区别是，前者只关心被抽出来的包含哪些数字，而不管这些数字的顺序；而后者则既关心被抽出来的包含哪些数字，也关心这些数字的顺序。惟请注意，「排列」和「组合」虽然是两种很不相同的问题，但两者却并非绝然对立，而是有着非常密切的联系。日常生活中很多点算问题往往同时包含着「排列」和「组合」的因素，如能了解其中奥妙，很多点算问题便容易解决。事实上，我们正可利用「排列」和「组合」的这种微妙关系找出「组合」问题的公式。我们把从n个球中抽r个出来的组合数记为C(n,r)。以下我们利用「排列」和「组合」之间的关系以及「排列」的公式来推导出C(n,r)的公式。前面提过，「部分排列」问题可以理解成从n个标了编号的球中抽r个出来，并把球上的数字按被抽出来的顺序记下。其实我们可以把上述过程分解为两个程序，第一个程序就是从n个球中抽r个出来，先不理会它们被抽出来的顺序，此即前面所定义的「组合」问题。第二个程序则是把这r个被抽出来的球全部排次序，并求有多少种排法，此即前面介绍过的「全排列」问题。换句话说，我们可以把「部分排列」问题分解为一个「组合」问题和一个「全排列」问题(由此可见「排列」和「组合」并非绝然对立)。由于上述两个程序是「各自独立」的，根据「乘法原理」，「部分排列」问题的解应等于「组合」问题的解乘以「全排列」问题的解，即P(n,r)=C(n,r)xr!，由此得C(n,r)=P(n,r)/r!。代入前面P(n,r)的公式，应得C(n,r)=n!/((n-r)!xr!)正如前面的「排列」公式适用于「全排列」的情况，上述「组合」公式也适用于「全组合」的情况，即求C(n,n)的问题。根据上述公式，C(n,n)=n!/((n-n)!xr!)=n!/(0!xr!)=1。这一结果是完全合理的，因为从n个球中抽取所有n个出来，当然只有1种方法。例题3:从1至4这4个数字中抽2个出来(不考虑次序)，共有多少种组合？试列出所有组合。答3:共有C(4,2)=4!/⑵x2!)=(4x3x2!)/⑵x2!)=(4x3)/2=6种组合。这6种组合是1,2；1,3；1,4；2,3；2,4；3,4。请注意如果我们把上述6种组合的每一种排序，由于每一组合均包含两个数字，所以每一组合各有两种排序方式(例如从1,2可得到1-2和2-1两种排序方式)，这样从4个数字中抽2个出来排序的排法便有6x2=12种，这正与例题2的解答完全一致。口请注意在上述C(n,r)的公式中，如果我们把r换成n-r，我们将得到C(n,n-r)=n!/(n!x(n-r)!)其结果与C(n,r)相同，由此我们得到C(n,r)=C(n,n-r)。这一点是容易理解的，可以用一个简单的例子来说明筒中原理。假设我们要求从5个人(假设为A、B、C、D、E)中选出4个人的组合数，此即C(5,4)。这个问题其实可以从另一个角度去理解。由于只要我们知道哪一个是「落选者」，便自然知道哪些人是「入选者」，因此从5个人中选出4个人(入选者)的组合数其实就等同于从5个人中选出1个人(落选者)的组合数，即C(5,4)=C(5,5-4)=C(5,1)=5。把上述结果推广到一般情况，便得到上述的等式。前面提过，「排列」和「组合」并非绝然对立，有时同一个问题可以从不同角度理解为「排列」或「组合」的问题，而转换角度往往可以令本来难解的问题变得容易。以下笔者将举出两个例题，说明如何利用这种转换角度的方法解答问题。例题4:用1和2这两个数字可以构造多少个包含3个1的八位整数？答4:本题初看似应理解为一个「排列」问题，可不是吗？11122222跟22222111是两个不同的八位整数，由此可见，本题必须考虑八位整数中1和2的次序，因此似乎应运用「排列公式」。可是想深一层，本题其实已规定了所求的八位整数必须包括3个1和5个2,因此我们已无须考虑这些八位整数应包含哪些数字，而只须考虑这些数字的位置。而且由于这些八位整数只包含两种数字，我们只需确定其中一种数字(例如1)的位置便确定了整个八位整数，例如如果我们确定那3个1位于第1、第3和第5位，我们便确定这个八位整数是12121222。因此确定本题的八位整数便等同于从8个位置中选出3个位置来安放那3个1,而且由于把代表位置的数字列出来无所谓谁先谁后(注2)，因此本题其实应理解为一个「组合」问题，所求答案是C(8,3)=8!/(5!x3!)=(8x7x6x5!)/(5!x3!)=(8x7x6)/(3x2)=112。□本例题说明了一点，对于一个具体问题，我们不能一概而论地把它归类为「排列」问题还是「组合」问题，因为这要看我们是在点算什么。就本例题而言，由于我们点算的对象是那3个1的「位置」，而这些位置的先后次序不影响点算结果，所以本题是「组合」问题而非「排列」问题。例题5:设有5个可区别的木星人和3个可区别的火星人，现在要安排他们坐在一排共8个座位上，问有多少种不同坐法？答5:由于这8个外星人是可区别的，不妨把他们命名为A、B、C、D、E、F、G和H。本题其实相当于把这8个字母排次序，并求有多少种排法，因此本题是一个「全排列」问题，答案是8!=40320。有些人可能觉得奇怪，为何本题的答案如此简单？既然本题涉及两类数目各不相同的外星人，似乎应对这两类人分别处理。现在就让我们从另一个角度解本题，看看答案是否相同。首先，我们可以把排座位的过程分解为三个程序：第一个程序是先从那8个座位选5个出来给木星人坐，这是一个「组合」问题，应有C(8,5)种选法。第二个程序则是安排那5个木星人(假设为A、B、C、D和E)坐这5个已选定的座位，这是一个「全排列」问题，共有5!种排法。第三个程序则是安排那3个火星人(假设为F、G和H)坐余下的座位，这也是一个「全排列」问题，共有3!种排法。最后运用「乘法原理」求得本题答案为C(8,5)x5!x3!=⑻x5!x3!)/⑶x5!)=8!，所得结果跟前面的完全相同。口比较上述两种解题方法，当然是第一种简洁得多。而这种简洁的解题法之所以能成立，是因为本题所给予的有两类外星人的信息是多余的。由于本题对两类外星人的坐法完全不加限制，因此不论这两类外星人的比例如何，也不论有多少类外星人，只要外星人的总数是8,答案都是一样的。当然，如果对外星人的坐法有所限制，例如不容许两个火星人坐在相邻的位置，情况将大为不同。此一情况在以后还将讨论到。注1:有些人可能难以理解为何0!等于1而不是等于0,因为0乘以任何数都是0。请注意n!=nx(n-1)x..