Knuth 的 2022 圣诞三重奏终章
经过了前面三篇（ 一 twintree 树，二 baxter 数，三 floorplan 画） 看似“毫无关系”的介绍，关子也到此结束，终于要揭露他们之间的关系了。相信看完这篇你也能感受到这些数据结构和数学的奇妙之处。
Floorplan -> Baxter
继续摆出上次的划分，注意从左下角到右上角我们依次写出字母，这也是当时重画图形的顺序，\(EDFACIHJGB\)，这本身就是一个 baxter 排列， 再来复习下它的定义（我发现之前第二篇理解错了，已经更正）：对于任意的 j 在 j+1 之前之间的数（字母），它们之间的【比 j 小的】都排在【比 j+1 大的】之 前，反之亦然。 可以发现连续 3 个及以下一定满足，我们只要检验 4 个或以上的就行，比如 \(F\) 和 \(G\) 之间有 \(ACIHJ\)，比 \(F\) 小的 \(AC\) 排在比 \(G\) 大的 \(IHJ\) 的前面，再比如 \(D\) 和 \(C\) 之间（这是递减）有 \(FA\)，比 \(D\) 大的 \(F\) 排在比 \(C\) 小的 \(A\) 之前，也是递减。你可以验证所有的组合，所以 floorplan 可以转换成 baxter 表示。
Baxter <-> Twintree -> Floorplan
同时，这个 baxter 也可以表示成 twintree 的形式，我们正向和反向的顺序分别插入二叉树，如下图 (点击可看大图)
注意到 T0 的节点左上角和它的左子树呈 \(\vdash\) 关系，比如树和图里的 \(ED\)，而节点的右下角和它的右子树呈 \(\bot\) 关系，同理，T1 的左右子树分别在右上角和左下角呈 \(\top\) 和 \(\dashv\)。这说明 baxter 排列和 twintree 可以相互转换，twintree 也能表示成 floorplan。
另外提一句，观察 T0 从 \(E\) 开始的右子树是 \(EFIJ\)，它们恰好是图上以底边为下边界的 4 个长方形，而左子树 \(EDA\) 恰好是左边向上的一排。
细心的同学发现原来 floorplan 图里的坐标在树上体现不出来，确实如此，我在这里分享原图，感兴趣的同学可以在树的基础上标记出来，看看你能新发现什么。
小结
通过上面不太严谨的表达，我们已经可以看到这三个看似无关的表达，其实却是互通的，每个都可以转化成另一种形式。事实上，根据这篇论文 n 个长方形所组成的 floorplan（准确地说是 mosaic floorplan，区别于 slicing floorplan）的个数和 baxter 数是一样的。 另外在 Knuth 视频的最后也展示了这三种表达能通过程序相互转化（不包括 floorplan 的坐标）。 这就是 Knuth 圣诞三重奏所有要讲的，视频里也不忘推荐下他将要出版的 TAOCP 4B，出现在第 7 章的大量练习中，期待中文译本国内也能尽快买到。
