生成函数生成果，生成数下你和我。
生成函数太美妙，蒟蒻一看被难倒。

生成函数

概念

*度娘定义：

生成函数又叫 母函数 ( 个人不太喜欢这个叫法 )，是组合数学中尤其是计数方面的一个重要理论和工具。
生成函数分为 普通型生成函数 和 指数型生成函数 两种，前者使用较多。形式上说，普通型生成函数用于解决多重集的组合问题，而指数型母函数用于解决多重集的排列问题。

生成函数的应用简单来说在于研究未知（通项）数列规律，用这种方法在给出递推式的情况下求出数列的通项，生成函数是推导 $Fibonacci$ 数列的通项公式方法之一，另外组合数学中的 $Catalan$ 数也可以通过生成函数的方法得到。

另外生成函数也广泛应用于编程与算法设计、分析上，运用这种数学方法往往对程序效率与速度有很大改进。

普通型生成函数

定义：

对于任意数列 $a_0,a_1,a_2,\dots ,a_n$ 用下面这个函数来表示这个数列： $G(x)=\sum_{i=0}^{\infty}a_ix^i=a_0+a_1x+a_2x^2+a_3x^3+\dots+a_nx^n\dots$
这个函数就叫做数列的 生成函数 ( $generating function$ ) 。

指数型生成函数

定义：

对于任意数列 $h_0,h_1,h_2,\dots,h_n$ 用下面这个函数来表示这个数列： $G(x)=\sum_{i=0}^{\infty}h_i\frac{x^i}{i!}=h_0+h_1+h_2x+h_3\frac{x^2}{2!}+\dots+h_n\frac{x^n}{n!}+\dots$

$\mathscr{Tips:}$ 在研究生成函数时，我们都假设级数收敛，因为生成函数中的 $x$ 没有实际意义。

例子

我们先来考虑这样的一个问题：一个班上有四个 $MM$ ，现在要从其中选出 $n$ 个做自己的老婆，请问有多少种选法？答案很简单， $\binom{4}{n}$ 对吧。也就是说从 $i=0$ 开始，问题的答案分别是 $1,4,6,4,1,0,0,0,\dots$ 那么它的生成函数应该为 $G(x)=1+4x+6x^2+4x^3+x^4$ 。诶，这不就是二项式展开吗？于是就有 $G(x)=(1+x)^4$ 。

这里有个广义的推论： $(1+x)^k=\binom k 0x^0+\binom k 1x^1+\dots+\binom k kx^k+\dots$ ，其中，广义的组合数 $\binom k i=\frac{k(k-1)(k-2)\dots(k-i+1)}{i!}$ 且 $k$ 为实数。
举个例子： $\binom4 6=\frac{4\times3\times2\times1\times0\times(-1)}{6!}=0，\binom{-1.4}2=\frac{(-1.4)\times(-2.4)}{2!}=1.68$
这个推论就是经典的 牛顿二项式定理 。

接下来我们再来考虑一个更复杂的生成函数：求出 $x_1+x_2+\dots+x_k=n$ 有多少个非负整数解。这道题在 $Chty\_syq$ 的课件中有详细解答过。

把每组解的每个数加 $1$ ，就变成了 $x_1+x_2+\dots+x_k=n+k$ 的正整数解的个数了，这时候我们就可以用 隔板法 来做：把 $n+k$ 个东西排成一排，在 $n+k-1$ 个间隔中插入 $k-1$ 个 “隔板” ，所以答案就是 $\binom{n+k-1}{k-1}=\binom{n+k-1}{n}$ ，则它关于 $n$ 的生成函数是 $G(x)=(1-x)^{-k}$ 。

推导：
将 $(1-x)^{-k}$ 按照牛顿二项式展开后可以得到 $x^n$ 的系数恰好是 $\binom{n+k-1}{n}$
因为展开后第n+1项： $\binom{-k}{n}(-x)^n=[(-1)^n\binom{n+k-1}{n}][(-1)^nx^n]=\binom{n+k-1}{n}x^n$

经典题目

1、求 Fibonacci 通项公式

在接下来的讲解之前，我们还需要知道一个公式： $\sum_{i=0}^\infty x^i=\frac 1{1-x}$

