前言

• 生成函数是什么啊？能吃吗？
• 生成函数（generating function），又称母函数，是一种形式幂级数，其每一项的系数可以提供关于这个序列的信息。——oi-wiki
• 太晦涩了，简而言之，对于一个序列，其生成函数就是以这个序列为系数的多项式。
• 举个栗子??：对于序列 \(A=<0,1,2,3,4,5,\ldots>\) ，其普通生成函数为 \(\sum_{i=0}^{+\infty}A_ix^i=\sum_{i=0}^{+\infty}ix^i\)，而对于序列 \(B=<1,2,3,4,5,\ldots>\)，其普通生成函数为 \(\sum_{i=0}^{+\infty}(i+1)x^i\)。
• 所以这玩意儿有什么用？用处可大了，至少在我目前看来，生成函数就有两种作用：
  1. 能够计算一个序列的第 \(n\) 项的系数，可以用来求通项公式。
  2. 广泛运用于组合数学。

形式幂级数

• 在生成函数的定义里面有一个词叫做形式幂级数。能吃吗？

先讲讲什么是幂级数叭

• 幂级数是指级数的每一项均为与级数项序号 \(n\) 相对应的以常数倍的 \((x?a)\) 的 \(n\:(n\in \N)\) 次方。

• 比如
  \[A(x)=\sum_{i\geq 0}a_i(x-x_0)^i \]
  它与多项式不同的一点在于多项式只有有限项的系数是非零的。

接着讲形式幂级数

• 其意思就是：对于我们生成的这个多项式来说，其中的变量 \(x\) 只是作为一个符号而已，只是一个形式，它的取值并不重要，我们关心的只是它所携带的信息而已。好惨一变量……
• 就比如在最简单的生成函数方案统计问题中，其指数就是我们要求的方案，而其系数就是答案。后面讲生成函数的时候会细讲。

生成函数

• 生成函数可以分为很多种，但是用的最广泛的还是普通生成函数和指数生成函数。

普通生成函数

• \(Ordinary\:Generating\:Function,OGF\) ：普通生成函数。定义为形式幂级数：
  \[F(x)=\sum_{n\geq0}a_nx^n \]

封闭形式

• 每次计算都要写一长串的多项式或者写一个 \(\sum\)，太麻烦了，有没有更好的方法？

• 自然是有的，我们发现：对于序列 \(<1,1,1,\ldots>\) 的普通生成函数 \(F(x)=\sum_{n\geq 0}x^n\) ，有

  \[F(x)\cdot x+1=F(x) \]

• 解得 \(F(x)=\frac{1}{1-x}\)，所以我们可以用这个来代替原来琐碎的 \(\sum\) 并简化运算。

• 真是天衣无缝又十分扯淡

• 这种方法用的非常多，尤其是在求通项公式的时候，比如求斐波那契和卡特兰数的通项公式时就会用到。

二项式定理

• 但是我们将一个多项式变成封闭形式之后就无法得到第 \(n\) 项的系数了啊。但是没有关系，我们可以用二项式定理将其展开。

• \(Generalized\:Binomial\:Theorem:\) 广义二项式定理：

  \[(x+y)^\alpha=\sum_{k=0}^\infty \left(\begin{matrix}\alpha\\k\end{matrix}\right)x^{\alpha-k}y^k \]

  其中 \(\left(\begin{matrix}\alpha\\k\end{matrix}\right)\) 为广义二项式系数（其实就是实数域下的组合数）

  \[\left(\begin{matrix}\alpha\\k\end{matrix}\right)=\frac{\alpha^{\underline k}}{k!}=\frac{\alpha(\alpha-1)\ldots(\alpha-k+1)}{k!},\alpha\in\R,k\in\N \]

  \(\alpha^{\underline k}\) 表示 \(\alpha\) 的 \(k\) 次下降幂，即 \(\alpha(\alpha-1)\ldots(\alpha-k+1)\)。上升幂类似。

• 举上面的那个栗子??，将 \(F(x)=\frac{1}{1-x}\) 展开：

  \[\begin{aligned} F(X)&=(1-x)^{-1}\\ &=\sum_{k\geq 0}\left(\begin{matrix}-1\\k\end{matrix}\right)(-x)^k\\ &=\sum_{k\geq 0}\left(\begin{matrix}-1\\k\end{matrix}\right)(-1)^kx^k\\ \end{aligned} \]

  那么 \(n\) 项的系数为

  \[\left(\begin{matrix}-1\\n\end{matrix}\right)(-1)^n \]

  将广义二项式系数展开，上下约分得 \((-1)^n\) ，所以第 \(n\) 项的系数为 \(1\)。

