[概率论]排列组合
排 列
一般地说,从 n个不同元素中,任取m(m≤n)个元素,按照一定的顺序排成一列,这就叫做从n 个元素中取出m 个元素的一个排列。
例如:已知 a、b 、c 、d 这四个元素,
写出每次取出3个元素的所有排列。 对于初学者可以先画下图来算出:
共 24个排列,这个数值24是可以根据乘法原理算出来的。数学中的乘法原理为:做一件事,完成它需要分成几个步骤,做第一步有m 1种不同的方法,做第二步有m 2种不同的方法„„,做第n 步有m n 种不同的方法,那么完成这件事共有N =m 1×m2×m3ׄ„×mn 种不同的方法。据此从a 、b 、c 、d 这四个元素中每次取出三个排成三位数的方法共有N =4×3×2=24种。
数学中有一个排列数公式:
从 n个不同元素中取出m(m≤n)个元素的所有排列的个数,叫做从n 个不同元素中取出m 个元素的排列数。用符号P n m 表示,(P
是“排列”一词的英文Permutation 的第一个字母) ,在数学课本中根据乘法原理可推出排列数的公式为:
P =n (n -1)(n -2) m
n (n -m +1)
公式中的 n,m∈N,且m ≤ n
例如:从 8个元素中每次取3个元素出来排
列,所得的排列数则为
P8=8×(8-1)(8-2)
=8×7×6
=336
例如:从 8个元素中每次取5个元素出来排
列所得的排列数为
5P8=8×(8-1)×(8-2)× (8-3)×(8-4)
=8×7×6×5×4
=6720
在排列数公式中,当 m=n 时,有: 3
P =n (n -1)(n -2) n
n 2⋅1 这表明, n个不同元素全部取出来排列的排列数等于自然数1到n 的连乘积。n 个不同元素,全部取出的一个排列叫做n 个不同元素的一个全排列。自然数1到n 的连乘积叫做n 的阶乘,用n! 表示,所以n 个不同元素的全排列数公式则为:
P =n !
前面所讲的排列数公式可作如下变形: n n
P =n (n -1)(n -2) m
n (n -m +1)
2⋅1n (n -1)(n -2) (n -m +1)(n -m ) =(n -m ) 2⋅1
n ! =(n -m )!
(注意:为了使这个公式在m =n 时也成立,我们规定0! =1) 例如,从8个元素中全部取出来的排列数则为:8的阶乘。
8! =P =8⨯7⨯6⨯5⨯4⨯3⨯2⨯1 =40320
88
组 合
一般地说,从 n个不同元素中,任取m(m≤n)个元素出来拼成一组,就叫做从n 个不同元 素中取出m 个元素的一个组合。
从 n个不同元素中取出m(m ≤ n)个元素的所有组合的个数,就叫做从n 个不同元素中取出m 个元素的组合数,用符号C m
n 表示,C
是“组合”的英文Combination 的第一个字 母。
前面讲到的从 a、b 、c 、d 这四个元素中取3 个元素出来的排列与组合的关系如下
组合数 排列数
由上分析可以看出,对于每一个组合都有 6个不同的排列,因此,求从4个不同元素中
3取3个元素出来排列的排列数为P 4,可接下
列两步来考虑。
第一步:从 4个不同元素中取出3
3个元素作组合,共有C 4=4个组合;
第二步:对每一个组合中的 3个不
3同元素作全排列,各有P 3=6个排列。
这样,再根据乘法原理即得:
P =C ⨯P 3
43433
一般地说,求从 n个不同元素中取出m 个元素排列的排列数为P n m ,可按下列两步来考
虑:
第一步:先求出从这 n个不同的元
m 素中取出m 个元素的组合数为C n ;
第二步:求每一个组合中 m个不同
m 元素的全排列数P m 。根据乘法原理则得到:
P =C ⨯P
m
n m n m
m m n m n m m P n (n -1)(n -2) (n -m +1) C ==P m !
n ! =m !(n -m )!
例如:从 8个元素中每次取3个元素出来组
合所得的组合数为:
例如:从
例如:从
显见,这个组合数与前面从 4个元素中每次取3个元素出来组合所得的组合数为:
8个不同元素中每次取5个元素出来组合所得的组合数为:
8个不同元素中
每取3个元素出来组合所得的组合数
是相等的,即C 8=C8,
因此有公式:C m
n 53=C n -m (性质n 1)
(注意:为了使这个公式在n =m 时也成立,
0我们规定C n =1)
此外,组合数还有另一个性质为:
C m
n +1=C +C m n m -1 (性质n 2) 。
9832例如:计算 C100和C 20+C 20
解:由组合数的性质1可得:
而由组合数的性质2可得: