普通型母函数主要是来求组合的方案数,而指数型母函数是求多重排列数。
问题引出
指数型母函数问题:
假设有n个元素,其中a1,a2,····,an互不相同,进行全排列,可得n!个不同的排列。若其中某一元素a1重复了n1次,全排列出来必有重复元素,其中真正不同的排列数应为n!/n1!,即其重复度为n1!
同样理由a1重复了n1次,a2重复了n2次,····,ak重复了nk次,n1+n2+····+nk=n。对于这样的n个元素进行全排列,可得不同排列的个数实际上是
定义
对于序列a0,a1,a2,····定义
Ge(x)= +
为序列{ }的指数型母函数
举例:
p(n,0),p(n,1),p(n,2),…,p(n,n)
其中p(n,k)表示n元素的k排列的数目,因此对于k=0,1,2,…,n,这个排列的数目是n!/(n-k)!。因此指数生成函数是:
因此是数列p(n,0),p(n,1),p(n,2),…,p(n,n)的指数生成函数。