• \(Tips:\left(\begin{matrix}m\\n\end{matrix}\right)(-1)^n=\left(\begin{matrix}n-m-1\\n\end{matrix}\right)\)，将广义二项式系数展开之后把 \(-1\) 代进去得上升幂再转下降幂即可。

  \[\begin{aligned} \left(\begin{matrix}m\\n\end{matrix}\right)(-1)^n&=\frac{m(m-1)\ldots (m-n+1)}{n!}(-1)^n\\ &=\frac{-m(-m-1)\ldots (n-m-1)}{n!}\\ &=\frac{(n-m-1)^{\underline n}}{n!}\\ &=\left(\begin{matrix}n-m-1\\n\end{matrix}\right) \end{aligned} \]

回到形式幂级数

• 用一个题目来简单说明一下：你有两个苹果??，三个梨子??，两个桃子??。问：拿五个水果共有几种方案？

• 我们分别写出 ?????? 的生成函数：

  ?? : \(1+x+x^2\)

  ?? : \(1+x+x^2+x^3\)

  ?? : \(1+x+x^2\)

• 其中 \(x\) 的指数表示这种水果拿多少个，我们将其乘起来之后，五次项（表示选五个）的系数即为问题的答案：

  \[(1+x+x^2)(1+x+x^2+x^3)(1+x+x^2)=1+3x+6x^2+8x^3+8x^4+6x^5+3x^6+x^7 \]

  所以答案为 \(6\)。

指数生成函数

• \(Exponential\:Generating\:Function,EGF\) ：指数生成函数。定义为形式幂级数：
  \[\hat F(x)=\sum_{n\geq 0} a_n\frac{x^n}{n!} \]

封闭形式

• 我们先反着来，先说展开

• 前置芝士??：泰勒展开

• 看到指数生成函数的阶乘分母有没有觉得很熟悉？

• 我们想到泰勒级数也同样具有作为分母的阶乘，那么我们可以考虑将某个函数泰勒展开。

• 考虑在 \(x_0=0\) 处用多项式去模拟 \(e^x\)，将 \(e^x\) 取一阶导数、二阶导数、三阶导数……然后将 \(x_0=0\) 代入可得

  \[e^x=\sum_{n\geq 0}\frac{1}{n!}x^n \]

  为什么去模拟 \(e\) ？因为这玩意儿太好算了

• 所以我们将这个式子反过来就得到了序列 \(<1,1,1,1,\ldots>\) 的指数生成函数的封闭形式。

• 类似的，还有

  \[\begin{aligned} xe^x&=\sum_{n\geq 0}\frac{n}{n!}x^n\\ e^{Cx}&=\sum_{n\geq 0}\frac{C^n}{n!}x^n\\ \ln (1-x)&=-\sum_{n\geq 1}\frac{1}{n}x^n\\ \end{aligned} \]

一个小小的问题

• 为什么指数生成函数需要除以一个阶乘呢？这个阶乘有什么用？

• 因为指数生成函数就类似于多重集的排列数，从一个多重集中依次选择 \(N\) 个元素的方案数为 \(\frac{N!}{a_1!a_2!\ldots a_n!}\) （\(a_i\) 表示每一个元素有多少个），有没有觉得很像？没有。其实除以的这个阶乘就相当于方案数中的分母。所以最后得到系数之后是需要乘上 \(N!\) 的。
• 等等，这个乘是什么意思，是额外再乘一个 \(N!\) 吗？
• 显然不是，它是自动生成的。怎么越来越玄乎了？
• 我们可以将这个阶乘想象成是 \(x\) 的一部分（不要看做是系数），就是有 \(x\) 就必须要有阶乘，那么我们将两个指数生成函数相乘之后，第 \(n\) 项可能就是 \(\frac{1}{i!j!}x^n\)，这个时候我们发现没有 \(n!\)，所以我们乘上 \(\frac{n!}{n!}\) 得到 \(\frac{n!}{i!j!}\cdot \frac{x^n}{n!}\)，前面才是我们最终得到的系数，是已经乘了的结果。
• 补充一点，因为平时计算最后结果时都是先化成封闭形式再展开。展开时分母可能会有 \(n!\)，所以这时我们只要取前面的系数就可以了。果然自动。

一些通项公式的推导

斐波那契数列

• 斐波那契数列（Fibonacci sequence），又称黄金分割数列，因数学家莱昂纳多·斐波那契（Leonardoda Fibonacci）以兔子繁殖为例子而引入，故又称为“兔子数列”，指的是这样一个数列：0、1、1、2、3、5、8、13、21、34、……在数学上，斐波那契数列以如下被以递推的方法定义：F(0)=0，F(1)=1, F(n)=F(n - 1)+F(n - 2)（n ≥ 2，n ∈ N*）——百度百科

• 斐波那契数列真是再熟悉不过的数列了，因为它比较简单，其每一项都等于前两项之和。所以其通项公式也比较容易得到。

