培玉 · 一试
2023 年全国高中数学联赛一试（B 卷） · 第 8 题
F3填空题组合计数综合
七张标有 的正方形卡片构成下图。现逐一取走这些卡片，要求每次取走一张卡片时，该卡片与剩下的卡片中至多一张有公共边（例如可按 的次序取走卡片，但不可按 的次序取走卡片），则取走这七张卡片的不同次序的数目为。
作答
分数写 a/b，根号写 √ 或 sqrt，π 写 pi 也可以。
标准答案：
解析
提示
图形的公共边关系构成一棵树。
思路
固定最后一张卡片后，每条通向末项的支链必须从远端开始删除，便可按末项计数固定次序的交错排列。
解答
用顶点表示卡片，用边表示有公共边，得到长链
以及连接 的一条边。合法操作就是依次删除叶子，最后删除唯一剩下的顶点。 固定末项 后，每个其他顶点都必须先于其通向 的相邻顶点删除；反之，遵守这些先后关系时，每次删除的顶点至多剩一个邻居，因此一定合法。
按最后一张卡片分类，得到
| 末项 | 次序数 | 计数说明 |
| 交错排列 ；； | ||
| 倒数第二，前五张交错两支链 | ||
| 单张 与含 的五张交错 | ||
| 最后三张为 | ||
| 与含 的四张交错 | ||
| 单张 与其余五张交错 | ||
| 最后四张为 |
表中，当一支最后为 且还包含 时，必须先交错排列 与 ，有 种；当该支包含 时，先交错排列 与 ，有 种。这分别解释表中的两个内部计数因子。 七种末项互斥且穷尽，因此总数为
复核
逐步检查全部 种排列得到的末项计数为 ，与上述分类一致。题面给出的合法次序也满足每次至多留一个邻居的规则。
方法总结
在树形邻接结构上，固定末项可将局部删除规则化为全局先后关系；计数时分别说明支链内部次序与支链之间的交错数。
为什么评为 F3（会透露解法方向）
将删卡片规则转为树的删叶次序，并固定末项后，七种情况均由支链内部次序和交错排列计数。
已记下，谢谢！