指数型母函数

更新时间:2024-05-21 14:34

普通型母函数主要是来求组合的方案数,而指数型母函数是求多重排列数。

问题引出

指数型母函数问题:

假设有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)= +

为序列{ }的指数型母函数

举例:

设n是正整数。确定下列数列的指数生成函数

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)的指数生成函数。

免责声明
隐私政策
用户协议
目录 22
0{{catalogNumber[index]}}. {{item.title}}
{{item.title}}