• 我们设 \(F(x)=f_0+f_1x+f_2x^2+\ldots\) 为斐波那契数列的生成函数。则

  \[\begin{aligned} F(x)&=\sum_{i\geq 0}f_ix^i\\ &=f_0+f_1x+\sum_{i\geq 2}f_ix^i\\ &=x+\sum_{i\geq 2}(f_{i-2}+f_{i-1})x^i\\ &=x+x^2\sum_{i\geq 2}f_{i-2}x^{i-2}+x\sum_{i\geq 2}f_{i-1}x^{i-1}\\ &=x+x^2F(x)+xF(x) \end{aligned} \]

  解得 \(F(x)=\frac{x}{1-x-x^2}\) 。考虑到这是封闭形式，我们尝试用待定系数法将其化为广义二项式的形式并将其展开。

  设：

  \[\frac{x}{1-x-x^2}=\frac{A}{1-ax}+\frac{B}{1-bx} \]

  通分然后用待定系数法：

  \[\begin{aligned} \frac{x}{1-x-x^2}&=\frac{A-Abx+B-Bax}{(1-ax-bx+abx^2)}\\\:\\ \therefore &\begin{cases} A+B=0\\ -Ab-Ba=1\\ -a-b=-1\\ ab=-1 \end{cases} \end{aligned} \]

  解得：

  \[\begin{cases} A=\frac{1}{\sqrt 5}\\ B=-\frac{1}{\sqrt 5}\\ a=\frac{1+\sqrt 5}{2}\\ b=\frac{1-\sqrt 5}{2} \end{cases} \]

  那么：

  \[\begin{aligned} F(x)&=\frac{1}{\sqrt 5}\left(\left(1-\frac{1+\sqrt 5}{2}x\right)^{-1}-\left(1-\frac{1-\sqrt 5}{2}x\right)^{-1}\right)\\ &=\frac{1}{\sqrt 5}\left(\sum_{n\geq 0}\left(\frac{1+\sqrt 5}{2}x\right)^n-\sum_{n\geq 0}\left(\frac{1-\sqrt 5}{2}x\right)^n\right)\\ &=\sum_{n\geq 0}\frac{1}{\sqrt 5}\left(\left(\frac{1+\sqrt 5}{2}\right)^n-\left(\frac{1-\sqrt 5}{2}\right)^n\right)x^n \end{aligned} \]

  所以我们就得到了斐波那契数列的通项公式：

  \[\frac{1}{\sqrt 5}\left(\left(\frac{1+\sqrt 5}{2}\right)^n-\left(\frac{1-\sqrt 5}{2}\right)^n\right) \]

卡特兰数

简介

• 卡特兰数，又称卡塔兰数，是组合数学中一种常出现于各种计数问题中的数列。以比利时的数学家欧仁·查理·卡塔兰 (1814–1894)的名字来命名。1730年左右被蒙古族数学家明安图 (1692-1763)使用于对三角函数幂级数的推导而首次发现，1774年被发表在《割圜密率捷法》。——百度百科

• 完全不懂

• 简而言之，卡特兰数也是组合数学中十分重要的内容，其有多种计算公式：

  1. 递推公式 \(1\) ：\(C_n=\sum_{i=0}^{n-1}C_iC_{n-1-i}\)
  2. 递推公式 \(2\) ：\(C_n=\frac{C_{n-1}\times (4\times n-2)}{n+1}\)
  3. 组合公式 \(1\) ：\(f(n)=\frac{C_{2n}^n}{n+1}\)
  4. 组合公式 \(2\) ：\(f(n)=C_{2n}^n-C_{2n}^{n-1}\)

• 以下一些问题的答案都是卡特兰数：

  1. \(n\) 个节点的二叉树的形态个数。
  2. 设进栈的序列为 \(<1,2,3,\ldots,n>\) ，有多少种不同的出栈序列。
  3. \(n\) 级阶梯的化分数。
  4. \(n\) 个 \(0\) 和 \(1\) 组成的长度为 \(2n\) 且前缀和非负的 \(01\) 序列的个数。
  5. \(n+2\) 边形三角划分方案数。
  6. 网格图中从 \((0,0)\) 走到 \((n,n)\) 且不越过对角线的方案数。

