欢迎来到天天文库
浏览记录
ID:12987784
大小:36.50 KB
页数:5页
时间:2018-07-20
《排列组合公式推导》由会员上传分享,免费在线阅读,更多相关内容在行业资料-天天文库。
1、1公吨=1t=1000kg密度单位g/cm3Proe密度单位公吨/mm31公吨/mm3=1000kg/(cm3×10-3)=109g/cm31g/cm3=10-9公吨/mm3排列和组合基本公式的推导,定义在本节中,笔者将介绍「排列」(Permutation)和「组合」(Combination)的基本概念和两个基本公式。请注意 「点算组合学」中的很多概念都可以从不同角度解释为日常生活中的不同事例,因此笔者亦会引导读者从不同 角度理解「排列」和「组合」的意义。 先从「排列」开始。「排列」的最直观意义,就
2、是给定n个「可区别」(Distinguishable,亦作「相 异」)的物件,现把这n个物件的全部或部分排次序,「排列」问题就是求不同排列方式的总数。为了区别这些 物件,我们可不妨给每个物件一个编号:1、2 ... n,因此「排列」问题实际等同於求把数字1、2 ... n的全 部或部分排次序的方式总数。「排列」问题可分为「全排列」和「部分排列」两种,当我们把给定的n个数字1 、2 ... n全部排次序,求有多少种排法时,就是「全排列」问题。我们可以把排序过程分解为n个程 序:第一个程序决定排於第一位
3、的数字,第二个程序决定排於第二位的数字...第n个程序决定排於第n位的数字 。在进行第一个程序时,有n个数字可供选择,因此有n种选法。在进行第二个程序时,由於在前一程序已选定 了一个数字,现在可供选择的数字只剩下n-1个,因此有n-1种选法。在进行第三个程序时, 由於在前一程序已选定了一个数字,现在可供选择的数字只剩下n-2个,因此有n-2种选法。 如是者直至第n个程序,这时可供选择的数字只剩下1个,因此只有1种选择。由於以上各程序是「各自独立」的 ,我们可以运用「乘法原理」求得答案为n×(n-1)
4、×(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)来 排序,并求有多少种排法,这样的问题就是「部分排列」问题。我们可以把「部分排列」
5、问题理解成 抽东西的问题。设在某袋中有n个球,每个球都标了编号1、2 ... n。现从袋中抽r个球出来(抽出来之后不得再 放回袋中),并把球上的数字按被抽出来的顺序记下,这r个数字的序列实际便等同於一个排序。「部分排列」 问题的解答跟「全排列」问题非常相似,只不过现在我们是把排序过程分解为r个而非n个步骤。进行第一个程 序时,有n个数字可供选择,因此有n种选法。在进行第二个程序时,由於在前一程序已选定了一个数字,现在 可供选择的数字只剩下n-1个,因此有n-1种选法。在进行第三个程序时,由於在前一程
6、序已 选定了一个数字,现在可供选择的数字只剩下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 ×
7、 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,
8、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
此文档下载收益归作者所有