Y序列

$Y$ 序列，一般指 $1 - Y$ ，一种Worm型序数记号。

定义

合法表达式

一个合法的 $1 - Y$ 表达式是以 1 开头的正整数序列，即形如

$(a_{1}, a_{2}, \dots, a_{n}) (n, a_{1}, a_{2}, \dots, a_{n} \in ℕ, a_{1} = 1)$

的序列。

例如： $(1, 4, 6, 4)$ 和 $(1, 1, 4, 5, 1, 4)$ 都是合法的 $1 - Y$ 表达式，而 $(1, 2, π)$ 不是。

结构

$1 - Y$ 的合法表达式可分为零表达式、后继表达式和极限表达式。

零表达式指 $n = 0$ 的表达式，即空序列；
后继表达式指 $n > 0, a_{n} = 1$ 的表达式，即末项为1的非空序列；
极限表达式指 $n > 0, a_{n} > 1$ 的表达式，末项不为1的非空序列。

对于 $1 - Y$ 的一个极限表达式 $(a_{1}, a_{2}, \dots, a_{n})$ ，定义以下术语：

行标与列标

设想我们在一个无限大的矩阵下工作，从左往右是第1,2,...列，从下往上是第0,1,...行。与 $0 - Y$ 不同的是：

行标现在可以是一个超限序数，例如第 $ω$ 行。
一些项现在可以不赋予任何数作为取值，这些项称为空项，记作 $\emptyset$ 。

第 $α$ 行第 $j$ 列的项记为 $x_{α, j}$ 。

初始时，我们有 $x_{0, j} = a_{j}$ ， $1 \leq j \leq n$ 。

后继序数行的父项 & 阶差项

对于后继序数 $α + 1$ 和非空项 $x_{α + 1, j}$ ，它的父项是与它位于同一行，且满足以下条件的最右侧非空项 $x_{α + 1, k}$ ：

$k < j$ 且 $x_{α + 1, k} < x_{α + 1, j}$ 。
$x_{α, k}$ 是 $x_{α, j}$ 的祖先项。

这里“祖先项”的定义类似于BMS：一个元素自己，以及它的父项、父项的父项、父项的父项的父项......共同构成它的祖先项。

对于第0行的项 $x_{0, j}$ ，它的父项是与它位于同一行，且同时满足 $k < j$ 和 $x_{0, k} < x_{0, j}$ 的最右侧项 $x_{0, k}$ 。

如果满足上述条件的项不存在，那么 $x_{α + 1, j}$ (或者 $x_{0, j}$ )的父项不存在。特别地，等于1的项的父项不存在。

对于任何序数 $α$ ，项 $x_{α, j}$ ：

如果它有父项 $x_{α, k}$ ，则它的阶差项为 $x_{α + 1, j} = x_{α, j} - x_{α, k}$ 。
如果它没有父项，或者为空项，它的阶差项为 $x_{α, j} = \emptyset$ 。

由于第 $α$ 行的项的阶差项构成了第 $α + 1$ 行，称第 $α + 1$ 行的序列是第 $α$ 行的序列的阶差序列。

极限序数行的父项 & 提取

上述定义只给出了后继序数行的项的取值和父项关系。接下来给出极限序数的情形：

设极限序数 $α = β + ω < ω^{2}$ ， $β$ 为极限序数。则定义项 $x_{α, j}$ 如下：

取出最大的非负整数 $p$ 使得 $x_{β + p, j}$ 不为空项，则 $x_{α, j} = x_{β + p, j}$ 。这些项 $x_{β + p, j}$ 称为主项。

对大于1的项 $x_{α, j}$ 定义如下概念：

设 $x_{α, j} = x_{β + p, j}$ ，令 $a = j$ 。
设 $x_{β + p - 1, a}$ 的父项为 $x_{β + p - 1, k}$ 。如果 $x_{β + p - 1, k}$ 是主项，或者 $x_{β + p, k}$ 是主项，称 $x_{α, k}$ 是 $x_{α, j}$ 的拟父项。
否则令 $a = k$ 并回到第2步，直到找到某个主项，设其列标是 $l$ ，称 $x_{α, l}$ 是 $x_{α, j}$ 的拟父项。