• 对④的一些理解：受网格图中容斥原理的启发，我们假设一开始在原点，\(1\) 代表向右上方走一步，\(0\) 代表向右下方走一步，那么最终都会走到 \((2n,0)\)。如果不考虑前缀和非负这一条件的话，那么方案数就为 \(C_{2n}^n\)。这时加上前缀和这一条件，我们发现，在该网格图中，纵坐标就代表着前缀和，那么合法的方案一定不会经过直线 \(y=-1\) 。换句话说，我们将 \((2n,0)\) 沿着 \(y=-1\) 翻折得到对称点 \((2n,-2)\)，那么从 \((0,0)\) 到 \((2n,-2)\) 的每条路线就对应着原图中的一条不合法的路线，这样的路线一共有 \(C_{2n}^{n-1}\) 条，即有 \((n-1)\) 个 \(1\) 的序列数，减去即可。所以答案即为 \(C_{2n}^n-C_{2n}^{n-1}\)，为卡特兰数组合公式 \(2\)。

• 为什么⑤是卡特兰数？其递推公式明明为 \(C_n=\sum_{i\geq 2}^{n-1}C_iC_{n-i+1}\)。我们考虑作以下变换：

  \[\begin{aligned} C_n&=\sum_{i\geq 2}^{n-1}C_iC_{n-i+1}\\ &=\sum_{i\geq 0}^{n-3}C_{i+2}C_{n-i-1} \end{aligned} \]

  将整个数列向左平移两个位置

  \[\begin{aligned} C_{n-2}&=\sum_{i\geq 0}^{n-3}C_iC_{n-i-3}\\ \therefore C_m&=\sum_{i\geq 0}^{m-1}C_iC_{m-1-i}\quad(m=n-2) \end{aligned} \]

• 其实有一种更为直观的理解：在求和的时候，\(i\) 的取值范围为 \(2\sim n-1\)，而 \(n-i+1\) 则为 \(n-1\sim 2\)，标准的卡特兰数。

求通项公式

• 知道卡特兰数的递推公式之后就好办了。

• 设 \(F(x)=C_0+C_1x+C_2x^2+\ldots\) 为卡特兰数的生成函数。则

  \[\begin{aligned} F(x)&=\sum_{i\geq 0}C_ix^i\\ &=1+x\sum_{i\geq 1}\sum_{j=0}^{i-1}C_jx^j\cdot C_{i-1-j}x^{i-1-j}\\ &=1+x\sum_{i\geq 0}\sum_{j=0}^{i}C_jx^j\cdot C_{i-j}x^{i-j}\\ &=1+xF^2(x)\\ \end{aligned} \]

  解得 \(F(x)=\frac{1\pm\sqrt{1-4x}}{2x}\)，因为 \(F(0)=C_0=1\)，且

  \[\begin{aligned} \lim_{x\to 0} \frac{1+\sqrt{1-4x}}{2x}&=\infty\\ \lim_{x\to 0} \frac{1-\sqrt{1-4x}}{2x}&=0 \end{aligned} \]

  （具体参考洛必达法则）

  所以 \(F(x)=\frac{1-\sqrt{1-4x}}{2x}\) 。

• 这才推了一点点

• 考虑将 \(\sqrt{1-4x}\) 广义二项式展开

  \[\begin{aligned} (1-4x)^\frac{1}{2}&=\sum_{n\geq 0}\left(\begin{matrix}\frac{1}{2}\\n\end{matrix}\right)(-4x)^n\\ &=1+\sum_{n\geq 1}\frac{\left(\frac{1}{2}\right)^{\underline n}}{n!}(-4x)^n \end{aligned} \]

  而

  \[\begin{aligned} \left(\frac{1}{2}\right)^{\underline n}&=\frac{1}{2}\frac{-1}{2}\frac{-3}{2}\cdots \frac{-(2n-3)}{2}\\ &=\frac{(-1)^{n-1}(2n-3)!!}{2^n}\\ &=\frac{(-1)^{n-1}(2n-2)!}{2^n(2n-2)!!}\\ &=\frac{(-1)^{n-1}(2n-2)!}{2^{2n-1}(n-1)!} \end{aligned} \]

  所以

  \[\begin{aligned} (1-4x)^\frac{1}{2}&=1+\sum_{n\geq 1}\frac{(-1)^{n-1}(2n-2)!}{2^{2n-1}(n-1)!n!}(-4x)^n\\ &=1-\sum_{n\geq 1}\frac{(2n-2)!}{(n-1)!n!}2x^n \end{aligned} \]

  带回原式得到

  \[\begin{aligned} F(x)&=\frac{1}{2x}\sum_{n\geq 1}\frac{(2n-2)!}{(n-1)!n!}2x^n\\ &=\sum_{n\geq 1}\frac{(2n-2)!}{(n-1)!n!}x^{n-1}\\ &=\sum_{n\geq 0}\frac{2n!}{n!(n+1)!}x^n \end{aligned} \]

  所以卡特兰数的通项公式为

  \[\frac{2n!}{n!(n+1)!}=\frac{2n!}{n!n!}\cdot\frac{1}{n+1}=\frac{C_{2n}^n}{n+1} \]

  为组合公式 \(1\)

——2021年2月11日