母函数

母函数又称生成函数，发生函数。

母函数可以帮助我们解决很多问题，例如一些简单的组合数学问题。

母函数更为有用的应用在于解常系数线形齐次递推式。

---

从Fibonacci数列看，

Fibonacci数列满足前两项之和等于第三项，

即f_n = f_{n − 1} + f_{n − 2}。

显然这是一个一次二项递推式，

为了得到这个递推关系的通项公式，

一种做法是：设f_n = qⁿ

这样一个Fibonacci数列就转为了一个等比数列（几何数列），

将f_n = qⁿ

代入f_n = f_{n − 1} + f_{n − 2}

得到q⁽n − 1) + q⁽n − 2) = qⁿ

于是q⁽n − 2) * (q² − q − 1) = 0，

由于q⁽n − 2)并不恒等于0，

所以得到q² − q − 1 = 0。

解这个方程很容易得到：

$q_1=\frac{1-\sqrt{5}}{2}$

$q_2=\frac{1+\sqrt{5}}{2}$。

我们把这两个根称为特征根。

---

下面讲一个结论。

对于任何一个线形齐次递推式，

设次数为n，则必然有n个特征根，

记n个特征根为q₁..q_n

则数列{f_m}的

通项公式为$f_m=sum_{i=1}^n r_i*q_i^n$;

其中r_i为使得f_i = a_i

（a_i为n次递推关系的n个边界项，显然可以随意改变）

成立的实数,而q_i为特征根。

为什么这个命题一定成立呢？

首先我们可以知道，几何序列{$q_1^n$}和{$q_2^n$}

是满足递推关系f_n = f_{n − 1} + f_{n − 2}的，

所以$f_m=sum_{i=1}^n r_i*q_i^n$是满足f_n = f_{n − 1} + f_{n − 2}的。

而我们为了让求得的通项公式满足f_i = a_i这n个边界项，

根据一次方程组根的性质，则必然需要给n个特征根n个待定系数。

于是我们列出方程组$\begin{cases} sum_{i=1}^n r_i=a_1 \\ sum_{i=1}^n r_i*q_i=a_2 \\ sum_{i=1}^n r_i*q_i^2=a_3 \\ .......\\ sum_{i=1}^n r_i*q_i^n=a_n \end{cases}$ 例如，对于Fibonacci数列，我们得到：

$\begin{cases} r_1+r_2=0 \\ r_1*\frac{1-\sqrt{5}}{2}+r_2*\frac{1+\sqrt{5}}{2}=1 \end{cases}$ 于是解得r_1=$\frac{1}{\sqrt{5}}$,r_2=$\frac{-1}{\sqrt{5}}$, 代入得到Fibonacci数列满足：

$f_n=\frac{1}{\sqrt{5}}*{(\frac{1+\sqrt{5}}{2})}^n-\frac{1}{\sqrt{5}}*{(\frac{1-\sqrt{5}}{2})}^n$

---

上面只是一种解线形齐次递推式的方法，

接下来介绍母函数的应用。

母函数是什么？

众所周知，Fibonacci数列展开之后就是：

1，1，2，3，5，8……

那么Fibonacci数列的递推式的母函数就是：

G_x = 1 * x¹ + 1 * x² + 2 * x³ + 3 * x⁴ + 5 * x⁶……。

如果把Fibonacci数列换成数列1，1，1，1……

那么它的母函数就是G_X = 1 + x + x² + x³……。

由于母函数中x可以任取，我们设x是真分数，那么很容易得到：

$G_x=\frac{1}{1-x}$。

如此这般，我们就把一个无穷数列转为了一个很简洁的形式。

这个是很有用的——

我们引用《组合数学》上经典的一道例题：

我们要从苹果、香蕉、橘子和梨中拿一些水果出来，要求苹果只能拿偶数个，香蕉的个数要是5的倍数，橘子最多拿4个，梨要么不拿，要么只能拿一个。问按这样的要求拿n个水果的方案数。