kl800.com省心范文网

排列组合公式推导


1 公吨=1t=1000kg 密度单位 g/cm3 Proe 密度单位 公吨/mm3 1 公吨/mm3=1000kg/(cm3× -3)=109g/cm3 10 3 -9 3 1g/cm =10 公吨/mm

排列和组合基本公式的推导,定义
在本节中,笔者将介绍「排列」(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 个, < n)来 排序, r 并求有多少种排法, 这样的问题就是 「部 分排列」问题。我们可以把「部分排列」问题理解成 抽东西的问题。设在某袋 中有 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 位」是没有分别的。


排列组合公式推导

10 3 -9 3 1g/cm =10 公吨/mm 排列组合基本公式推导,定义在本节中,笔者将介绍「排列」(Permutation)和「组合」(Combination)的基本 概念和两个基本公式...

排列组合公式推导2014

排列组合公式推导2014_数学_高中教育_教育专区。排列和组合基本公式的推导,定义先从「排列」开始。「排列」的最直观意义,就是给定 n 个「可区别」 (Distinguishable...

排列组合 公式推导

排列组合 公式推导_教育学/心理学_人文社科_专业资料。排列组合 公式推导 排列P---和顺序有关 组合C ---不牵涉到顺序的问题 排列分顺序,组合不分例如把5 本...

排列组合的基本理论和公式

、20 这二十个数中任取三个不同的数组成等差 数列,这样的不同等差数列有__...排列组合公式(全) 3页 免费 排列组合公式推导 5页 免费喜欢此文档的还喜欢 ...

全错位排列递推公式的简易推导(齐麟-晋级)

华图文库: wenku.huatu.com 全错位排列递推公式的简易证明华图教育 齐麟 错位排列作为排列组合中的一类典型题目, 自身难度较高, 考生往往只是知其然而不知 其所以...

排列组合公式

排列组合公式推导都基于如下两条计数原理: (1)乘法原理(分步) 如果某件事需经 k 个步骤才能完成,做第一步有 m1 种方法,做第二步有 m2 种方 法??做...

题目f37a77232f60ddccda38a02e

简答题12分 理科数学 组合数公式推导 已知定点A(-1,0),F(2,0),定直线l:x=,不在x轴上的动点P与点F的距离是它到直线l的距离的2倍.设点P的轨迹为E...

排列组合公式详解(公务员)

知识要点及典型例题分析: 1.加法原理和乘法原理 两个原理是理解排列组合的概念,推导排列数及组合数公式,分析和解决 排列组合的应用问题的基本原则和依据;完成...

组合公式及证明

组合公式证明_数学_自然科学_专业资料。组合公式证明第十讲一、知识概要 组合恒等式 数学竞赛中组合数计算和组合恒等式的证明,是以高中排列、组合、二项式定理为...

全错位排列公式

全错位排列公式_数学_自然科学_专业资料。关于排列组合问题之全错位排列递推公 式推导!把编号 1---n 的小球放到编号 1---n 的盒子里,全错位排列(1 号球...

排列组合公式 | 排列组合公式证明 | 排列组合公式大全 | 排列组合公式算法 | 组合公式推导 | 排列数公式 | 排列组合公式推导过程 | 二项式定理 |