![[宝典]排列组合公式推导2014](https://swf.iask.com/iGJtuuiDFX.jpg?ssig=vYq3eFx53%2F&Expires=1719191526&KID=sina,ishare&range=0-334605)
[宝典]排列组合公式推导2014
排列和组合基本公式的推导，定义
先从「排列」开始。的最直观意义，就是给定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种方法。
本文档为【[宝典]排列组合公式推导2014】，请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑，
图片更改请在作品中右键图片并更换，文字修改请直接点击文字进行修改，也可以新增和删除文档中的内容。
该文档来自用户分享，如有侵权行为请发邮件ishare@vip.sina.com联系网站客服，我们会及时删除。
[版权声明] 本站所有资料为用户分享产生，若发现您的权利被侵害，请联系客服邮件isharekefu@iask.cn，我们尽快处理。
本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权，请谨慎使用。
网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传，仅限个人学习分享使用，禁止用于任何广告和商用目的。
浙公网安备 33021202002483