《排列与组合.docVIP

预备知识 　　　 在概率的计算中经常要用到一些排列组合知识，也常常用到牛顿二项式定理。 　　　　这里罗列一些同学们在中学里已学过的有关公式，并适当作一点推广。 　　　　 一. 两个原理 1. 乘法原理: 完成一项工作有m个步骤，第一步有种方法，第二步有种方法，...， 　　　　　　　第m步有种方法，且完成该项工作必须依次通过这m个步骤， 　　　　　　　则完成该项工作一共有 ... 　　　　　　　　　种方法，这一原理称为乘法原理。 2. 加法原理: 完成一项工作有m种方式，第一种方式有种方法，第二种 　　　　　　　　　方式有种方法，...，第m种方式有种方法，且完成该项工作只需 　　　　　　　　　选择这m种方式中的一种，则完成这项工作一共有 ++...+ 　　　　　　种方法，这一原理称为加法原理。 二. 排列: 从n个元素里每次取出r个元素，按一定顺序排成一列，称为 从n个元素里每次取r个元素的排列，这里n和Z。均为正整数(以 下同)。 当这n个元素全不相同时，上述的排列称为无重复排列，我 们关心的是可以做成多少个排列，即排列数。 对于无重复排列，要求当 时 称为选排列，而当 r＝n时称为全排列。我们记排列数分别为 即将全排列看成选排列的特例。 利用乘法原理不难得到 由阶乘的定义 由阶乘的定义 将上面的n个不同的元素改为n类不同的元素，每一类元素 都有无数多个。今从这n类元素中取出r个元素，这r个元素可 以有从同一类元素中的两个或两个以上，将取出的这r个元素dl 成一列，称为从n类元素中取出r个元素的可重复排列，排列数记 作，由乘法原理得 显然，此处r可以大于n 例3 将三封信投入4个信箱，问在下列两种情形下各有几 种投法? 　1)每个信箱至多只许投入一封信； 　2)每个信箱允许投入的信的数量不受限制。 解 1)显然是无重复排列问题，投法的种数为 　　　　　　 2)是可重复排列问题，投法的种数为 三、组合 从个元素中每次取出r个元素，构成的一组，称为从n个元 素里每次取出r个元素的组合。 　　设这n个元素全不相同，即得所谓无重复组合，我们来求组合数，记作 　　　　　　 　　将一个组合中的r个元素作全排列，全排列数为 　　　　　　　　， 　　　　　所有组合中的元素作全排列，共有 　　　　　　　　　　　　　 　　　　 个排列，这相当于从n个元素里每次取r个元素的选排列，排列总数为 　　　　　　　　　　　　 　　　　故有 　　　 　　　　　 性质(2)的左端表示 　　　　　　　　　　 　　　从 　　　　　　　　　 　　　　中取出r个的组合数。我们可以固定这n十1个元素中的任意一个，不妨固定 　　　　　　　　 　　　于是考察所有取及所有不取。的组合数， 　　　前者即从个中取r-1个的组合数，而后者即 从个中取r个的组合数 　　　　 类似于可重复排列，也有可重复组合，即从n类不同元素中每次取出r个元素，这r个 元素可以从同一类元素中取两个或两 　 例4 掷两颗银子可以有多少种点子的排列?多少种点子的 组合? 解 每颗银子各有六面，分别刻有1，2，3，4，5，6个点，掷出的 结果可以重复。 　　　　　 四、较复杂的排列、组合问题 问题1，不全相异元素的全排列 将一个包含n 个元素的整体分成r个有序的部分，其中第一部分包含个元 素，第二部分包含个元素，...，第r部分包含个元素，分法数 共有 　　 种，上式称为多项式系数。 例5 将15名新生平均分配到三个班级中去，这15名新生中 有3名优秀生。问：1)15名新生平均分配到三个班级中有多少种 分法?2)每个班级各分配到一名优秀生有多少种分法?3)3名优 秀生分配在同一个班级有多少种分法? 　　解 1)15名新生平均分配到三个班级中的分法总数为 　　 　　 2)将3名优秀生分配到三个班级使每个班级都有一名优 秀生的分法共3!种。对于其中每一种分法，其余12名新生平均 到三个班级中的分法共有种，由乘法原理不难得到每个 班级各分配到一名优秀牛的分法总数为 3)将3名优秀生分配在同一班级内的分法共有3种(因 有3个班级)。对于这每一种分法，其余12名