【学习笔记】母函数Part2

这一部分大概是从「特征多项式」整理到「指数型母函数及其应用」。

特征多项式

齐次

考虑对于一个以 $\{c_i\}$ 为递推转移的 $k$ 阶线性循环数列 $\{a_i\}$ 的母函数,根据构造似乎可以被写成这样的形式:

$\{b_i\},m$ 都是根据实际情况会变的参数。

那么可以发现这样的恒等的关系:

可以发现分子上的多项式至多有 $k-1$ 次.

像这种根据递推方式快速确定的一个线性循环数列母函数的方法,称为特征法。而多项式

则称为 $\{a_i\}$ 的特征多项式。

e.g.

的通项。


首先分解因式

并且观察到 $b_0=1,b_1=0,b_2=-8$。

那么不妨设

解得

那么就可以知道 $\frac{1-8x^2}{1-x-9x^2-9x^3}$ 的展开是:

那么通项就是

非齐次

非齐次的话,可以直接把常数构造在系数里,本质上没什么不同的。

例题

(1)用 $1,2,3$ 三个数来构造一个 $n$ 位数。不允许两个 $1$ 相邻,求方案数。

发现如果第一位放 $2$ 或 $3$ ,那么有 $2\cdot a_{n-1}$ 的方案;如果放 $1$,那么第二维只能放 $2$ 或 $3$ ,那么有 $2\cdot a_{n-2}$ 的方案。所以有 $a_n=2a_{n-1}+2a_{n-2}$ 。

(2)有一行方格,每个格子可以放黑色或者白色,白色不能相邻地放。求方案树。

发现还是讨论第一个位置放的是不是白色。$f_n=f_{n-1}+f_{n-2}$ 。

高阶差分

一点定义

定义 $\{a_i\}$ 的一阶差分 $\Delta^1\{a_i\}$ 是这样的数列 $\{a_1-a_0,a_2-a_1,\cdots,a_n-a_{n-1}\}$ 。

那么 $k$ 阶差分指的是 $\Delta^k\{a_i\}=\Delta\{\Delta^{k-1}\{a_i\}\}$ 。

假设一个数列 $\{a_i\}$ 在 $k$ 阶差分时不是全 $0$ 数列,在 $k+1$ 阶差分时是全 $0$ 数列,那么称这个数列为 $k$ 阶等差数列。

一个定理

如果记 $\Delta^k\{a_i\}:\{a_0^{(k)},a_1^{(k)},a_2^{(k)},\cdots,a_n^{(k)}\cdots \}$,那么有:

这个显然可以直接归纳。就懒得证了。

$k$ 阶等差数列 $\{a_n\}$ 的前 $n$ 项和。

考虑对于数列 $\{s_n\}$ ,满足 $s_i=\sum_{j=0}^ia_i$,那么发现可以直接让 $\{a_n\}*(\frac{1}{1-x})$ 得到 $\{s_n\}$

所以假设 $\{a_n\}$ 的母函数是 $f(x)$,那么 $\{s_n\}$ 的母函数就是 $\frac{f(x)}{1-x}$。

那么考虑如何计算 $f(x)$ 。根据性质可知:

那么由于 $a_{n}^{(k+1)}=0$ ,所以可以得到:

发现本质上 $\binom{k+1}{x}$ 属于常数项。所以可以知道 $\{a_n\}$ 是一个 $k+1$ 个线性循环数列。所以可以用特征法直接求出。

但其实这种方法有时候比归纳要麻烦很多。这种方法主要用来解决一些比较妙的问题。

一点应用

e.g.

给定 $n$ ,求坐标系中 $|x|+|y|=m,(m=0,1,2,3\cdots n)$ 的 $(x,y)$ 点对数。

考虑设 $\{a_i\}$ 表示 $i=m$ 时的方案数,$\{s_i\}$ 即为所求。那么可以知道 $a_i$ 的母函数为:

看上去十分 $easy$,因为每个坐标有$+-$ 两种取值,所以加一个系数 $2$ 。

那么发现可以这么转化:

所以 $\{s_n\}$ 的母函数 $f_s(x)$ 为

发现 $(1-x)$ 是它的 $3$ 重根,所以有:

那么可以展开得到:

于是可知 $s_n=2n^2+2n+1$ 。

卡特兰数

首先发现卡特兰数的定义式就是

那么这东西的母函数大概可以这么求(默认第 $0$ 为位是 $0$ 而不考虑):

那么解一下方程可以得到俩根:

验一下发现应该取 $f_1$.

在不考虑牛顿迭代的情况下,不加证明地给出一个等式:

那么代换一下可以得到:

再带回去得到:

那么可知卡特兰数第 $n$ 项 $\mathrm{Cat}_n=\frac{\binom{2(n-1)}{n-1}}{n}$。

当然一般情况下 $\rm Cat$ 的定义有从 $0$ 开始的,只是把这种方式向前平移了一项而已。

指数型母函数

基础定义

出于需要,定义另一种生成函数,即指数型母函数 $(\mathbf{EGF})$ 。对于数列 $\{a\}$,他的 $\rm EGF$ 是:

那么可以得出两个 $\rm EGF$ 卷积的结果是:

可以发现有

那么之所称之为指数型母函数,则依赖于下面的性质:

可以发现有

证明大概是可以把 $e(y)$ 改写成

然后

发现这种性质类似于指数运算的性质,所以称之为指数型母函数。

同时可知,令 $y=-x$ 则有 $e(x)=\frac{1}{e(-x)}$ 。

二项式反演

设 $\{a_n\}$ 给定,且

则必有

考虑让数列 $\{(-1)^na_n\}$ 的母函数卷上 $e(x)$ 得到:

也就是

因为 $\frac{1}{e(x)}=e(-x)$ ,所以有:

对比第 $n$ 项即可得到

一个例子

首先有一个比较 general 的结论:

这是由于

那么稍微变一下形态:

移个项就完了。

那么根据这个可以再证明出一个更强一点的结论:

考虑直接归纳。不难验证 $n=1$ 成立。那么考虑 $n\to n+1$ 的过程

其中最后一步用的就是上面的 $(1)$。

那么回到本题,考虑设 $a_0=0, a_n=-\frac{1}{n}\quad (n=1,2,3\cdots )$ 。同时设 $b_0=0$,

那么根据 $(2)$ 和二项式反演可以得到

指数型母函数的应用

有限制的可重排列问题

给定 $n$ 个物品,从中取 $r$ 个进行排列,第 $k~(k=1,2,3\cdots m)$ 种物品有 $n_k$ 个,求排列方案数。

首先给出这东西的母函数:

考虑这样表示的意义。对于 $f_e(x)$ 的第 $r+1$ 项,有:

其中 $\{d_m\}$ 可以看做是满足 $d_1+d_2+\cdots+d_m=r$ 的一组枚举量。

考虑这样做的可行性。首先变一下形

发现第 $r+1$ 项的系数 $\frac{r!}{\prod d_i!}$,正好是从 $r$ 个物品中,共 $m$ 中,每种分别有 $d_i$ 个,取满 $r$ 个的方案数。所以正确性显然。

例子

用 $1,2,3,4$ 四个数字能组成多少五位数?要求 $1$ 只能出现 $2$ 或 $3$ 次,$2$ 出现 $0$ 或 $1$ 次,$3$ 没有限制, $4$ 出现偶数次。

这个问题的母函数显然就是这个:

考虑一个性质

那么原式就变成了

发现本质上右边不存在 $x^5$ 这一项,所以忽略。

于是最后通过化简可知答案是 $140$ .