1. 三重奏其一 twintree
2. 三重奏其二 baxter
3. 三重奏其三 floorplan
4. 三重奏终章

上一篇 讲了 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 上看到，这里就不贴了。

这篇介绍非常短，这个排列有啥用呢，深呼吸，第三篇会长一些，但我们快接近真相了。