posts - 14,  comments - 4,  trackbacks - 0

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 阅读(393) 评论(1)  编辑 收藏 引用 所属分类: 算法笔记

FeedBack:
# re: 母函数,排列组合笔记
2011-04-13 20:43 | 李金福
哥,我崇拜你   回复  更多评论
  

只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


<2020年8月>
2627282930311
2345678
9101112131415
16171819202122
23242526272829
303112345

常用链接

留言簿

随笔档案(14)

文章分类(8)

文章档案(11)

搜索

  •  

最新评论

阅读排行榜

评论排行榜