一 排列
1.从n个元素中取r个元素排列的全体数目
Pnr=P(n,r)=n(n-1)(n-2)...(n-r+1)=n!/(n-r)! :例:n个球取r个放入r个不同盒子,每个盒子一个球,多少种放法
2. n个元素的全排列
Pnn=P(n,n)=n!
3.例:随机选n(n<365)个人,求其中至少有两人生日相同的概率。
n个人的生日的序列数:365n
n个人生日均不相同的概率:P(365,n)
故:1-P(365,n)/365n
4.圆排列
从n个元素中取r个元素沿一圆周排列
Qnr=Pnr/r (取r个元素作排列的结果与圆排列的结果比较,每个排列重复了r次)
同理:Qnn= n!/n =(n-1)!
二 组合
r:从n个元素中取r个元素排列而不考虑顺序;
如:n个球取r个放入r个盒子,r个盒子是相同的。
若在每种组合结果的基础对盒子排列,便得到n取r的排列,则:
Cnrr! =Pnr故 Cnr=Pnr/r! = n!/(n-r)!r!
2 分组
有a1,a2...a8八位成员,两两配对,分成4组,试求方案N
方法一:依次选择: a1选择同样有7种选择,余下6人中一人,选择同样有5种选择,余下4个,其中一个选择同样有3种可能; N=7*5*3
方法二:全排列与分组(组内,组间):
将8个成员全排列,共8!种可能;若分成4组,{12}{34}{56}{78},若在组内位置互换,对于选择同样没有影响,则全排列中选择同样有重复,重复数:2n
同时,4组之间的排列也不影响同样关系,故全排列中对同样关系也有重复,重复数:4!
故得 8!/(2n*4!)
方法三:先分组,再组内
8个人分成4组,第1组有C82种选择,第2组有C62种选择,同理第3组有C42种选择; 且组的顺序无关
N= C82* C62*C42 * C22/4! =105
3 允许重复的组合
定理1:在n个不同元素中取r个进行组合,允许重复(r个元素中元素是可重复的),组合数:Cn+r-1r
定理2:将r个无区别的球,放入n个有标志的盒子,每个盒子中可多于一个,则共有Cn+r-1r 种方案
例:(x+y+z)4共有多少项:
相当于 将4个球,放入3个盒子里,而且每个盒子中的数目不限。如 X4 可理解为将4个球都放入盒子X中。
N=C(n+r-1,r)=C(3+4-1,4)=C(6,4)=15
4 不相邻的组合
指:从序列A={1,2,....n}中取r个,其中不存在,i,i+1两个相邻数同时出现于一个组合中的组合。
定理: 从序列A={1,2,....n}中取r个作不相邻组合,其中组合数为:Cn-r-1r
三 母函数-幂级数
定义:设 a0,a1,a2...an是一个数列,定义它的母函数为幂级数 ——————————解决元素重复的组合问题
fa(x)=(1+x)a=C(a,0)X0+C(a,1)X1+C(a,2)X2+C(a,3)X3+.....+C(a,n)Xn+
母函数与其他母函数存在的关系式:
A(x)= 1/(1-x) = 1+X+X2+X3+.....+Xn+
B(x)=1/(1-x)2=A(x)/(1-x) =1+2X+3X2+4X3+.....+nXn-1
C(x)=1/(1-x)3=B(x)/(1-x) =1+3X+6X2+10X3+.....+
应用:
例1:红球两个,白球,黄球各一个,试问有多少种不同的组合数
利用:fa(x)=(1+x)a=C(a,0)X0+C(a,1)X1+C(a,2)X2+C(a,3)X3+.....+C(a,n)Xn+ 其中每一项 指数表示选择数,系数表示该该选择的方案数。
令r个球组合数为Cr,则 C0 ,C1,C2,C3,C4的母函数:
G(x)=( 1+x+x2)(1+x)(1+x)=1+3x+4x2+3x3+x4
1+x+x2表示第红球选0个,选一个,选两个
共有:1+3+4+3+1=12种不同组合数。
由4x2表示选2个球的组合数为4;3x表示选1个球的组合数
例2 :若有1g,2g,3g,4g的砝码各一枚,问能称出几种可能的重量。
利用:fa(x)=(1+x)a=C(a,0)X0+C(a,1)X1+C(a,2)X2+C(a,3)X3+.....+C(a,n)Xn+ 其中每一项 指数表示重量,系数表示该重量的方案数。
母函数为:G(x)=(1+x)( 1+x+x2)( 1+x+x2+x3)( 1+x+x2+x3+x4)
将系数相加,可得答案。
例3: 若有1g的砝码3枚,2g的砝码4枚,4g的砝码2枚,问能称出哪些重量,各有几种方案。
G(x)=(1+x+x2+x3)( 1+x2+x4+x6+x8) (1+x4+x8)
四 母函数—指数型
定义:设 a0,a1,a2...an是一个数列,定义它的母函数为指数型母函数: —— 解决元素重复的排列问题
fa(x)=(1+x)a=C(a,0)X0+C(a,1)X1/1!+C(a,2)X2/2!+C(a,3)X3/3!+.....+C(a,n)Xn/n!+
例1:
8个元素,a1重复3次,a2重复2次,a3重复3次,从中取r个组合,其组合数的母函数:
G(x)=(1+x+x2+x3)( 1+x2)(1+x+x2+x3)=1+3x+6x2+9x3+10x4+9x5+6x6+3x7+x8
可得到,若取4个元素进行组合有10种方案。 若需要取4个元素进行排列呢:问题就转化为从8个元素取4个进行排列,其排列数应是每种组合的排列。
如:x1x33表示1个a1,3个a3; 那么它对应的排列数为 4!/1!3! ;
由:
Cnr=Pnr/r!
Ge(x)=(1+x/1!+x2/2!+x3/3! )( 1+x/1!+x2/2!)(1+x/1!+x2/2!+x3/3! )=
1+ 3X/1! + 9x2/2! + 28x3/3! + 70x4/4! + 170x5/5!+ 350x6/6!+ 560x7/7!+ 560x8/8!
这里取K的排列数应该是K!.故取4个的排列数应是:70;
例: a1,a2...a7为7个有区别的球,将它们放入4个有标志的盒子,要求第1,2两个盒子必须含偶数个数,第3个盒子含有奇数个数。 有多少放法
可理解为从1,2,3,4这4个数字中取7个作允许重复的排列————元素重复的排列
例:求1,3,5,7,9 这5个数字组成的n位数的个数,要求其中3和7出现的次数为偶数,其他数字出现的次数无限制。
来源:/dan-cnblogs/p/4733721.html