Knuth 的 2022 圣诞三重奏终章
经过了前面三篇（ 一 twintree 树，二 baxter 数，三 floorplan 画） 看似“毫无关系”的介绍，关子也到此结束，终于要揭露他们之间的关系了。相信看完这篇你也能感受到这些数据结构和数学的奇妙之处。
Floorplan -> Baxter
Knuth 的 2023 圣诞三重奏其三 Floorplan
这次是三重奏的最后一篇，这篇依然和前两篇（一 twintree，二 Baxter）看起来没什么关系。
这次研究的是在一个长方形的地板上进行划分小长方形的方法，首先排除“榻榻米”划分，是指每两个小长方形如果相邻只能边相邻，不允许角相邻，也就是说不允许组成一个十字的缝隙，只允许出现 T 字形缝隙，4 种方向如 \(\vdash\) \(\dashv\) \(\bot\) \(\top\)。如下是一个 floorplan 的划分
Knuth 的 2023 圣诞三重奏其二 Baxter permutation
上一篇 讲了 twintree 是一种数据结构，这篇来介绍一个离散数学上的排列。
Baxter permutation 是这样一种排列，对于每一对 j 和 j+1的位置关系，如果 j 排在 j+1 前，那它俩之间的数字必须严格递增，反之它俩之间的数字必须严格递减，那么所有（如果有）比 j 小的必须排在比 j+1 大（如果有）的前面，反之大的排在小的前面，但小的和小的及大的和大的之间顺序并不重要，比如 3142 就不符合，因为 3 和 2 之间的 14 应当像 32 一样递减，这个被 Knuth 称为 pi permutation，因为它是 3.1415 的近似，另一个不符合的是 2413。给出更形式化的定义像这样，\(\sigma(i)\)表示数字 i 的下标：
\(i < j < k, \sigma(j) < \sigma(i)<\sigma(k)<\sigma(j+1) \text{ or }\sigma(j+1) < \sigma(k)<\sigma(i)<\sigma(j)\)
上面两个排列是 1 到 4 的排列中唯二不符合的排列，因此 4 以内是 baxter permutation 的个数是 \(4!-2=22\)，实际的计算公式可以在 wiki 上看到，这里就不贴了。
这篇介绍非常短，这个排列有啥用呢，深呼吸，第三篇会长一些，但我们快接近真相了。
Knuth 的2023圣诞三重奏其一 Twintree
引言
Knuth 今年圣诞在 Stanford 做了一次演讲，讲了三种看似毫无关联的主题，但最终能相互转换，这系列文章将会分成 4 部分依次介绍这 3 个主题，最后再将这些“调料”烩在一起组成一道“圣诞大餐”。感兴趣的可以直接观看原视频。
如何公平地分蛋糕
最近看了李永乐老师的视频，讲如何 2 个或 3 个公平地分蛋糕，2 人其实很简单，一个人切 1 刀另一个选就完了，3 个人就会比较复杂，这题建议有娃的父母都掌握，因为国家现在开放三胎了，将来生日聚会用得上（狗头）。这个复杂的分法实际我早在 matrix67 大牛blog 就看过，不过也忘得差不多了，在此也回顾下。
假设
首先我们还是要明确一些假设
