122 指数型生成函数.ppt
《122 指数型生成函数.ppt》由会员分享,可在线阅读,更多相关《122 指数型生成函数.ppt(14页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、12.2 指数型生成函数,用生成函数可以解决组合计数问题,那么是否可用来解决排列问题?注意到组合计数问题,多重集S=a1,a2, ak的r-组合数是C(r+k-1,r),数列C(r+k-1,r)的生成函数,收敛于初等函数,而对于集合a1,a2,an的r-排列数为p(n,r), 数列p(n,r)的生成函数,其收敛和函数不能表示为初等函数,因此无法直接应用。但因为C(n,r)=p(n,r)/r!,所以,对排列数的生成函数可考虑用这样的幂级数,指数型生成函数,定义12.2:设a0,a1,an,是一个数列,构造形式幂级数,称f(x)是数列a0,a1,an,的指数型生成函数为什么要称指数型生成函数?因为
2、,与上述幂级数类似。,根据定义知,指数型生成函数与幂级数型生成函数的一般项仅相差一个因子1/n!只要令 ar=ar/r!,则ar的幂级数型生成函数就是ar的指数型生成函数,因此由定理12.1易得指数型生成函数的性质。定理12.2:设an,bn的指数生成函数分别为fe(x)和ge(x),则:,对于an=1的数列1,它的指数型生成函数为:,现在用指数型生成函数来解决多重集的排列问题。定理12.3:设有限多重集n1a1,n2a2, nkak,且n=n1+n2+nk,对任意的非负整数r,ar为S的r-排列数,则数列ar的指数型生成函数为:g(x)=gn1(x)g n2(x)gnk,其中gni(x)=1
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 指数 生成 函数
限制150内