生成函数大杂烩
本文最后更新于:2022年10月10日 晚上
生成函数
大家都知道,生成函数是一类求解数列的方法。基本思想就是把数列
需要特地指出的是,上述有关级数的收敛问题,都是被一种称为形式收敛的理论系统严格解决的。也就是说不考虑
通常而言,会对递推数列使用生成函数进行求解。
生产函数通常分为普通生成函数,指数生成函数和狄利克雷生成函数三类,接下来会一一进行讨论。
普通生成函数
最一般的生成函数,我们定义
在这个定义下,组合数
值得指出的是,
一些运算性质
我们设
加法
显然
乘法(卷积)
从而
数列乘法
若
特殊的
Catalan数
Catalan数是一个使用生成函数可以解决的经典例子。因为生成函数的基本思想比较容易理解,所以使用一些例子来熟悉一下。
先给出Catalan数
所以我们定义
从而可以得到
所以我们得到
得到
从而可知
从上面的例子,我们可以看出使用普通生成函数求解数列的一般方法。这个方法是容易理解的,只是如何使用正确的变换来得到关于
正如在前面提到的,组合数的生成函数十分的优美简洁,所以普通生成函数跟组合类的计数问题有密不可分的联系。下面介绍一类经典的使用普通生成函数计数的组合类型的问题。
典中典1
给出一个命题:
从
证明:考虑等式右边
这类问题有一个经典的具体问题,如下
一个例子
从数量不限的苹果、香蕉、橘子和梨中,选取
解
就是上述命题的运用,可以看出
所以可以得到生成函数
可以看出这类问题中选取元素的顺序对答案是没有影响的,是一类组合问题
指数生成函数
对于普通生成函数,组合数可以得到一个优美简洁的函数,但对于另一个重要的计数数列,排列数,似乎就十分的复杂。所以引入一个指数生成函数,使用指数生成函数,排列数也可以得到一个优美简洁的结果。
首先给出定义,如下
我们考虑$a_k=(n)k=A_n^k
我们发现,结果确实十分优雅。
至于他为什么叫指数生成函数,我们考虑数列
类似的我们举一个例子来熟悉指数生成函数的计算过程
一些运算性质
我们设
加法
显然
乘法
从而
数列乘法
若
特殊的
Bell数
首先给出Bell数的递推定义
所以我们可以定义它的指数生成函数
我们发现如果能把分母上的
使用我们常微分方程的知识,可以容易得到
所以我们得到
所以我们得到
在这个例子中,我们可以发现使用指数生成函数求解数列的一般步骤和普通生成函数并没有什么太大的差别。但对于含有组合数的求和类的递推关系,我们更倾向于使用指数生成函数,因为可以去掉组合数的分子,并且得到另外一些指数生成函数形式的无穷级数。
正如前面提到的,排列数的指数生成函数非常简洁优美,所以指数生成函数与排列类计数问题有密不可分的联系。与普通生成函数类似,我们给出另一个类似的经典的排列类计数问题。
典中典2
给出另一个命题:
从
证明:对数列单独考虑,考虑
而等式右边
一个例子
有1,2,3,4能组成多少个五位数?要求这些五位数中1出现2次或3次,2至多出现1次,4出现偶数次
解
为了方便考虑,我们暂时不考虑具体的
可以看出来,在本问题中,
所以我们得到生成函数
从而我们得到
容易看出上述问题是一类排列问题
狄利克雷生成函数
除了普通生成函数和指数生成函数,还有一类狄利克雷生成函数。在数论中是十分重要的工具。
先给出狄利克雷卷积的定义,如下
对于数列
一些运算性质
我们设
乘法(Dirichlet卷积)
从而
方幂
的狄利克雷生成函数
由乘法性质容易推出
积性函数的狄利克雷生成函数
若
证明:
考虑
故
典中典3
给出一个命题,与普通生成函数和指数生成函数的颇为相似
Mobius反演的另一个证明
使用狄利克雷生成函数可以非常巧妙的证明Mobius反演,即
若
先求Mobius函数
又
从而
证明:设
则由上述乘法的性质,得到
总结
普通生成函数和指数生成函数可以用于求解很多计数问题,尤其是递推关系的求解;而狄利克雷生成函数在数论方向有极大的用处。
下一篇博客计划写Polya计数原理,从而更好的解决各种计数问题。
本博客所有文章除特别声明外,均采用 CC BY-SA 4.0 协议 ,转载请注明出处!