引入

我们中学在学习多项式和数列时，知道二项式 $(1+x)^n$ 展开后每一项的系数都是 $C_n^i$ ， 对应着数列 $a_i=C_n^i$ 。那么，我们是否可以构造一个函数 $f(x)$ ，使得 $f(x)$ 的系数对应着数列 $a_i$ ，从而可以方便地研究数列的性质呢？

这个能生成出数列的函数 $f(x)$ 就被称为生成函数。生成函数是组合数学中一个非常重要的工具，可以方便地研究数列的性质。

定义

实数序列 $a_0,a_1,\cdots ,a_k, \cdots$ 的生成函数（Generating function）是无穷级数

例如，数列 的生成函数为 、数列 的生成函数为 、 数列 的生成函数为 。

例题：

  1. 求 ${1,1,1,1,1,1}$ 的生成函数。

    解： $G(x)=1+x+x^2+x^3+x^4+x^5=\frac{x^6-1}{x-1}$ (这里 $a_0=1 $ )。

  2. 求无穷等差数列 $a_n=1+2n$ 其中 $n\ge 0$ 的生成函数。

    解：

    下面我们求 $\sum_{n=0}^\infty nx^{n-1}$ 的生成函数，设其生成函数为 $F(x)$ ，则

    我们将 $x$ 乘上 $F(x)$ 有

    错位相减得

    于是

    所以

我们归纳出常用的生成函数：

数列 $a_k$ 生成函数 $G(x)$
$C_n^k$
$\alpha^k C_n^k$
$1$
$\alpha^k$
$k+1$
$C_{n+k-1}^k$
$a^kC_{k+p}^{p}$
$\frac{1}{k!}$
$\frac{(-1)^{k+1}}{k}$

性质

计算性质

  1. 叠加性：
    数列 和 的生成函数分别为 和 ，其每项和 的生成函数为
  2. 常数倍性：
    数列 的生成函数为 ，其每项乘以常数 的生成函数为 。
  3. 乘法性：
    数列 和 的生成函数分别为 和 ，其每项乘积 的生成函数为 （即卷积） 。
  4. 移位性：
    数列 的生成函数为 ，其每项向前（左）移动 位的生成函数为 （构造数列 ） （生成少的项减0）。
    相反地，其每项向后（右）移动 位的生成函数为 （构造数列 ，并规定对于所有的 有 ） （生成多的项补0）。

    举个例子： 数列 的生成函数为

    • 其每项向前移动一位 ，构造 ，其生成函数为 。
    • 其每项向后移动一位 ，构造 ，其生成函数为 。
  5. 可导性：
    对于数列 的生成函数 ，其导数 。如果我们再将 乘上 ，则得到 ，这得到了加权数列 的生成函数。
    也就是说，我们可以通过求导来得到加权数列的生成函数。那么对于幂级数 ，其n阶导数在 $x=0$ 的取值为 。反过来，我们可以通过求导来得到数列 的每一项 。

与计数问题对应

在符号组合学（Symbolic Combinatorics）框架下，两个组合类的乘积对应着两个组合类元素集合的笛卡尔积，而一个组合类元素集合的幂集对应着该组合类元素集合的并集。换句话说如果 $\mathcal{A}$ 和 $\mathcal{B}$ 是两个组合类，那么 $\mathcal{A}\times\mathcal{B}$ 对应着 $\mathcal{A}$ 和 $\mathcal{B}$ 的元素集合的笛卡尔积，而 $\mathcal{A}^*$ 对应着 $\mathcal{A}$ 的元素集合的并集。

例如，$\mathcal{C}=\mathcal{A}\times\mathcal{B}$ ，中 $\mathcal{C}$ 的每个大小为 $n$ 的对象都可以被唯一分解为 $(a,b)$ ，其中 $a\in\mathcal{A}$ ， $b\in\mathcal{B}$ ，因此有：

即普通生成函数的Cauhy-乘积（即卷积）。

Simple 1

方程 $x_1+x_2+x_3=11$ 有几组解？其中 $x_i\in{0,1,\cdots,11}$ 。

解：
$x_1+x_2+x_3=11$ 的非负数解可以看作3个元素重复计数11-组合数。
由于每个对象可以取任意个数，故因子为 $1+x+x^2+\cdots$ ，则有生成函数：

由生成函数的性质，我们知道 ，所以 。因此 。

Simple 2

我们对 Simple 1 再加入限制，$2\leq x_1 \leq 5$ ， $3\leq x_2 \leq 4$ ， $2 \leq x_3 \leq 6$ ，求此时的解的个数。

解：
我们将 的取值范围限制为 ，则 的生成函数为 。同理可求 、 。
所以 ，则 。

Simple 3

人民币的面值有集合 $\mathbb{A}={1,5,10,50,100,200,500,1000}$ （单位：角）求用这些面值凑出 $S$ 角的方案数。

解：
对于面值为 $v$ 的货币，其生成函数为

于是对于所有面值的生成函数为

则 $G(x)$ 的第 $S$ 项系数 $a_S$ 即为方案数。

