符号化方法。小学习。

幻影忍者前情提要

这个我一百年之前就想学习了。但是我一直不会。
wxir 对“现役选手需不需要学习多项式”有一些疑问。我的评价是：我不会。
还有就是。这里记的东西都不严谨。所以不要看这篇文章。
不要看这篇文章。
真的不要看这篇文章。

1.咕咕嘎嘎。

• \(\mathcal{A}\)：这是一个组合类，可以简单地看作一个集合。

• \(a\in \mathcal{A}\)：指的是组合类 \(\mathcal{A}\) 中的一个组合对象。组合对象有大小函数 \(f\)，可以记 \(f(a)=|a|\)。假如现在组合类 \(\mathcal{A}\) 中是所有 \(\text{01}\) 序列，那么可以定义 \(f(a)\) 为 \(\text{01}\) 序列 \(a\) 的长度。

• 组合类转 OGF：
  直接对着组合类做题对我们没有任何帮助。于是我们可以定义 \(A(x)=\sum\limits_{a\in \mathcal{A}} x^{|a|}\)。
  显然，这可以等价地写成

  \[A(x)=\sum\limits_{i=0}^{+\infty}A_ix^i \]

  其中 \(A_i = \sum\limits_{a\in \mathcal{A}} [|a|=i]\)。
  于是，组合类的笛卡尔积就可以看作 OGF 的乘积。组合类的加法就可以看作 OGF 的加法。

• \(\epsilon\)、\(\mathcal{E}\)：\(\epsilon\) 是中性对象、\(\mathcal{E}\) 是中性类。非常不严谨地，可以把它看作（乘法）单位元。\(|\epsilon|=0\)。在上面的例子里，可以看作 \(\mathcal{E}\) 中只有空串。\(\mathcal{E}=\{\epsilon\}\)。显然有 \(E(x)=1\)。

• \(\bullet\)：这是一个原子对象。它可以表示一个东西。就是大小为 \(1\) 的一个东西。很好，待会做题就知道了。大概吧。\(\mathcal{Z}={\bullet}\)，我们称它为原子类。显然有 \(Z(x)=x\)。

2.灵感菇。

下述组合类的乘法都是笛卡尔积。多项式的乘法都是多项式乘法。

举一些简单的例子。

• 卡特兰数 \(C_n\)。
  我们知道其组合意义为大小为 \(n\) 的二叉树个数。于是定义组合类 \(\mathcal{C}\)，里面包含了所有的二叉树。一棵二叉树的大小就是其节点个数。于是 \(C_n=[x^n]C(x)\)。
  一个二叉树可以看作一棵左子树加上一个根节点再加上一个右子树，注意特判为空的情况。于是有式子：
  \[\mathcal{C}=\mathcal{E}+\mathcal{C}\times\{\bullet\}\times\mathcal{C} \]
  转成 OGF，得到：
  \[C(x)=1+xC(x)^2 \]
  解一元二次方程：
  \[C(x)=\frac{1\pm\sqrt{1-4x}}{2x} \]
  因为 \([x^0]C(x)=1\)，所以 \(C(0)=1\)，于是 \(C(x)=\frac{1-\sqrt{1-4x}}{2x}\)。可以考虑 \(x\) 趋近于 \(0\) 的情况。
  使用广义二项式定理展开后可得到卡特兰数的通项公式。然而我不会。
• 长度为 \(n\) 的 \(\text{01}\) 序列，不能有连续的两个 \(0\)，这样的序列有多少个。
  定义组合类 \(\mathcal{S}\) 里面是所有合法的 \(\text{01}\) 序列。一个 \(\text{01}\) 序列的大小就是它的长度。这样的 \(\mathcal{S}\) 满足什么呢？
  任意一个合法串可以看作 \(\text{1}\) 加上一个合法串或者 \(\text{01}\) 加上一个合法串，于是有：
  \[\mathcal{S}=\mathcal{E}+\{0\}+\text\{\text{1},\text{01}\}\times \mathcal{S} \]
  写成 OGF：
  \[\mathcal{S}=1+x+(x+x^2)\mathcal{S} \]
  解得：
  \[\mathcal{S}=\frac{1+x}{1-x-x^2} \]
  wxir 说这是斐波那契。这貌似真的是斐波那契。非常的酷炫。不过可能要改一下边界定义，不重要吧。大概。

这个时候聪明的小朋友们就要问了：是不是对于任意组合类，都有 \(\mathcal{A}=\mathcal{E}+\mathcal{A}\) 啊？即 \(A(x)=1+A(x)\)。
其实这个问题不是聪明的小朋友们问的，是我刚刚想出来的。出现这种情况只可能是因为我对中性类和中性对象的定义不够完整。如果够完整的话就不会出现这种问题了。但是这只是一个小学生的学习笔记，所以不用纠结那么多。大概吧。

这个时候聪明的小朋友们就要问了：你这个东西有啥用啊？还不是要我去观察。而且和我直接用生成函数去做没有任何区别。

那是因为，这个是在讲组合类。符号化方法还在后面。更多内容请参考《解析组合学》。我休息一会再来写。