序
离散和连续的不期而遇，
抽象与数分的阴阳交融。
我将以加与乘的生铁铸就组合的奇迹，
这世间都要把你的伟岸与光辉所传颂。
$ \mathfrak{Generating Function}$
生成函数所蕴含的思想
生成函数的主要思想是用简单的加法乘法运算，组合出强大的复杂的数列。你会惊讶于这些简单的东西经过组合之后竟然有如此强大的能量！或许，这也是 组合数学 其名的来历。
这一思想的直接运用，就是数解空间的大小，即解的数量。
\(\text{Double Deck}\) 问题
给定两副完全一样的牌，各有 \(n\) 张，现在选 \(m\) 张，有多少种选法？
我们将其转化，设 \(z_i\) 是第 \(i\) 张牌被选择的次数，则对 \((z_1,z_2,\cdots,z_n)\)，有 \(z_i \in \{0,1,2\}\)，\(\sum z_i=m\)
然后，我们可以用一个单项式表示一个选择的方法，\(ax_1^{k_1}x_2^{k_2}\cdots x_n^{k_n}\) 表示第 \(i\) 张牌选择 \(k_i\) 个的方法种数。
我们就可以用简单的 \((1+x+x^2)\) 组合出问题的答案：\((1+x+x^2)^n\) 的第 \(m\) 项的系数。
而我们用两次二项式定理拆开，能得到
\((1+x+x^2)^n=\sum_{k\le n}{n\choose k}(x+x^2)^k=\sum_{m}(\sum_{\ell}{n \choose m-\ell}{m-\ell \choose \ell})x^m\)
所以第 \(m\) 项的系数就是 \((\sum_{\ell}{n \choose m-\ell}{m-\ell \choose \ell})\)。
普通生成函数
\(\text{ordinary generating function}\) 是一个级数 \(\sum_{n=0}^\infty a_nx^n\)，对于计算机人来说，它就像是一种编码，把 \(\{a_i\}\) 这个序列用另一种方式写了出来。
在这种情况下，代数运算成为了基础的零件，供我们利用生成函数之间的运算生成某个答案。答案的形式往往是级数某一项的系数。
抽象代数
抽象代数是我们严格的定义生成函数的方式。
从抽象代数的角度来说，生成函数是一个 形式幂级数，而在形式幂级数上定义加法和乘法就可以构成一个环 \(\mathbb{C}[[x]]\)。它是形式的，也就是只有加法和乘法。
这个环有很多便于我们理解的性质。
-
在环上的加法和乘法是通常意义的，也就是，我们可以直接用多项式的卷积理解它。
-
环上的乘法幺元是 \(1\)，也就是我们通常理解的自然数 \(1\)。
同时，因为它是环，那么 \(0\) 以外的每个元素都存在乘法逆元。
这样，我们就可以表示元素 \(F(x)\) 的逆元，即若 \(F(x)G(x)=1\)，则称 \(G(x)\) 是 \(F(x)\) 的逆元，表示为 \(F(x)^{-1}\) 或者 \(\dfrac{1}{F(x)}\)。
数学分析
数学分析是我们感性而经验性的理解生成函数的方式，但是它也是严格的。
从定义上说，形式幂级数和普通的无穷级数具有千丝万缕的联系，所以我们可以方便的把数分中无穷级数的性质拓展到生成函数去。
首先，从数分角度理解生成函数的基础是这个定理：
- 对于 \(A(x)=\sum_n^{\infty}a_nx^n\) 和 \(B(x)=\sum_n^{\infty}b_nx^n\)，如果对于 \(0\) 在复平面上的邻域 \((0,\delta)\) 中的任意 \(x_0\) 都有 \(A(x)=B(x)\)，则对任意的 \(i\) 都有 \(a_i=b_i\)。
然后，我们就可以理解成，生成函数是一个本身的函数性质不重要的数学结构，同时，因为对于任何无穷级数总有收敛半径 \(r\) 使得复平面上 \(0\) 的半径为 \(r\) 的邻域内级数都收敛，我们不妨就认为它总是只在这个收敛半径内取值。从而方便的进行求逆、微分等运算。
在数分角度上理解生成函数，意味着所有的运算，加法、乘法、微分、积分、泰勒展开、求逆，都可以用普通的为我们所熟悉的方式来理解和运用，这是非常可贵的，在实际运用中具有重要的性质。
生成函数的运算
加法
加法是本身形式幂级数所定义的运算，是简单和常规的。
\((\sum a_nx^n)+(\sum b_nx^n)=\sum(a_n+b_n)x^n\)
乘法
乘法也是形式幂级数所定义的，又名为卷积
\((\sum a_nx^n)*(\sum b_nx^n)=\sum (\sum_{k\le n}a_kb_{n-k})x^n\)
几何级数
从数分的角度上讲，因为我们无时无刻不认为生成函数这个“无穷级数”收敛，所以生成函数 \(\sum{\alpha^nx^n}=\dfrac{1}{1-\alpha x}\)。
从形式幂级数的角度上讲，\(\dfrac{1}{1-\alpha x}\) 是一个记号。
也就是 \(\sum{\alpha^nx^n}\) 在 \(\mathbb{C}[[x]]\) 上的乘法逆元。也就是 \((1-\alpha x)\sum{\alpha^nx^n}=1\)。但是因为逆元的可乘性，\(\sum{a^nx^n}\) 和 \(\sum{b^n x^n}\) 的积的逆元就是两者逆元的积 \(\dfrac{1}{1-ax}\dfrac{1}{1-bx}\)。
如果我们再深究下去，我们会发现，
\[\dfrac{1}{1-ax}+\dfrac{1}{1-bx}=A(x)+B(x)=\sum{(a^n+b^n)x^n} \]\[=(\sum_n^{\infty}\sum_{k\le n}a^{k}b^{n-k}x^k-\sum_n^{\infty}\sum_{k\ge 1}a^kb^{n-k}x^n)+ \]\[(\sum_n^{\infty}\sum_{k\le n}a^{k}b^{n-k}x^k-\sum_n^{\infty}\sum_{k\le n-1}a^kb^{n-k}x^n) \]\[=2\sum_n^{\infty}\sum_{k\le n}a^{k}b^{n-k}x^k-\sum_n^{\infty}\sum_{k\in[0,n-1]}a^{k+1}b^{n-k}x^n-\sum_n^{\infty}\sum_{k\in[0,n-1]}a^{k}b^{n-k-1}x^n \]\[=2\sum_n^{\infty}\sum_{k\le n}a^{k}b^{n-k}x^k-ax\sum_n^{\infty}\sum_{k\le n}a^{k}b^{n-k}-bx\sum_n^{\infty}\sum_{k\le n}a^{k}b^{n-k} \]\[=2A(x)B(x)-axA(x)B(x)-bxA(x)B(x) \]\[=\dfrac{1-ax+1-bx}{(1-ax)(1-bx)} \]也就是，逆元记号的加法完全符合分数的运算法则！！！
或许，我们不应该用“美妙”之类的词汇形容它，因为这种性质是由相似的定义决定的。但是，它就像前路绘制好的风景，只是等待着你，等待着发现美的你。
微分
\[G'(x)=\sum_{n=0}^{\infty}(n+1)g_{n+1}x^n \]从数分的角度来说，这是简单的。
从抽象代数的角度来说，我们不能去研究值域的收敛和极限，但是我们可以定义一个 微分算子，也就是，这个形式是我们直接所定义出来的。因为这里只涉及幂，所以不需要进行普适的函数的定义。
泰勒展开
\[G(x)=\sum_{n=0}^{\infty}\dfrac{G^{(n)}(0)}{n!}x^n \]对数分来说，这是简单的。
但是代数这里确实说不过去了，因为我们带入值本身是不合法的。
不过我们仔细思考一下，代入 \(0\) 相当于什么呢？相当于只取 \(G(x)\) 的常数项。那么我们也可以直接定义算子 \(\mathbb{0}G(x)\) 代替 \(G(0)\)，表示 \(G(x)\) 的常数项。然后就可以直接做了。
使用生成函数解决组合计数问题
\(\text{multiset}\) 问题
这个问题我们研究过，我们知道它等价于十二重计数法的第 \(\text{IV}\) 个。但是我们可以用生成函数的语言来表示。
\(S=\{x_1,x_2,\cdots,x_n\}\) 的 \(multiset\) 个数可以用 \((1+x_1+x_1^2+\cdots)\cdots(1+x_n+x_n^2+\cdots)\) 来生成。
然后，因为我们不需要区分这些数到底是什么，所以就是 \((1+x+x^2+\cdots)^n\)
也就是 \((1-x)^{-n}\)。
然后我们用牛顿公式展开
\(=\sum_{k\ge 0}\dfrac{(-n)(-n-1)\cdots(-n-k+1)(-1)^k}{k!}x^k\)
\(=\sum_{k\ge 0}\dfrac{(n)(n+1)\cdots(n+k-1)}{k!}x^k\)
\(=\sum_{k\ge 0}{n+k-1\choose k}x^k\)
- 牛顿公式：\((1+x)^a=\sum_{k\ge 0}\dfrac{(a)(a-1)\cdots(a-k+1)}{k!}x^k\)。证明：\(\int(\int\cdots(\int ((1+x)^a)^{(k)}dx)\cdots dx)dx\)。
斐波那契数列
斐波那契数列是一个数列 \(\{f_i\}\) 满足 \(f_{i-2}+f_{i-1}=f_i,f_0=1,f_1=1\)。
我们考虑它的生成函数 \(F(x)=\sum_{n\ge 0}f_n x^n\)，明显的，\(f_{i-2}+f_{i-1}=f_i\) 意即 \(x^2F(x)+xF(x)+1=F(x)\)（\(+1\) 是为了配平常数项为 \(1\)）。
解此方程得 \(F(x)=\dfrac{1}{x^2+x-1}\)。
通过有理分式的知识，我们知道，设
\[\phi_-=\dfrac{-\sqrt{5}+1}{2},\phi_+=\dfrac{\sqrt{5}+1}{2} \]\[1-x-x^2=(1-\phi_+x)(1-\phi_-x) \]\[F(x)=\dfrac{1}{x^2+x-1}=\dfrac{1}{(1-\phi_+x)(1-\phi_-x)} \]则待定系数 \(a,b\) 得
\[F(x)=\dfrac{a}{(1-\phi_+x)}+\dfrac{b}{(1-\phi_-x)} \]\[a(1-\phi_-x)+b(1-\phi_+x)=1 \]解得 \(a=-\dfrac{1}{\sqrt{5}}\phi_-,b=\dfrac{1}{\sqrt{5}}\phi_+\)
由于 \(kA(x)=\sum_{n\ge 0}{ka_n x^n},(A(x)+B(x))=\sum_{n\ge 0}{(a_n+b_n)x^n}\)
以及 \(\dfrac{1}{1-ax}=\sum_{n\ge 0}a^nx^n\)
\[F(x)=a(\sum_{n\ge 0}{\phi_-^n x^n})+b(\sum_{n\ge 0}{\phi_+^n x^n})=\dfrac{1}{\sqrt{5}}\sum_{n\ge 0}{-\phi_-^{n+1} x^n}+\dfrac{1}{\sqrt{5}}\sum_{n\ge 0}{\phi_+^{n+1} x^n} \]\[=\dfrac{1}{\sqrt{5}}\sum_{n\ge 0}{(\phi_+^{n+1}-\phi_-^{n+1}) x^n}=\sum_{n\ge 0}{\dfrac{(\phi_+^{n+1}-\phi_-^{n+1})}{\sqrt{5}} x^n} \]展开 \(\phi_-\) 和 \(\phi_+\)，就得到我们的最终 \(\{f_n\}\)：
\[f_n=\dfrac{(\dfrac{\sqrt{5}+1}{2})^{n+1}-(\dfrac{-\sqrt{5}+1}{2})^{n+1}}{\sqrt{5}} \]