1. 圆排列
圆排列个数 =P(n, r)/r= n!/( r*(n-r)! )
例:8人围着餐桌吃饭,多少种就座方式?
Ans: P(8, 8)/8=7!
2. 重排列
a. 无限重排列:n个不同元素中取r个按次序排列,每个元素可取无限次,总数为nr。
b. 有限重排列:r个不同色彩球放入n个标号的盒子,第i种彩球有ri个,总数为P(n, r) / (r1!* r2!*… rt!)
3. 非重组合:每个元素最多出现一次
C(n, r)
4. 重组合
N个不同的元素中取r个元素,允许重复取,不考虑顺序。总数为C(n+r-1, r)
5. 母函数
a. 引出:
(x1+ x2+… +xk)n的组合数学意义是将n个无区别的球放入k个编号不同的盒子里,每个盒子球数不限。多项式展开后,x1n1 *x2n2*…* xknk通过幂可以表示一组解。而这个项的系数为
C(n, n1)* C(n-n1, n2)*…* C(n-n1-n2-…-nk-1, nk)=n!/ (n1!n2!…nk! )
各系数之和为kn。
b. 普通母函数
一个序列{an},称a0+a1x+ a2x2+…+ anxn+…这个多项式为{an}的普通母函数。
例1:(天平称物问题)有质量n1,n2…nk整数克的砝码,要称i克物体,物体在左,砝码在右。共有多少种不同的称法?
解:设有ai种方法,则
(1+xn1) (1+xn2)…(1+xnk)=∑ ai xi
1表示(1+xnj)中提供1,砝码nj没有用上。
ai为所求。
注:多项式展开后,还可以看出能称出哪些重量
经验:始终记得,一个括号内一次仅有一个项被取,用于提供给展开式的某一项
例2:(重复取物)有n种不同的物品,每种物品分别能最多取b1,b2… bn件。从中可重复的取r件物品有多少种不同的取法?
解:设有ar种不同的取法。则
(1+x+x2+…+xb1) (1+x+x2+…+xb2)… (1+x+x2+…+xbn)=a0+a1x+ a2x2+…+ arxr+…
展开式中xr的来源xm1xm2…xmn=xr
于是成了重组合问题,答案为C(n+r-1, r)
例3:整数拆分:整数r拆分成k1,k2… km的和,ki允许最多重复ni次。求拆分方案数。
解:这是求k1b1+ k2b2+…+ kmbm=r的不定方程的非负整数解的个数,0<= bi<= ni 。
考虑(1+xk1+xk1*2+xk1*3+…+xk1*n1)( 1+xk2+xk2*2+xk2*3+…+xk2*n2)…( 1+xkn+xkn*2+xkn*3+…++xkm*nm)
则答案是xr的系数
c. 指数母函数
N个元素中,ai重复了ni次,求从中取r个元素的排列数为br。
设取mi个ai,∑mi=r。则相互不同的排列数为r! / ∏mi!
则对于所有的mi的拆分方法,br=∑( r! / ∏mi! )
例4:若有8个元素,其中a1重复了3次,a2重复了2次,a3重复了3次。求从中取出4个元素的排列数。
解:先构造普通母函数
G(x)=(1+x+ x2+x3) (1+x+ x2) (1+x+ x2+x3)
X4的系数为10,说明取4个元素的组合数为10。这相当于上面所说的对于mi的拆分方法。
4 = 1+0+3 = 0+1+3 = 2+0+2 = 1+1+2 = 0+2+2 = 3+0+1 = 2+1+1 = 1+2+1 = 3+1+0 = 2+2+0
代入br=∑( r! / ∏mi! ),得到70种
为了便于计算br,引入函数
g(x)= (1+x+x2/2!+x3/3!+…+xn1/n1!) (1+x+x2/2!+x3/3!+…+xn2/n2!)… (1+x+x2/2!+x3/3!+…+xnk/nk!)=∑ (br*xr/r!)
g(x)称为{br}的指数母函数。br=∑( r! / ∏mi! )
posted on 2011-04-13 18:05
mr_chen 阅读(653)
评论(1) 编辑 收藏 引用 所属分类:
算法笔记