对于极限序数 $α$ 和大于1的项 $x_{α, j}$ ，它的父项是与它位于同一行，且满足以下条件的最右侧项 $x_{α, k}$ ：

$k < j$ 且 $x_{α, k} < x_{α, j}$ 。
$x_{α, k}$ 是 $x_{α, j}$ 的拟祖先项。

这里“拟祖先项”的定义是：一个元素自己，以及它的拟父项、拟父项的拟父项......共同构成它的拟祖先项。

如果满足上述条件的项不存在，那么 $x_{α, j}$ 的父项不存在。另外，等于1的项的父项不存在。

以上定义项 $x_{α, j}$ 时，将所有位于 $β$ 到 $β + ω$ 之间的行中每一列的最上方非空项取了出来，并“提”到了 $α = β + ω$ 行(还保留了其下的一些父项关系)，这就是提取(Extraction)的含义。

注：此处的“主项”，“拟父项/拟祖先项”是编者引入的等价的临时定义。在主流的定义与教程中，通常使用山脉图(见下文)定义此部分内容。

末列与坏根

第 $n$ 列称为末列。

对于末列的某一项 $x_{α, n}$ ，它的父项设为 $x_{α, r}$ 。如果在计算到某行(第 $γ$ 行)时有 $x_{γ, n} - x_{γ, r} = 1$ ，则称 $a_{r}$ 为坏根，称第 $r$ 列为根列。

以上给出了 $1 - Y$ 极限表达式 $(a_{1}, a_{2}, \dots, a_{n})$ 的完整寻找坏根流程。

山脉图

此部分内容来自梅天狸的知乎内容

1,3前的Y序列山脉图

这一部分的1-Y，山脉图与0-Y是相当相似的。区别仅在于，每个序列的1在阶差序列中将不再是1，而是空项。例如， $Y (1, 2, 4, 5, 7)$ 的阶差序列为 $(\emptyset, 1, 2, 1, 2)$ ，二级阶差序列为 $(\emptyset, \emptyset, 1, \emptyset, 1)$ ，山脉图如图1所示。找父项时，如果沿左腿向下走一步之后无法向上走，那么认为这一项在当前行不存在父项。例如在图1中，如果右上角的是2，那么它找父项时不能连续沿左腿向下走两步再沿右腿向上两步，找到前面的1。(仅用来举例，实际上右上角是2的时候不标准)

图1，Y(1,2,4,5,7)的山脉图

再来个 $Y (1, 2, 4, 8, 10, 7, 12)$ 的例子，如图2。可以看到除了会出现缺项以外，这部分的1-Y山脉图规则和0-Y没什么不同。

图2，Y(1,2,4,8,10,7,12)的山脉图

1,3后的Y序列山脉图

对于一个Y序列的山脉图，它被展开完全的一大特征是所有列的最上层都为1。但按照前一部分的规则，展开 $Y (1, 3)$ 的结果会是这样，如图3：

图3

此时，第二列的最上层是2而不是1，表明展开未完全。但这一层，又已经只剩它一个数，它没有同一层的父项。因此，我们需要添加新规则以继续展开它。

这个新规则，便是1-Y的核心“提取”。

所谓提取，指的是将山脉图所有列最上层的数取出来构成一个新的序列，同时保持原来的父项关系。用稍复杂的 $Y (1, 3, 7, 14, 7, 13)$ 举个例子,如图4：

图4，Y(1,3,7,14,7,13)的山脉图(提取前)

我们从上面这个山脉图中，能提取出的新序列就是 $(1, 2, 2, 1, 2, 2)$ 。所谓的“保持原来的父项关系”，指的是这个提取出的新序列，在寻找待定父项时要回到原来的山脉图中寻找。例如在上面的例子中，新序列最后两项的2的父项都是首项的1，而不是第四项的1。

把这些信息画在一个山脉图上，会像这样,如图5：

图5，Y(1,3,7,14,7,13)的山脉图(提取后)

