[人工智能]生成函数简介（Generating function）

生成函数（Generating function），又称母函数，是一种形式幂级数，其每一项的系数可以提供关于这个序列的信息。使用母函数解决问题的方法称为母函数方法。
生成函数有许多不同的种类，但大多可以表示为单一的形式：
$$F(x)=\sum _n{a}_n{k}_n(x)$$
其中$k_n(x)$被称为核函数。不同的核函数会导出不同的生成函数，拥有不同的性质。举个例子：

• 普通生成函数：$k_n(x)=x^n$；

• 指数生成函数：$k_n=\frac{x^n}{n!}$；

• 狄利克雷生成函数：$k_n(x)=\frac{1}{n^x}$。
  其他还有L级数，贝尔级数。
  另外，对于生成函数$F(x)$，我们用$[k_n(x)]F(x)$来表示它的第$n$项的核函数对应的系数，也就是$a_n$。
  对于每个序列都可以写出以上每个类型的一个母函数。构造母函数的目的一般是为了解决某个特定的问题，因此选用何种母函数视乎序列本身的特性和问题的类型。
  母函数的表示一般使用解析形式，即写成关于某个形式变量$x$形式幂级数。对幂级数的收敛半径中的某一点，可以求母函数在这一点的级数和。但无论如何，由于母函数是形式幂级数的一种，其级数和不一定对每个$x$的值都存在。
  母函数方法不仅在概率论的计算中有重要地位，而且已成为组合数学中一种重要方法。此外，母函数在有限差分计算、特殊函数论等数学领域中都有着广泛的应用。
  注意母函数本身并不是一个从某个定义域射到某个上域的函数，名字中的“函数”只是出于历史原因而保留。

• 历史
  瑞士数学家雅各布·伯努利在考虑“当投掷$n$粒骰子时，加起来点数总和等于$m$的可能方式的数目”这个问题时首先使用了母函数方法，并得出可能的数目是$(x+x^2+x^3+x^4+x^5+x^6)$的展开式中$x^m$项的系数。之后欧拉在研究自然数的分解时也使用了母函数方法并奠定了母函数方法的基础。1812年，法国数学家拉普拉斯在著作《概率的分析理论》的第一卷中系统地研究了母函数方法及与之有关的理论。

• 定义
  母函数就是一列用来展示一串数字的挂衣架。——赫伯特·维尔夫
  普通母函数
  普通母函数就是最常见的母函数。一般来说，序列$(a_n{)}_{n\in \mathbb{N}}$
  $$G(a_n;x)=\sum _{n=0}^{\infty }{a}_n{x}^n$$
  如果$a_n$是某个离散随机变量的概率质量函数，那么它的母函数被称为一个概率母函数。
  多重下标的序列也可以有母函数，例如序列$(a_{m,n}{)}_{m\in \mathbb{N},n\in \mathbb{N}}$的母函数是：
  $$G(a_{m,n};x,y)=\sum _{m,n=0}^{\infty }{a}_{m,n}{x}^m{y}^n.$$
  指数母函数
  序列$(a_n{)}_{n\in \mathbb{N}}$的指数母函数是：
  $$EG(a_n;x)=\sum _{n=0}^{\infty }{a}_n\frac{x^n}{n!}$$
  泊松母函数
  序列$(a_n{)}_{n\in \mathbb{N}}$的泊松母函数是：
  $$PG(a_n;x)=\sum _{n=0}^{\infty }{a}_n{e}^{?x}\frac{x^n}{n!}$$
  L级数
  序列$(a_n{)}_{n\in \mathbb{N}}$的L级数是：
  $$LG(a_n;x)=\sum _{n=1}^{\infty }{a}_n\frac{x^n}{1?x^n}$$
  注意这里的下标$n$从1而不是0开始。
  贝尔级数
  关于算术函数：$f(n)$和$p$的贝尔级数是：
  $$f_p(x)=\sum _{n=0}^{\infty }f(p^n)x^n$$
  狄利克雷级数母函数
  狄利克雷级数经常被用作母函数，尽管实际上狄利克雷级数并不是严格意义上的形式幂级数。序列$(a_n{)}_{n\in \mathbb{N}}$的狄利克雷级数母函数是：
  $$DG(a_n;s)=\sum _{n=1}^{\infty }\frac{a_n}{n^s}$$
  当$a_n$是积性函数时狄利克雷级数比较有用，因为这时的母函数可以写成一系列贝尔级数的欧垃积：
  $$DG(a_n;s)=\prod _p{f}_p(p^{?s})$$
  如果$a_n$是狄利克雷特征，那么它对应的狄利克雷级数母函数被称为狄利克雷L函数。

• 应用

1. 有1克、2克、3克、4克的砝码各一枚，能称出哪几种重量？每种重量各有几种可能方案？
   我们用母函数来解决这个问题：
   1). 1个1克砝码可以看成$1+x^1$或$x^0+x^1$,1表示不取，x^1表示取一个，以下同理；
   2). 1个2克砝码可以看成$1+x^2$；
   2). 1个3克砝码可以看成$1+x^3$；
   2). 1个4克砝码可以看成$1+x^4$。
   那么生成函数就是：
   $$\begin{gathered} G(x)=(1+x^1)(1+x^2)(1+x^3)(1+x^4) \\ =1+x+x^2+2x^3+2x^4+2x^5+2x^6+2x^7+x^8+x^9+x^{10} \end{gathered}$$
   这个函数中可以看出重量为3克的方案有两种，重量为7克的方案有两种，重量为10克的有一种。
   不难发现指数表示重量，系数表示方案。
2. 求用1分、2分、3分的邮票贴出不同数值的方案数：
   把这种情况和第一种比较有何区别？第一种每种是一个，而这里每种是无限的。
   那么生成函数就是：
   $$G(x)=(1+x+x^2+x^3+...)(1+x^2+x^4+x^6+...)(1+x^3+x^6+x^9+...)$$
   以展开后的$x^4$为例，其系数为4，即4拆分成1,2,3之和的拆分方案数为4：
   $$4=1+1+1+1=1+1+2=1+3=2+2$$
3. 设有$n$个标志为1,2,…,n的网袋，第i个$(i=1,2,...,n)$网袋里放有$n_i$个球。不同网袋里的球是不同的，而同一网袋里的球则是没有差别的，认为是相同的。询问从中取$r$个球的方案数。
   设生成函数：
   $$G(x)=(1+x^1+x^2+...++x^{n_i})(1+x^1+x^2+...++x^{n_2})...$$
   最后指数为$r$的那一项的系数就是方案数。
   总结一下，生成函数大多用来解决有限或无限物体的组合方案。