假如 $0 \leq S \leq 10^{8}$ ，最后的结果会很大，需要对 $998244353$ 取模。
这里我们给出这个问题的C++代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define endl '\n'
#define mod 998244353
ll s;
int A[8]={1,5,10,50,100,200,500,1000};

int main()
{
  ios::sync_with_stdio(false);
  cin.tie(nullptr);cout.tie(nullptr);
  cin >> s;
  vector <ll> f(s+1,0);
  f[0]=1;
  for(int v: A)
  {
    vector<ll> g(s+1,0);
    for(ll i=0;i<=s;i+=v) g[i]=1;
    vector<ll> newf(s+1,0);
    for(ll i=0;i<=s;i++)
    {
      if(f[i]==0) continue;
      for(ll j=0;j+i<=s;j++)
        newf[i+j]+=(f[i]*g[j])%mod;
    }
    f=newf;
  }
  cout << f[s] << endl;
  return 0;
}

但这个直接暴力模拟生成函数的时间复杂度为 $O(8 \cdot s^2)$ ，显然会超时。
我们可以换个思路，对同一个 $s$ 每次选取新的面值就是在以往的方案数上加上新的面值对应的方案数，所以我们可以用动态规划的思想来优化，时间复杂度降为 $O(8s)$ 。
我们做二维表，行表示凑出的金额，列表示含有这个面值（包含小于其面值）的方案数，则有表：

凑出金额 1 5 10 50 100 200 500 1000
0 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1
$\vdots$
5 1 2 2 2 2 2 2 2
6 1 2 2 2 2 2 2 2
$\vdots$
10 1 3 4 4 4 4 4 4
11 1 3 4 4 4 4 4 4
$\vdots$
15 1 4 6 6 6 6 6 6
$\vdots$

归纳有

于是有C++代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define endl '\n'
#define maxn 300005
#define minn 1005
ll s;
int a[8]={1,5,10,50,100,200,500,1000};


int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    cin >> s;
    vector <vector<ll> > dp(s+1,vector<ll>(8,1));
    for(ll i=2; i<=s; i++)
    {
    	for(ll j=1; j<8; j++)
    	{
    		if(a[j]>i) dp[i][j]=dp[i][j-1]%mod;
    		else 
    			dp[i][j]=dp[i][j-1]+dp[i-a[j]][j]%mod;
    	}
    }
    cout << dp[s][7];    

    return 0;
}

但是这个方法还是不够优秀，我们再进一步优化。
我们注意到：

我们要求的是 $aS$ ，那么我们可以直接用递推公式 $a_n=a_n+a{n-v}$ 来计算。于是有C++代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define endl '\n'
#define mod 1000000000000000000
ll s;
int A[8]={1,5,10,50,100,200,500,1000};

int main()
{
  ios::sync_with_stdio(false);
  cin.tie(nullptr);cout.tie(nullptr);
  cin >> s;
  vector <ll> f(s+1,0);
  f[0]=1;
  for(int v: A)
    for(int i=v;i<=s;i++)
      f[i]=(f[i]+f[i-v])%mod;

  cout << f[s] << endl;
  return 0;
}

与数列的关系

由生成函数的计算公式，我们知道：

  1. 生成函数 $G(x)$ 的系数就是数列的通项公式；
  2. 生成函数 $G(x)$ 乘上 $\frac{1}{1-x}$ 后的系数就是数列的前 $n$ 项和。
  3. 的系数就是数列的差分 。

Simple 1

斐波那契数列 ， ，求斐波那契数列的显式通项公式，并证明其前 项和为

解：
由斐波那契数列的递推公式，我们可以得到其生成函数为

解得

又 $G(x)$ 可变为：

于是有方程：

解得 $\varphi=\frac{1+\sqrt{5}}{2},\overline{\varphi}=\frac{1-\sqrt{5}}{2}$

$G(x)$又可变换为：

于是有：

解得 $A=\frac{1}{\sqrt{5}},B=-\frac{1}{\sqrt{5}}$ ，于是有：

于是有：

下面来求前 $n$ 项和：

我们知道 所生成的序列，实际上是 的前 项和。欲证 ，即证 的生成函数等于 。

于是有：

因此有 。

Simple 2

卡特兰数列
求卡特兰数列的显式通项公式。

解：
设其生成函数为：

不难发现，卡特兰数列的递推公式中 实际上就是 $C(x)\cdot C(x)$ 的系数，于是有：

又注意这个等号的左侧：

于是我们得到 ，解这个方程得： ，取 + 时这个解析解会发散，于是我们取 - ，得到

接下来利用二项式定理展开：

因此，卡特兰数列的通项公式为：

Simple 3

求数列 $a_n=n^3$ 的前 $n$ 项和。

解：
我们设 的生成函数为 。

我们知道 ，求导有：

向右移动一位有：

再求导有：

向右移动一位有：

再求导有：

向右移动一位有：

因此， $a_n=n^3$ 的生成函数为：

于是有：

我们记 ，则有：