预备知识
在概率的计算中经常要用到一些排列组合知识,也常常用到牛顿二项式定理。 这里罗列一些同学们在中学里已学过的有关公式,并适当作一点推广。
一. 两个原理 1.
乘法原理: 完成一项工作有m 个步骤,第一步有1n 种方法,第二步有2n 种方法,…,
第m 步有m n 种方法,且完成该项工作必须依次通过这m 个步骤, 则完成该项工作一共有
1n 2n …m n
种方法,这一原理称为乘法原理。
2. 加法原理: 完成一项工作有m 种方式,第一种方式有1n 种方法,第二种
方式有2n 种方法,…,第m 种方式有m n 种方法,且完成该项工作只需 选择这m 种方式中的一种,则完成这项工作一共有
1n +2n +…+m n
种方法,这一原理称为加法原理。
二. 排列:
从n 个元素里每次取出r 个元素,按一定顺序排成一列,称为 从n 个元素里每次取r 个元素的排列,这里n 和Z 。均为正整数(以 下同)。
当这n 个元素全不相同时,上述的排列称为无重复排列,我 们关心的是可以做成多少个排列,即排列数。
对于无重复排列,要求当 时 r 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个有序的部分,其中第一部分包含
n个元
1
素,第二部分包含2n 个元素,…,第r 部分包含r n 个元素,分法数 共有
种,上式称为多项式系数。
例5 将15名新生平均分配到三个班级中去,这15名新生中 有3名优秀生。问:1)15名新生平均分配到三个班级中有多少种 分法?2)每个班级各分配到一名优秀生有多少种分法?3)3名优 秀生分配在同一个班级有多少种分法?
解 1)15名新生平均分配到三个班级中的分法总数为
2)将3名优秀生分配到三个班级使每个班级都有一名优 秀生的分法共3!种。对于其中每一种分法,其余12名新生平均 到三个班级中的分法共有种,由乘法原理不难得到每个 班级各分配到一名优秀牛的分法总数为
3)将3名优秀生分配在同一班级内的分法共有3种(因
有3个班级)。对于这每一种分法,其余12名新生的分法是将其 中的2名分配到已有3名优秀生的班级,而另二个班级各5名,因 此分法数为种,由乘法原理得3名优秀生分配在同一班级的分法总数为
例 :将3个白球、4个红球和4个黑球排成一行.如果颜色相同的球彼此不加区别,
问有多少种排法? 解:有
种排法
问题2,不全相异元素的组合
仍设
有r 种不同元素,第一种有1n 个
元素,第二种有2n 个元素,…,第r 种有r n 个元素,今从这n 个元 素中,每次取
,其取法总数为下列乘积
例6 由词中的字母,每次择取4个,共有几种 不同的选择法?
解 此词中有8种字母,其中包括3个a ,2个m ,2个,以及
各一个,每次择取4个,故所求的取法数由
∴2
3
2
5
2
3
4
12
(1)(1)(1)183178143x x x x x x x x x x x ++++++=++++++L 例: 要求某学生会主席指定一个委员会,包括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每组可以取三个,不计顺序,有以
下取法:AB C,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)