排列与组合.doc

1、 1 预备知识 在概率的计算中经常要用到一些排列组合知识，也常常用到牛顿二项式定理。 这里罗列一些同学们在中学里已学过的有关公式，并适当作一点推广。 一 . 两个原理 1. 乘法原理 : 完成一项工作有 m个步骤，第一步有 1n 种方法，第二步有 2n 种方法， 第 m 步有 mn 种方法，且 完成该项工作 必须依次通过这 m个步 骤 ， 则完成该项工作一共有 1n 2n mn 种方法，这一原理称为乘法原理。 2. 加法原理 : 完成一项工作有 m种方式，第一种方式有 1n 种方法，第二种 方式有 2n 种方法，第 m种方式有 mn 种方法，且 完成该项工作 只需 选择这 m种方式中的一种 ，

2、则完成这项工作一共有 1n + 2n + + mn 种方法，这一原理称为加法原理。 二 . 排列 : 从 n 个元素里每次取出 r 个元素，按一定顺序排成一列，称为 从 n 个元素里每次取 r 个元素的排列 ，这里 n和 Z。均为正整数 (以 下同 )。 当这 n个元素全不相同时，上述的排列称为无重复排列，我 们关心的是可以做成多少个排列，即排列数。 对于无重复排列，要求当 时 rn 称为选排列，而当 r n 时称为全排列。我们记排列数分别为 即将全排列看成选排列的特例。 利用乘法原理不难得到 由阶乘的定义 2 由阶乘的定义 将上面的 n个不同的元素改为 n 类不同的元素，每一类元素 都有 无

3、数多个。今从这 n类元素中取出 r 个元素，这 r 个元素可 以有从同一类元素中的两个或两个以上，将取出的这 r 个元素 dl 成一列，称为从 n类元素中取出 r 个元素的可重复排列，排列数记 作 ，由乘法原理得 显然，此处 r 可以大于 n 例 3 将三封信投入 4个信箱，问在下列两种情形下各有几 种投法 ? 1)每个信箱至多只许投入一封信； 2)每个信箱允许投入的信的数量不受限制。 解 1)显然是无重复排列问题，投法的种数为 2)是可重复排列问题，投法的种数为 三、组合 从“个元素中每次取出 r 个元素，构成的一组，称为从 n 个元 素里每次取出 r 个元素的组合。 设这 n 个元素全不相

4、同，即得所谓无重复组合，我们来求组合数，记作 将一个组合中的 r 个元素作全排列，全排列数为 ， 所有组合中的元素作全排列，共有 个排列，这相当于从 n个元素里每次取 r 个元素的选排列，排列总数为 故有 3 性质 (2)的左端表示 从 中取出 r个的组合数。我们可以固定这 n十 1个元素中的任意一个，不妨固定 于是考察所有取 及 所有不取 。的组合数， 前者即从 个中取 r 1 个的组合数，而后者即 从 个中取 r个的组合数 类似于可重复排列，也有可重复组合，即从 n类不同元素中每次取出 r 个元素，这 r个 元素可以从同一类元素中取两个或两 例 4 掷两颗银子可以有多少种点子的排列 ?多少

5、种点子的 组合 ? 解 每颗银子各有六面，分别刻有 1， 2， 3， 4， 5， 6个点，掷出的 结果可以重复。 4 四、较复杂的排列、组合问题 问题 1，不全相异元素的全排列 将一个包含 n 个元素的整体分成 r 个有序的部分，其中 第一部分包含 1n 个元 素，第二部分包含 2n 个元素，第 r 部分包含 rn 个元素，分法数 共有 种，上式称为多项式系数。 例 5 将 15 名新生平均分配到三个班级中去，这 15 名新生中 有 3 名优秀生。问： 1)15 名新生平均分配到三个班级中有多少种 分法 ?2)每个班级各分配到一名优秀生有多少种分法 ?3)3名优 秀生分配在同一个班级有多少种分

