排列与组合
预备知识 在概率的计算中经常要用到一些排列组合知识，也常常用到牛顿二项式定理。 这里罗列一些同学们在中学里已学过的有关公式，并适当作一点推广。 一. 两个原理 1. 乘法原理: 完成一项工作有m个步骤，第一步有[pic]种方法，第二步有[pic]种方法，…， 第m步有[pic]种方法，且完成该项工作必须依次通过这m个步骤， 则完成该项工作一共有 [pic][pic]…[pic] 种方法，这一原理称为乘法原理。 2. 加法原理: 完成一项工作有m种方式，第一种方式有[pic]种方法，第二种 方式有[pic]种方法，…，第m种方式有[pic]种方法，且完成该项工作只 需 选择这m种方式中的一种，则完成这项工作一共有 [pic]+[pic]+…+[pic] 种方法，这一原理称为加法原理。 二. 排列: 从n个元素里每次取出r个元素，按一定顺序排成一列，称为 从n个元素里每次取r个元素的排列，这里n和Z。均为正整数(以 下同)。 当这n个元素全不相同时，上述的排列称为无重复排列，我 们关心的是可以做成多少个排列，即排列数。 对于无重复排列，要求当 [pic] 时 [pic] 称为选排列，而当 r＝n时称为全排列。我们记排列数分别为[pic] 即将全排列看成选排列的特例。 利用乘法原理不难得到 由阶乘的定义 [pic] 由阶乘的定义 [pic] [pic] 将上面的n个不同的元素改为n类不同的元素，每一类元素 都有无数多个。今从这n类元素中取出r个元素，这r个元素可 以有从同一类元素中的两个或两个以上，将取出的这r个元素dl 成一列，称为从n类元素中取出r个元素的可重复排列，排列数记 作[pic]，由乘法原理得 [pic] 显然，此处r可以大于n 例3 将三封信投入4个信箱，问在下列两种情形下各有几 种投法? 1)每个信箱至多只许投入一封信； 2)每个信箱允许投入的信的数量不受限制。 解 1)显然是无重复排列问题，投法的种数为 [pic] 2)是可重复排列问题，投法的种数为 [pic] 三、组合 从“个元素中每次取出r个元素，构成的一组，称为从n个元 素里每次取出r个元素的组合。 设这n个元素全不相同，即得所谓无重复组合，我们来求组合数，记作 [pic] 将一个组合中的r个元素作全排列，全排列数为 [pic]， 所有组合中的元素作全排列，共有 [pic] 个排列，这相当于从n个元素里每次取r个元素的选排列，排列总数为 [pic] 故有 [pic] [pic] 性质(2)的左端表示 [pic] 从 [pic] 中取出r个的组合数。我们可以固定这n十1个元素中的任意一个，不妨固定 [pic] 于是考察所有取[pic]及所有不取[pic]。的组合数， 前者即从[pic]个中取r—1个的组合数，而后者即 从[pic]个中取r个的组合数 [pic] 类似于可重复排列，也有可重复组合，即从n类不同元素中每次取出r个元素，这r个 元素可以从同一类元素中取两个或两 [pic] 例4 掷两颗银子可以有多少种点子的排列?多少种点子的 组合? 解 每颗银子各有六面，分别刻有1，2，3，4，5，6个点，掷出的 结果可以重复。 [pic] 四、较复杂的排列、组合问题 问题1，不全相异元素的全排列 [pic]将一个包含n 个元素的整体分成r个有序的部分，其中第一部分包含[pic]个元 素，第二部分包含[pic]个元素，…，第r部分包含[pic]个元素，分法数 共有 [pic] 种，上式称为多项式系数。 例5 将15名新生平均分配到三个班级中去，这15名新生中 有3名优秀生。问：1)15名新生平均分配到三个班级中有多少种 分法?2)每个班级各分配到一名优秀生有多少种分法?3)3名优 秀生分配在同一个班级有多少种分法? 解 1)15名新生平均分配到三个班级中的分法总数为 [pic] 2)将3名优秀生分配到三个班级使每个班级都有一名优 秀生的分法共3!种。对于其中每一种分法，其余12名新生平均 到三个班级中的分法共有[pic]种，由乘法原理不难得到每个 班级各分配到一名优秀牛的分法总数为 [pic] 3)将3名优秀生分配在同一班级内的分法共有3种(因 有3个班级)。对于这每一种分法，其余12名新生的分法是将其 中的2名分配到已有3名优秀生的班级，而另二个班级各5名，因 此分法数为[pic]种，由乘法原理得3名优秀生分配在同一班级的分法总数为 [pic] 例 ：将3个白球、4个红球和4个黑球排成一行．如果颜色相同的球彼此不加区别， 问有多少种排法？ 解：有 [pic] 种排法 问题2，不全相异元素的组合 仍设[pic]有r种不同元素，第一种有[pic]个 元素，第二种有[pic]个元素，…，第r种有[pic]个元素，今从这n个元 素中，每次取[pic]，其取法总数为下列乘积 [pic] 例6 由[pic]词中的字母，每次择取4个，共有几种 不同的选择法? 解 此词中有8种字母，其中包括3个a，2个m，2个，以及 [pic] 各一个，每次择取4个，故所求的取法数由 [pic] [pic] ∴[pic] 例： 要求某学生会主席指定一个委员会，包括5名男 生和3名女生，在提供的候选人名单中有10名男生和7名女生。 问可能有多少个委员会可供他选择？ 解 在某一委员会中，如果改变委员的顺序，结果仍相同， 因此，这是一个求组合的问题。从lo名男生中，主席能选出每组 有5名男生的组合数为 5．5 组合与排列个元素的整体分成r个有序的部分，其中第一部分包含Rt个元 素，第二部分包含n2个元素，…，第r部分包含n r个元素，分法数 共有 组合与排列研究事物的分组与排列，在计算概串方面，它们 可以用来决定一切可能情况的总数以及有利情况数。 定义5—8 每一个集合可以由给定事物的部分或全体组成， 可以不管集合中事物的顺序则这一集合称作组合。 定义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，BDA，DAB，DBA，ACD，ADC，CAD， CDA，DAC，DCA，BCD， BDC， CBD，CDB，DBC，DCB。 因此，共有24种排列：即从4物件中每次取三个共有24种排 列。 例5—15 排列数。 解 求四物件在每次取4件时的(a)组合数； (b)A，B，C，D四个 字母的顺序数容易求出为24，于是4 物件每次取4件有24种排列。 为了求出计算组合数与排列数的简易公式，我们首先考虑一 个特例，求n个物件(例如字母)每组有n项的排列数。 把这些排列都写出来，我们就可以看到第一个字母有n种选 择；每一种选择对应于图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) [pic]
排列与组合