这里的虚线表明经历了一次提取操作。这些灰色的“右腿”将原山脉图每一列顶端的项和提取序列对应的项相连，灰色的“左腿”由这些顶端项沿原山脉图中的左腿向下走一步，再沿右腿向上走一步，重复这个过程直到遇见另一个顶端项得到。由于这些“左腿”和“右腿”不直接表示父项关系，所以用灰色表示。现在，要找提取序列中某一项的父项，也只需要像之前我们做的那样，先沿灰色的左腿向左下，再沿灰色的右腿向上就可以了。

对提取序列再次取阶差、作山脉图，直到每一列的最上端都为1为止，就得到了完整的山脉图。例如，下面是 $Y (1, 3, 7, 14, 7, 13)$ 的完整山脉图，如图6：

图6，Y(1,3,7,14,7,13)的完整山脉图

如果提取后的序列作山脉图之后，仍不能使每一列最上端都为1，那么就需要再次提取。下面的 $Y (1, 4, 11, 21)$ 就是一个要提取两次的例子，如图7：

图7，Y(1,4,11,21)的山脉图

网站whY mountain可以绘制 $1 - Y$ 的山脉图。

展开

$1 - Y$ 的展开难度远高于0-Y。

对于 $1 - Y$ 的极限表达式 $Y (a_{1}, a_{2}, \dots, a_{n})$ ，其基本列第 $q$ 项可按以下方式确定：

先作出其山脉图，求出根列 $r$ ，根列右侧的结构称为坏部。

设序列一共进行了 $m$ 次提取操作，此时山脉图被分为 $m + 1$ 层，第 $k$ 层的行标位于 $ω (k - 1)$ 和 $ω k$ 之间。

$1 - Y$ 的展开是从上到下逐层进行的。

对于最上面一层，其展开规则和 $0 - Y$ 类似：

先将末列行标第二大的项 $x_{ω m + p, n}$ 减1(行标最大的项为1)，删除本层坏部第 $ω m + p$ 行以下元素的数值。
将本层的坏部平移并复制在山脉图末尾，复制 $q - 1$ 次。“坏部平移”是指左右腿及端点同时平移
特别地，如果某一条左腿的端点位于根列左侧，复制时左腿的端点不向右平移。
接下来，从根列右侧开始从上到下，每一行从左到右填入数字。对于某个位置，若其向上通过右腿移动到值为 $x$ 的项，然后向左下通过左腿移动到值为 $y$ 的项，则这个位置应填入 $x + y$ 。

第 $k (1 \leq k \leq m)$ 层山脉图的展开需要引入几个概念^[1]：顶点元素、平移边、轮廓边、参考边。

顶点元素的定义如下：从本层根列的主项出发，重复“沿左腿向上走一步，再沿右腿向下走若干步(终点的行标不能低于起点)”，得到的所有主项称为顶点元素。或者说，顶点元素是在提取之后以根列为“拟祖先项”的主项。

平移边、轮廓边、参考边的定义和顶点元素有关：

轮廓边：从一个顶点元素出发，重复“沿左腿向上走一步，再沿右腿向下走一步”直至无路可走，中间经过的所有边称为轮廓边。
平移边：根列右侧的非轮廓边称为平移边。
参考边：从本层根列的主项出发，得到的所有轮廓边称为参考边。取基本列第 $q$ 项时，根列右边的结构需要循环复制 $q - 1$ 次。在每一轮复制的过程中，三种边的行为如下：

平移边只需要简单地向右平移。特别地，若左腿的端点位于根列左侧，则左腿的端点保持不动。这一点和 $0 - Y$ 的规则类似。
轮廓边在向右平移的同时，还需要向上提升它的高度。具体来说，提升的高度为最右列和根列顶点元素的高度差。
参考边在向右平移后，还要向上复制，用来填补平移边和轮廓边之间的空隙。

在所有的边复制完成之后，我们还是按照从上到下、从左到右的顺序向山脉图填入数字。

首先，本层每一列最上方的项等于上层最底行(即第 $ω k$ 行)对应项，即保持虚线两端的对应关系

填充完最上方的数字之后，按照之前相同的规则继续填充其它项，就得到了第 $k$ 层的山脉图。

