广告
由于本人太弱，本文可能层次较浅，没有太深的了解与证明
0. 前置知识
- 知道多项式是啥
您最好还要知道卷积（多项式乘法）是啥不用会写
- Taylor 展开
其实这个不是重点
- 广义二项式定理
我们都知道喜闻乐见的二项式定理：
\[(1+z)^n=\sum\limits_{i=0}^n C_n^i z^i \]但有时候，我们想让这个 \(n\) 变成负数甚至小数咋办？
设 \(f(z)=(1+z)^\alpha\)
我们有 \(f(z)=\sum\limits_{k \geq 0} \dfrac{f^{(k)}(0)}{k!}z^k\)
解释一下求导：
\(f(z)=(1+z)^\alpha\)
\(f^{(1)}(z)=\alpha(1+z)^{\alpha-1}\)
\(f^{(2)}(z)=\alpha(\alpha-1)(1+z)^{\alpha-2}\)
\(\cdots\)
\(f^{(k)}(z)=\alpha^{\underline{k}} (1+z)^{\alpha-k}\)
代入
\[f(z)=(1+z)^\alpha = \sum\limits_{k \geq 0} \dfrac{\alpha^{\underline{k}} }{k!}z^k \]啊哈，于是我们还能定义拓展的组合数 \(C_m^n=\dfrac{m^{\underline{n}}}{n!}\)
1. 生成函数
生成函数是啥呢？
我们现在有一个序列 \(\{a_i\}\)
把序列扔到多项式的系数上，就能得到一个对应的多项式
\[A(z)=\sum\limits_{i=1}^n a_iz^i \]- 注意：\(z\) 只是形式的自变量，并没有实际意义，想让它取啥就取啥
没了
下面来介绍一些变换
1.1 \(k\) 重前缀和
我们有一个数列 \(\{a_i\}\) 和它的生成函数 \(A(z)\)
求出它的前缀和 \(\{b_i\}\)
那 \(\{b_i\}\) 的生成函数是啥呢？
\[b_k=\sum\limits_{i=0}^k a_i=\sum\limits_{i=0}^k a_i \times 1 \] \[B(z)=(1+z+z^2+z^3+\cdots)A(z) \]相信大家都会卷积不用我解释了
那又多了一个新的多项式 \(f(z)=1+z+z^2+z^3+\cdots\)
事实上，当 \(-1 \leq z \leq 1\) 时，\(f(z)=\dfrac{1-z^{+\infty}}{1-z} \rightarrow \dfrac{1}{1-z}\)
啊？这不是多项式吗？咋变成一个数了？
没事，看广义二项式定理！
\[f(z)=(1-z)^{-1}=\sum\limits_{i \geq 0} C_i^{-1} (-z)^i \]当然，要求出 \(k\) 重前缀和也很简单了
\[f(z)=(1-z)^{-k}=\sum\limits_{i \geq 0} C_i^{-k} (-z)^i \] \[C_i^{-k}=\dfrac{(-k)(-k-1)\cdots(-k-i+1)}{i!}=(-1)^i\dfrac{k(k+1)\cdots(k+i-1)}{i!}=\dfrac{C_k^i}{i!} \] \[f(z)=\sum\limits_{i \geq 0} \dfrac{C_k^i}{i!} z^i \]拿 \(f\) 跟 \(A\) 卷一下就行了，\(O(nlogn)\)
2.2 伸缩与单位根反演
\[A(z)=a_0+a_1z+a_2z^2+a_3z^3+\cdots \] \[A(z^2)=a_0+a_1z^2+a_2z^4+a_3z^6+\cdots \] \[A(z^k)=a_0+a_1z^k+a_2z^{2k}+a_3z^{3k}+\cdots \]多么显然！
就好像是把系数往后伸缩了一样
\[A(z)=a_0+a_1z+a_2z^2+a_3z^3+\cdots \] \[\dfrac{A(z)+A(-z)}{2}=a_0+a_2z^2+a_4z^4+a_6z^6+\cdots \] \[?=a_0+a_kz^k+a_{2k}z^{2k}+a_{3k}z^{3k}+\cdots \]
第二个能用 \(A(-z)\) 是因为 \((-1)^2=1\)
那什么 \(x\) 满足 \(x^k=1\) 呢？
聪明的同学们一定都想到了单位根
\[[k|n]=\dfrac{1}{k} \sum\limits_{i=0}^{k-1}\omega_k^{ni} \]这玩意叫单位根反演，拿等比数列随便证一下就行了咕咕
\(\sum\limits_{i=0} [k|i]a_iz^i=\sum\limits_{i=0} \dfrac{1}{k} a_iz^i \sum\limits_{j=0}^{k-1}\omega_j^{ki} = \dfrac{1}{k} \sum\limits_{j=0}^{k-1} \sum\limits_{i=0} a_iz^i \omega_j^{ki}=\dfrac{1}{k} \sum\limits_{j=0}^{k-1} A(\omega_j^k z)\)
好耶
2. 解析组合
终于进入正题了！
2.1 组合类
组合类是一类东西的集合，比如说一棵有根无标号树或者一堆蜜蜂
用好看的大写字母 \(\mathcal A\) 表示
组合类内的每个元素都定义了一个大小，比如树的大小就是它的节点个数，一群蜜蜂的大小就是里面蜜蜂的数量
记元素 \(\alpha \in \mathcal A\)，则其大小为 \(|\alpha|\)，需要满足：
-
\(|\alpha| \in N\)
-
\(\forall n \in N\) ，以其为大小的元素有限
组合类的生成函数
如果记 \(\mathcal A\) 中大小为 \(n\) 的元素有 \(a_n\) 个，那它的生成函数为：
\[A(z)=\sum\limits_{i=1}^n a_iz^i \]2.2 笛卡尔积
假如我们有一棵 \(5\) 个节点的树和 \(2\) 只蜜蜂
我们把它们放在一起，会得到啥呢？
组成了新的元素：带树的蜜蜂，大小为 \(7\) ，这是 蜜蜂 \(\times\) 树
组成了新的元素：带蜜蜂的树，大小也为 \(7\)，不过这是 树 \(\times\) 蜜蜂
这就叫笛卡尔积，相当于将 树和蜜蜂 组成一个有序对，大小为二者的和
现在我们有了元素的笛卡尔积了，那集合的笛卡尔积也比较优美
\[\mathcal A \times \mathcal B=\mathcal C=\{\gamma=(\alpha,\beta)|\alpha \in \mathcal A,\beta \in \mathcal B \} \]现在来考虑它的生成函数
聪明的同学肯定又发现了：这就是卷积！
于是又有了一个优美的式子：
\[C(z)=A(z)B(z) \]2.3 和（不交并）
假如我们有一棵 \(5\) 个节点的树和 \(5\) 只蜜蜂
我们还是把它们都拿出来，但这次放得比较远
组成了新的元素
但这次这个元素大小还是 \(5\) ，代表的是：树 或者 蜜蜂
其实就相当于将二者列出来，而不是组合起来
如果 \(\mathcal {A \bigcap B = \varnothing}\) （要求不交是为了方便运算）
定义 \(\mathcal A + \mathcal B = \mathcal A \bigcup \mathcal B = C\)
显然有 \(A(z)=B(z)+C(z)\)
只有相同大小的才会被加到一块，就没有问题了
2.4 序列
我们有一个组合类 \(\mathcal A\) ，用一只蜜蜂来表示
现在让 \(\mathcal {B=A \times A}\)，用两只蜜蜂表示
现在再让 \(\mathcal {C=A \times A \times A}\)，用三只蜜蜂表示
\(\cdots\)
我们把它们排成一列，相加起来
得到了啥？
\[SEQ(\mathcal A)=\mathcal{\{E\}+A+A \times A + A \times A \times A + \cdots} \]\(\{\mathcal E\}\) 也是一个组合类，不过它里面只有一个元素，叫空集
这是啥意思呢？
加的意思是或
也就是说，从 \(SEQ(\mathcal A)\) 取一个元素出来
可能是一只单独的蜜蜂，也可能是几只蜜蜂聚在一起，也可能是一个大蜂巢（有顺序）
生成函数也是一样滴
\[Q(A(z))=1+A(z)+A(z)^2+A(z)^3+\cdots=\dfrac{1}{1-A(z)} \]2.7 试试看！
求 \(n\) 个点的有根无标号树（儿子有区分）个数。
记组合类为 \(\mathcal A\)
先把根提出来
等下，子树有多少个？并不知道啊！
啊，刚刚的序列就是解决这个问题的
\(A(z)=zSEQ(A)=\dfrac{z}{1-A(z)}\)
好耶
3. 更高深的解析组合
不会，咕了