这个公式在之前我已经证明过了，再证一遍：
$ $\begin{aligned}&已知等比数列求和公式：\sum_{i=0}^n x^i=\frac{1-x^{n+1}}{1-x}\\ &\because -1<x<1\\ &\therefore\lim_{n\to\infty}x^{n+1}=0\\ &\therefore\sum_{i=0}^\infty x^i=\lim_{n\to\infty}\sum_{i=0}^n x^i=\lim_{n\to\infty}\frac{1-x^{n+1}}{1-x}=\frac 1{1-x} \end{aligned}$ $
证毕。

已知 $Fibonacci$ 递推数列为：$ $\begin{aligned}&F(n)=F(n-1)+F(n-2)\qquad( n\geqslant 3)\\&F_2=F_1=1\end{aligned}$ $设它的生成函数为$ g(x) $，则$ g(x) $为：$ $\begin{aligned}g(x)&=x+x^2+2x^3+3x^4+\dots\\&=F_1+F_2x^2+F_3x^3+\dots\end{aligned}$ $两边同时乘以$ x $：$ $x\cdot g(x)=x^2+x^3+2x^4+3x^5+\dots$ $用上式减下式可得：$ $g(x)-x\cdot g(x)=x+x^3+x^4+2x^5+3x^6+\dots=x+x^2\cdot g(x)$ $解得，$ g(x)=\frac x{1-x-x^2}$ 。

由于这个式子不是之前我们见过的 $x$ 成等比关系的式子，再根据这是个分式，于是我们可以把它裂项成等比数列无穷级数求和的式子，将下半部分因式分解可得：$ $g(x)=\frac{x}{(1-\frac{1-\sqrt 5}2x)(1-\frac{1+\sqrt 5}2x)}$ $再转变成和的形式：$ $\begin{aligned}&设g(x)=\frac{x}{(1-\frac{1-\sqrt 5}2x)(1-\frac{1+\sqrt 5}2x)}=\frac a{(1-\frac{1-\sqrt 5}2x)}+\frac b{(1-\frac{1+\sqrt 5}2x)}\\&通分一下得到，\\&g(x)=\frac{(1-\frac{1+\sqrt 5}2x)a+(1-\frac{1-\sqrt 5}2x)b}{(1-\frac{1-\sqrt 5}2x)(1-\frac{1+\sqrt 5}2x)}\\&\therefore (1-\frac{1+\sqrt 5}2x)a+(1-\frac{1-\sqrt 5}2x)b=x\\&又根据g(x)=0可以得到方程组：\\&\begin{cases}(1-\frac{1+\sqrt 5}2x)a+(1-\frac{1-\sqrt 5}2x)b=x&·······①\\a+b=0&·······②\end{cases}\\&将②带回到①中可以得到，a=-\frac 1{\sqrt 5}\\&\therefore b=\frac 1{\sqrt 5}\\&\Rightarrow g(x)=\frac 1{\sqrt 5}\frac 1{(1-\frac{1+\sqrt 5}2x)}-\frac 1{\sqrt 5}\frac 1{(1-\frac{1-\sqrt 5}2x)}\\&将其还原成数列展开得，\\&g(x)=\frac 1{\sqrt 5}(\frac{1+\sqrt 5}2x+(\frac{1+\sqrt 5}2)^2x^2+\dots+(\frac{1+\sqrt 5}2)^nx^n+\dots)-\frac 1{\sqrt 5}(\frac{1-\sqrt 5}2x+(\frac{1-\sqrt 5}2)^2x^2+\dots+(\frac{1-\sqrt 5}2)^nx^n+\dots)\\&g(x)=F_1+F_2x^2+F_3x^3+\dots+F_nx^n+\dots\\&于是我们可以得到\ Fibonacci\ 的通项公式：\\&F_n=\frac{1}{\sqrt{5}}\left(\frac{1+\sqrt{5}}{2}\right)^{n}-\frac{1}{\sqrt{5}}\left(\frac{1-\sqrt{5}}{2}\right)^{n}\end{aligned}$ $哎呦卧槽，这可把我码的累死了！！！

生成函数学习笔记&心得

生成函数

概念

普通型生成函数

指数型生成函数

例子

经典题目

1、求 Fibonacci 通项公式