排列组合公式推导.doc

1公吨=1t=1000kg密度单位g/cm3Proe密度单位 公吨/mm31公吨/mm3=1000kg/(cm3×10-3)=109g/cm31g/cm3=10-9公吨/mm3排列和组合基本公式的推导，定义在本节中，笔者将介绍排列(Permutation)和组合(Combination)的基本概念和两个基本公式。请注意 点算组合学中的很多概念都可以从不同角度解释为日常生活中的不同事例，因此笔者亦会引导读者从不同 角度理解排列和组合的意义。 先从排列开始。排列的最直观意义，就是给定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种选择。由於以上各程序是各自独立的 ，我们可以运用乘法原理求得答案为n×(n-1)×(n-2)×. 2×1。在数学上把上式简记为n!，读作n阶乘(n-factorial)。 例题1：把1至3这3个数字进行全排列，共有多少种排法？试列出所有排法。 答1：共有3! = 3 × 2 × 1 = 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种选择。最后，运用乘法原 理求得答案为n×(n-1)×(n-2)×.(n-r+1)。 我们可以把上式改写为更简的形式n! / (n-r)!，为甚麼可以这样改写？这要用到n!的定义和乘法的结 合律。举一个简单的例子，由於5! = 5 × 4 × 3 × 2 × 1 = 5 × (4 × 3 × 2 × 1) = 5 × 4!。同样由於5 × 4 × 3 × 2 × 1 = 5 × 4 × (3 × 2 × 1)，我们又可得5! = 5 × 4 × 3!。抽象地看，我们 可以把n!改写为n×(n-1)!，也可以改写为n×(n-1)×(n-2)!照此类推，我们可以把n!改写为n×(n-1)×(n-2)×.(n-r+1)×(n-r)!。由此得n! / (n-r)! = n ×(n-1)×(n-2)×.(n-r+1)。在点算组合学上，一般把上述部分排列的 解记为P(n, r)。至此我们求得排列问题的一条基本公式：P(n, r) = n!/(n-r)! 例题2：从1至4这4个数字中抽2个出来排序，共有多少种排法？试列出所有排法。 答2：共有P(4, 2) = 4! / 2! = (4 × 3 × 2!) / 2! = 4 × 3 = 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) × r!，由此得C(n, r) = P(n, r) / r!。代入前面P(n, r)的公式，应得C(n, r) = n!/(n-r)!×r!) 正如前面的排列公式适用於全排列的情况，上述组合公式也适用於全组合的情况，即求 C(n, n)的问题。根据上述公式，C(n, n) = n!/(n-n)! × r!) = n! / (0! × r!) = 1。这一结果是完全合理的，因为从n个球中抽取所有n个出来，当然只有1种方法。 例题3：从1至4这4个数字中抽2个出来(不考虑次序)，共有多少种组合？试列出所有组合。 答3：共有C(4, 2) = 4! / (2! × 2!) = (4 × 3 × 2!) / (2! × 2!) = (4 × 3) / 2 = 6种组合。这6种组合是1,2；1,3；1,4；2,3；2,4；3,4。请注意如果我们把上述6种组合 的每一种排序，由於每一组合均包含两个数字，所以每一组合各有两种排序方式(例如从1,2可得到1-2和2-1两 种排序方式)，这样从4个数字中抽2个出来排序的排法便有6 × 2 = 12种，这正与例题2的解答完全一致 。 请注意在上述C(n, r)的公式中，如果我们把r换成n-r，我们将得到C(n,n-r) = n!/(n!×(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! × 3!) = (8 × 7 × 6 × 5!) / (5! × 3!) = (8 × 7 × 6) / (3 × 2) = 56。 本例题说明了一点，对於一个具体问题，我们不能一概而论地把它归类为排列问题还是组合问题，因 为这要看我们是在点算甚麼。就本例题而言，由於我们点算的对象是那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) × 5! × 3! = (8! × 5! × 3!) / (3! × 5!) = 8!，所得结果跟前面的完全相同。 比较上述两种解题方法，当然是第一种简洁得多。而这种简洁的解题法之所以能成立，是因为本题所给予的有 两类外星人的信息是多余的。由於本题对两类外星人的坐法完全不加限制，因此不论这两类外星人的比例如何 ，也不论有多少类外星人，只要外星人的总数是8，答案都是一样的。当然，如果对外星人的坐法有所限制，例 如不容许两个火星人坐在相邻的位置，情况将大为不同。此一情况在以后还将讨论到。注1：有些人可能难以理解为何0!等於1而不是等於0，因为0乘以任何数都是0。请注意n! = n×(n-1)×.2×1这个定义只适用於当n是正整数的情况，当n = 0时，便不能再运用上式 来定义0!。至於为何要定义0! = 1，这完全是为了使上述的排列公式也适用於全排列的情况，并且使 0!的定义能与排列的公式相协调。这一点就正如定义n0 = 1 (当n为正实数)一样，是为了使n a的定义也适用於当a = 0的情况，并且使n0的定义能与指数的运算法则(例如na-b = na/nb)相协调。 注2：例如，当我们说那3个1位於第1、第3和第5位，跟说那3个1位於第5、第1和第3位是没有分别的。