6、法 ? 解 1)15 名新生平均分配到三个班级中的分法总数为 2)将 3 名优秀生分配到三个班级使每个班级都有一名优 秀生的分法共 3!种。对于其中每一种分法，其余 12名新生平均 5 到三个班级中的分法共有 种，由乘法原理不难得到每个 班级各分配到一名优秀牛的分法总数为 3)将 3 名优秀生分配在同一班级内的分法共有 3 种 (因 有 3 个班级 )。对于这每一种分法，其余 12 名新生的分法是将其 中的 2 名分配到已有 3 名优秀生的班级，而另二个班级各 5 名，因 此 分法数为 种，由乘法原理得 3 名优秀生分配在同一班级的分法总数为 例 ：将 3 个白球、 4个红球和 4 个黑球排成

7、一行如果颜色相同的球彼此不加区别， 问有多少种排法？ 解：有 种排法 问题 2，不全相异元素的组合 仍设 有 r种不同元素，第一种有 1n 个 元素，第二种有 2n 个元素，第 r 种有 rn 个元素，今从这 n个元 素中，每次取 ，其取法总数为下列乘积 例 6 由 词中的字母，每次择取 4个，共有几种 不同的选择法 ? 解 此词中有 8 种字母，其中包括 3个 a， 2个 m， 2个，以及 各一个，每次择取 4 个，故所求的取法数由 6 2 3 2 5 2 3 4 1 2( 1 ) ( 1 ) ( 1 ) 1 8 3 1 7 8 1 4 3x x x x x x x x x x x 例： 要

8、求某学生会主席指定一个委员会，包括 5名男 生和 3 名女生，在提供的候选人名单中有 10名男生和 7名女生。 问可能有多少个委员会可供他选择？ 解 在某一委员会中，如果改变委员的顺序 ，结果仍相同， 因此，这是一个求组合的问题。从 lo 名男生中，主席能选出每组 有 5 名男生的组合数为 5 5 组合与排列个元素的整体分成 r 个有序的部分，其中第一部分包含 Rt个元 素，第二部分包含 n2个元素，第 r 部分包含 n r 个元素，分法数 共有 组合与排列研究事物的分组与排列，在计算概串方面，它们 可以用来决定一切可能情况的总数以及有利情况数。 定义 5 8 每一个集合可以由给定事物的部分或

9、全体组成， 可以不管集合中事物的顺序则这一集合称作组合。 定义 5 9 事物的全部集合或部 分集合的每一种不同的顺序 或排列即称为排列。 例 5 14 在 A， B， C， D 四个字母中求每组三个字母的 (a) 组合数， (b)排列数。 解 (a)字母 A， B， C， D每组可以取三个，不计顺序，有以 下取法： ABC， ABD， ACD和 BCD。因此，共有 4 种组合，即 4 个物件中每次取三个共有 4种组合。 (b)如果还考虑顺序，在字母 A， B， C， D 中每组有三个， 共有以下排列： ABC， ACB， BAC， BCA， CAB， CBA， ABD， ADB， BAD， B

10、DA， DAB， DBA， ACD， ADC， CAD， CDA， DAC， DCA， BCD， BDC， CBD， CDB， DBC， DCB。 因此，共有 24种排列：即从 4 物件中每次取三个共有 24种排 7 列。 例 5 15 排列数。 解 求四物件在每次取 4 件时的 (a)组合数； (b)A， B， C， D 四个 字母的顺序数容易求出为 24，于是 4 物件每次取 4件有 24 种排列。 为了求出计算组合数与排列数的简易公式，我们首先考虑一 个特例，求 n个物件 (例如字母 )每组有 n项的排列数。 把这些排列都写出来，我们就可以看到第一个字母有 n种选 择；每一种选择对应于图

11、 5 3 中的一个分校图，这里表示的是 n 4 的情形。在选定第一个字母后 (例如 A)，在第二个字母就 余下 (n 1)种选择，于是对前面两个字母就有 n(n 1)种可能 的选择，与固 5 3中从左边顶端发散的分技数一样多的选择。在 前两个字母选定以后，对第三个字母还有 n 2 种选择，于是对前 三个字母就有 n(n 1)(n 2)种选择。继续这一过程，我们看 到对第 n个字母就只留有一种选择；因而 n 个字母有 n(n 1) (n 2)。 2 1 种排列法。 用符号 nI(读作“ n的阶乘” )表示前面 n个正 整数的乘积， 即 n！ n(n 1)(n 2) 2 1 (5 9) 用 Pn， n 表示 n个物件每组有 n个的排列数，我们已经表明 Pa， n n1 (5 10)