培玉 · 一试
2023 年全国高中数学联赛一试（A 卷） · 第 8 题
八张标有 的正方形卡片构成下图。现逐一取走这些卡片，要求每次取走一张卡片时，该卡片与剩下的卡片中至多一张有公共边（例如可按 的次序取走卡片，但不可按 的次序取走卡片），则取走这八张卡片的不同次序的数目为。
作答
分数写 a/b，根号写 √ 或 sqrt，π 写 pi 也可以。
解析
提示
只需保留卡片之间的公共边关系。
思路
所得结构是以 为分叉点、三条支链长度分别为 的树；按最后留下的卡片分类，可以把限制转为几条固定次序的交错排列。
解答
把卡片视为顶点，有公共边时连线，得到长链
以及连接 与 的一条边。每次操作恰好删除当前树的一片叶子；只剩一个顶点时也允许删除。
固定最后取走的卡片 。树上任何其他卡片，都必须在其通向 的相邻卡片之前取走：否则该相邻卡片被取走时，朝向 和朝向此卡片的两个方向仍有卡片，违反规定。 反之，只要每张卡片都在朝向 的相邻卡片之前取走，它被取走时至多剩一个邻居，故次序合法。于是只需计数这些先后关系的排列。
| 最后卡片 | 每个固定末项的次序数 | 同类末项个数 |
各项含义如下：末项为 时，交错排列两条各长 的固定次序支链和单张 ；末项为 时， 倒数第二，前六张由两条支链交错排列。 末项为 时，一侧为固定次序 ，另一侧含五张卡片，其末项为 ，前四张是 与 的 种交错；两侧再作 种交错。 末项为 时，一侧只有 ，另一侧六张内部有同样的 种次序；末项为 时，最后四张被迫依次为 ，此前只有 与 的 种交错。另三种末项由对称性得到。
因此所求数目为
复核
八种末项互斥且穷尽；逐步检查全部 种排列的辅助枚举给出的末项计数依次为 ，与证明中的分类完全一致。枚举仅作交叉检查，计数结论由上述分类给出。
方法总结
删除规则依赖邻接关系时，可先画出关系图；树的删叶次序在固定末项后，转为“远端先于近端”的交错排列。
为什么评为 F3（会透露解法方向）
关键转化是把删卡片视为删叶并固定最后一张，此后各类都归结为固定次序支链的交错排列。
已记下，谢谢！