生成函数大杂烩

本文最后更新于:2022年10月10日 晚上

生成函数

大家都知道,生成函数是一类求解数列的方法。基本思想就是把数列an作为幂级数n=0anxnf(x)的系数,得到有关f(x)的关系式,然后求得f(x)的解析表达式,从而再进一步使用幂级数展开求得an的表达式的方法。

需要特地指出的是,上述有关级数的收敛问题,都是被一种称为形式收敛的理论系统严格解决的。也就是说不考虑x的定义域问题。

通常而言,会对递推数列使用生成函数进行求解。

生产函数通常分为普通生成函数,指数生成函数和狄利克雷生成函数三类,接下来会一一进行讨论。

普通生成函数

最一般的生成函数,我们定义
f(x)=n=0anxn
在这个定义下,组合数ak=(nk)可以得到一个很好的生成函数f(x)=(1+x)n.

值得指出的是,1的普通生成函数是f(x)=11x

一些运算性质

我们设的普通生成函数

加法

显然的普通生成函数

乘法(卷积)

从而的生成函数

数列乘法

为一多项式函数,则的普通生成函数为,其中这个运算

特殊的的普通生成函数为

Catalan数

Catalan数是一个使用生成函数可以解决的经典例子。因为生成函数的基本思想比较容易理解,所以使用一些例子来熟悉一下。

先给出Catalan数的递推定义

所以我们定义

从而可以得到

所以我们得到,从而,又,所以取负号

得到

从而可知

从上面的例子,我们可以看出使用普通生成函数求解数列的一般方法。这个方法是容易理解的,只是如何使用正确的变换来得到关于的关系是需要一定技巧的,也是有一定难度的。

正如在前面提到的,组合数的生成函数十分的优美简洁,所以普通生成函数跟组合类的计数问题有密不可分的联系。下面介绍一类经典的使用普通生成函数计数的组合类型的问题。

典中典1

给出一个命题:

元集中选取个元的组合数为,其中要求出现的次数集为,则的生成函数

证明:考虑等式右边的展开式中项的系数,可以看出前面的系数即为的解的个数,其中

这类问题有一个经典的具体问题,如下

一个例子

从数量不限的苹果、香蕉、橘子和梨中,选取个水果装成一袋,且选取的苹果数是偶数,香蕉数是5的倍数,橘子至多有4个,梨至多有1个。这样的装法共有多少种?

就是上述命题的运用,可以看出

所以可以得到生成函数,所以所求数列

可以看出这类问题中选取元素的顺序对答案是没有影响的,是一类组合问题

指数生成函数

对于普通生成函数,组合数可以得到一个优美简洁的函数,但对于另一个重要的计数数列,排列数,似乎就十分的复杂。所以引入一个指数生成函数,使用指数生成函数,排列数也可以得到一个优美简洁的结果。

首先给出定义,如下

我们考虑$a_k=(n)k=A_n^kf(x)=\sum\limits{k=0}^n(n)k\frac{x^k}{k!}=\sum\limits{k=0}^n{n \choose k}x^k=(1+x)^n$

我们发现,结果确实十分优雅。

至于他为什么叫指数生成函数,我们考虑数列,可以得到,得到的是指数函数,所以被称为指数生成函数。

类似的我们举一个例子来熟悉指数生成函数的计算过程

一些运算性质

我们设的指数生成函数

加法

显然的生成函数

乘法

从而的生成函数

数列乘法

为一多项式函数,则的普通生成函数为,其中这个运算

特殊的的普通生成函数为

Bell数

首先给出Bell数的递推定义

所以我们可以定义它的指数生成函数,得到

我们发现如果能把分母上的去掉,就可以得到关于的关系式了,如果对原本的式子求导,就可以去掉,所以我们现在考虑对生成函数求导,得到

使用我们常微分方程的知识,可以容易得到,又,故

所以我们得到

所以我们得到

在这个例子中,我们可以发现使用指数生成函数求解数列的一般步骤和普通生成函数并没有什么太大的差别。但对于含有组合数的求和类的递推关系,我们更倾向于使用指数生成函数,因为可以去掉组合数的分子,并且得到另外一些指数生成函数形式的无穷级数。

正如前面提到的,排列数的指数生成函数非常简洁优美,所以指数生成函数与排列类计数问题有密不可分的联系。与普通生成函数类似,我们给出另一个类似的经典的排列类计数问题。

典中典2

给出另一个命题:

元集中选取个元的排列数为,其中要求出现的次数集为,则的指数生成函数

证明:对数列单独考虑,考虑恰取的排列数为

而等式右边的系数为,也就意味着前的系数

一个例子

有1,2,3,4​能组成多少个五位数?要求这些五位数中1出现2次或3次,2至多出现1次,4出现偶数次

为了方便考虑,我们暂时不考虑具体的,转而考虑求得一般的的生成函数。

可以看出来,在本问题中,

所以我们得到生成函数

从而我们得到

容易看出上述问题是一类排列问题

狄利克雷生成函数

除了普通生成函数和指数生成函数,还有一类狄利克雷生成函数。在数论中是十分重要的工具。

先给出狄利克雷卷积的定义,如下

对于数列,它的狄利克雷生成函数就是著名的Riemann-Zeta函数

一些运算性质

我们设的狄利克雷生成函数

乘法(Dirichlet卷积)

从而的生成函数

方幂

是数列

的狄利克雷生成函数

由乘法性质容易推出

积性函数的狄利克雷生成函数

为积性函数,则的狄利克雷生成函数有如下形式(表示所有质数)

证明:

考虑的质因数分解,则中与有关的项为

的狄利克雷生成函数中的系数为

典中典3

给出一个命题,与普通生成函数和指数生成函数的颇为相似

生成了的所有可分解为个有序正因子积的方法,而生成了的可分解为个有序非平凡正因子(每个都大于1)积的方法数

Mobius反演的另一个证明

使用狄利克雷生成函数可以非常巧妙的证明Mobius反演,即

,则

先求Mobius函数的狄利克雷生成函数



从而

证明:设的狄利克雷生成函数为

则由上述乘法的性质,得到,从而,所以再由乘法的性质

总结

普通生成函数和指数生成函数可以用于求解很多计数问题,尤其是递推关系的求解;而狄利克雷生成函数在数论方向有极大的用处。

下一篇博客计划写Polya计数原理,从而更好的解决各种计数问题。


本博客所有文章除特别声明外,均采用 CC BY-SA 4.0 协议 ,转载请注明出处!