组合类的序列构造 | Codeboy's Blog

形式陈述

给定组合类 $\mathcal B$ ，其长度为 $k$ 的序列类为

\operatorname{SEQ}_k(\mathcal B)=\mathcal B^k,

对象是有序元组 $(\beta_1,\ldots,\beta_k)$ ，大小按组件相加：

|(\beta_1,\ldots,\beta_k)|=\sum_{j=1}^k|\beta_j|.

自由序列构造定义为

\operatorname{SEQ}(\mathcal B) =\biguplus_{k\ge0}\operatorname{SEQ}_k(\mathcal B),

其中 $k=0$ 给出唯一空序列 $\varepsilon$ 。若 $\mathcal B$ 没有大小零对象，即 $B(0)=0$ ，符号方法给出

\operatorname{SEQ}_k(\mathcal B)\longleftrightarrow B(z)^k, \qquad \operatorname{SEQ}(\mathcal B)\longleftrightarrow \sum_{k\ge0}B(z)^k=\frac1{1-B(z)}.

这套公式对无标号类的 OGF 与标号类的 EGF 都成立；标号情形把每个乘积理解为标签集的有序划分。还常用

\operatorname{SEQ}_{\ge k}(\mathcal B) \longleftrightarrow\frac{B(z)^k}{1-B(z)}.

若每个组件的大小至少为一，那么固定总大小 $n$ 时，只有 $k\le n$ 的序列长度可能贡献。因此上面的无限和在逐个系数上其实都是有限和：这既证明形式几何级数合法，也说明构造后的组合类仍保持每层有限。

直觉

序列构造记录“先后次序”。同样两个组件， $(\beta_1,\beta_2)$ 与 $(\beta_2,\beta_1)$ 一般是不同对象。长度固定时，每多一个位置就多乘一个 $B(z)$ ；允许任意长度，就把所有幂相加成几何级数。形式级数的复合条件 $B(0)=0$ 也有直接组合含义：每添一个组件必须让总大小有所增长。

SEQ 的关键不是对象排成一行的图像，而是分解边界可辨。一个结果对象必须能唯一恢复第一个、第二个乃至最后一个组件。若切分位置不唯一，几何级数会把同一对象按多种切法重复计算。

例子与边界

把一个正整数部分看作非空原子序列：

\mathcal P=\operatorname{SEQ}_{\ge1}(\mathcal Z), \qquad P(z)=\frac z{1-z}.

整数的有序合成是这些正部分组成的序列，

\mathcal C=\operatorname{SEQ}(\mathcal P), \qquad C(z)=\frac1{1-P(z)} =\frac{1-z}{1-2z}.

因此 $[z^0]C(z)=1$ ，而 $n\ge1$ 时 $[z^n]C(z)=2^{n-1}$ 。这个系数可复算：在 $n$ 个连续原子之间有 $n-1$ 个空隙，每个空隙独立选择切开或不断开，正好决定一个合成。例如 $4$ 的八个合成对应三个空隙的八种切法。

条件 $B(0)=0$ 不能省略。若 $\mathcal B$ 含一个空对象，则任意序列都可在组件间插入任意多个空对象，大小不变却得到无限多个对象；代数上， $1-B(z)$ 的常数项不再可逆。若只允许至多一个空组件或固定长度，则可另作有限构造，但那已不是上述自由 SEQ。

SEQ 也不适用于忽略顺序的组件集，更不适用于只把旋转视为相同的环形排列。前者应使用 SET/MSET，后者应使用 CYC；把三者都翻译成几何级数会系统性地误计对称性。

推论与应用

词、路径的步序列、平面根树的有序子树、整数合成与正则语言都自然使用 SEQ。若递归规格形如

\mathcal T=\mathcal Z\times\operatorname{SEQ}(\mathcal T),

便得到隐式方程 $T=z/(1-T)$ ，再由系数提取获得 Catalan 数。长度还可用变量 $u$ 标记：

\operatorname{SEQ}(\mathcal B) \longleftrightarrow\frac1{1-uB(z)},

于是 $[u^kz^n]$ 同时记录组件数与总大小。该二元标记在分析组件数量的均值和极限定律时尤其有用。

参考资料

Philippe Flajolet and Robert Sedgewick, Analytic Combinatorics, Cambridge University Press, 2009, Chapters I–II, sequence constructions。
Robert Sedgewick and Philippe Flajolet, An Introduction to the Analysis of Algorithms, 2nd ed., Addison-Wesley, 2013, §3.2。
Herbert S. Wilf, generatingfunctionology, 3rd ed., A K Peters, 2006, Chapter 2。

形式陈述 ​

形式陈述