「数学」生成函数
组合排列
核心：数列卷积转化为多项式卷积转化为函数乘法
设集合 A 的 n 组合方案数为 \(a(n)\)， 集合 B 的 n 组合方案数为 \(b(n)\)， 同时 \(A\cap B=\emptyset\)， 那么集合 \(H=A\cup B\) 的 \(n\) 组合方案数为两者的卷积：
\[ h(n)=\sum_{k=0}^{n}a(k)*b(n-k) \]
这符合多项式乘法的形式，对应生成函数为
\[ f_h(x)=\sum_{k=0}h(k)x^{k} \]
设集合 A 的 n 排列方案数为 \(a(n)\)， 集合 B 的 n 排列方案数为 \(b(n)\)， 同时 \(A\cap B=\emptyset\)， 那么集合 \(H=A\cup B\) 的 \(n\) 排列方案数为：
\[ h(n)=\sum_{k=0}^{n}a(k)*b(n-k)*\frac{n!}{k!(n-k)!} \]
表达式仍然是卷积的形式， 但是增加了一些和下标相关的常数， 尝试进行变形
\[ \frac{h(n)}{n!}=\sum_{k=0}^{n}\frac{a(k)}{k!}*\frac{b(n-k)}{(n-k)!} \]
这符合多项式乘法的形式，对应生成函数为
\[ f_h(x)=\sum_{k=0}\frac{h(k)}{k!}x^{k} \]
单纯转化为多项式之后并没有简化计算。 注意到无穷多项式可能是某个函数的展开式， 那么利用该函数进行计算可能更加简便。如：
\[ \sum_{k=0}{n\choose k}x^k=(1+x)^n\\ \sum_{k=0}{n\choose k}(-x)^k=(1+x)^n\\ \sum_{k=0}{n+k-1\choose k}(x)^k=\frac{1}{(1+x)^n}\\ \sum_{k=0}{n+k-1\choose k}(-x)^k=\frac{1}{(1-x)^n} \]
\[ \sum_{k=0}\frac{x^k}{k!}=e^x\\ \sum_{k=0}\frac{(-x)^k}{k!}=e^{-x}\\ \sum_{k=0}\frac{x^{2k}}{(2k)!}=\frac{1}{2}(e^{x}+e^{-x})\\ \sum_{k=0}\frac{x^{2k+1}}{(2k+1)!}=\frac{1}{2}(e^{x}-e^{-x}) \]
算法流程如下：
- 将数列转化为多项式函数
- 将多项式函数转化为泰勒展开前的函数
- 函数乘法
- 函数乘法结果展开为多项式函数
- 多项式函数转化为数列
函数通项
生成函数和数列是一一对应的， 数列满足的性质生成函数的系数也应（在某种形式上）满足
那么求出满足性质的生成函数就能反推出对应数列
核心：利用性质消项