从第最上面一层开始，依次对每一层进行复制和填充，直到填充完第1层，得到第0行的序列就是 $Y (a_{1}, a_{2}, \dots, a_{n})$ 的基本列第 $q$ 项。

举例：

图8，Y(1,2,4,8,10,8)的山脉图

Y(1,2,4,8,10,8)的展开：首先，画出山脉图如图8：

图9

图中，标红的1便是根元素。把它所在的行按照0-Y规则展开为1,2,1,1,2,1,1,2,1,1,……，随后从上向下逐行复制山脉图，得到展开式。注意：第二行靠右侧的2父项位于根列左侧，它始终维持不变，如图9

Y(1,3,4,3)的展开：首先，我们画出它的完整山脉图，如图10：

图10

用红色标出了这个序列的根元素，可以看到，它位于最左列。因此，最左列是这个序列的根列。接着，我们展开上半部分，同时对下半部分的元素进行标注，如图11：

图11

在这个序列中，下半部分的所有边都是轮廓边，因为它们都可以由最左侧的顶点元素

沿左腿向上一步之后沿右腿向下一步，并重复这个过程得到。这对我们来讲毫无疑问是个好消息。

接着，我们把这些轮廓边向右复制，同时向上提升高度。由于最右侧的顶点元素位于第二行，而根列的顶点元素位于第一行，所以每次复制的时候，我们都需要把这些边向上提升一行。如图12

图12

现在，我们可以看到山脉图下半部分的右下方出现了空隙。这些空隙就需要我们使用参考边填充进去了。找出参考边，并进行复制，直到空隙被填满。如图13：

图13

图14

Y(1,3,4,2,5,6,5)的展开：首先，还是画出它的山脉图，如图14

这次的根列是第四列。展开最上层。这次的轮廓边只有两条了。底下的那些通通是平移边。进行向右的复制，同时提升轮廓边的高度。在这个例子中，依旧是每复制一次，高度提升一行。如图15：

图15

找到参考边，复制，填满空隙。注意第六列的1在复制时不向上提升。如图16

图16

图17

Y(1,4,9,4)的展开：先画出山脉图。如图17

展开上层，标注中层。如图18

图18

复制中层的轮廓边和平移边(这个例子中没有)。把参考边填进去。如图19

图19

现在我们完成了中层的展开，只需要再重复一次就大功告成了。由于这部分操作没什么不同，就一步到位了。如图20

图20

强度分析

主词条：Y序列 VS TBMS、Y序列 VS BTBMS、fffz分析

对Y序列进行强度分析是一个微妙的事情——它已经是googology最强的记号之一了，有能力和它对照的记号大多是与它类似的山脉型记号（如MN系列、MMS、ω-Y等），只有fffz、FOS、BLP等记号与其不存在表面上的相似性，但它们要么定义不全，要么分析困难。这里展示一些Y序列与TBMS的对照的关键节点。


Y序列	TBMS
1,3	$(0) (1^{ω})$
1,3,2,5,4	$(0) (1^{ω}) (1, 1)$
1,3,3	$(0) (1^{ω}) (1^{ω})$
1,3,4	$(0) (1^{ω}) (2)$
1,3,4,2,5,6,5	$(0) (1^{ω}) (2) (1^{ω})$
1,3,4,2,5,7	$(0) (1^{ω}) (2, 1)$
1,3,4,2,5,7,5	$(0) (1^{ω}) (2, 1^{ω})$
1,3,4,2,5,7,10	$(0) (1^{ω}) (2, 2)$
1,3,4,2,5,7,10,5	$(0) (1^{ω}) (2^{ω})$
1,3,4,2,5,7,11	$(0) (1^{ω + 1})$
1,3,4,2,5,8	$(0) (1^{ω^{2}})$
1,3,4,2,5,8,8	$(0) (1^{ω^{3}})$
1,3,4,2,5,8,10	$(0) (1^{Ω})$

参考资料

↑ Suzuka梅天狸：Y序列专题(4)——让我们请出主角登场(下) ，https://zhuanlan.zhihu.com/p/671375564

[1] Suzuka梅天狸：Y序列专题(4)——让我们请出主角登场(下) ，https://zhuanlan.zhihu.com/p/671375564

[1]