培玉 · 一试
2019 年全国高中数学联赛一试（A 卷） · 第 8 题
将6个数 按任意次序排成一行，拼成一个8位数（首位不为0），求产生的不同的8位数的个数。
作答
分数写 a/b，根号写 √ 或 sqrt，π 写 pi 也可以。
解析
提示
先独立尝试，再展开工具说明与想法来源。
思路
可把“表示”为点、保持拼接结果的局部变换为边，连通分量对应同一结果；这是计数辅助模型，不需图论前置知识。对一个点、一条边、一个四边形，点数减边数再加四边形数均为 ，所以可以逐类校正重数。
想法从哪来：先把每个给定数当成一个完整的块排列，可以数出合法表示数，却还没数出不同的数字串。值得先找反例：长块的数字恰好也能由两个单字符块拼出，这会让不同的分块方式落到同一个结果。这里的重点是重新分词，而不是普通的“有重复元素的排列”。 可以把一次改分块看作连接两种表示的一条边：把长块拆成两块，同时把另一处相邻的两个单字符块合并；两处不必紧挨，数字串仍不变。只有两种长块会引起歧义，先分别合并各自造成的成对重复；若两种歧义同时出现，四种表示会连成一个四边形，前面又多扣了一次，应补回。还须证明没有别的分词歧义：从左向右找第一次不同的分块位置，只可能以长块的首字符开头，随后由各单字符仅有一个限制后续。首位非零要在每一类合并中单独保留。
不同的排列可能拼成同一串，必须按合法的两种重新分词关系合并。
解答
把6个数先看作有标签的块，首块非0共有 个排列。两个表示拼成相同数字串，只能通过交换块20与相邻的块2、0，或交换块19与相邻的块1、9来得到；因为只有1、2能作为长块的首字符，且各单字符块仅有一个，分词歧义只在这两对块内。把每种表示看作顶点、一次这种交换看作边。第一种交换有 条边；第二种有 条边，排除了单独0在首位。两种交换同时存在时得到四个顶点组成的方形，每个这样的分量被边多扣一次；同时有2后接0与1后接9的有标签排列有 个，故方形有 个。各等价类是单点、一条边或这样的方形，所以数字串数为 。
复核
分母2、4是表示重数而非任意排列对称。穷举全部720个排列（去掉0在首位的120个，剩600个合法表示）复核：恰有1种表示的数字串408个，恰有2种表示的84个，恰有4种表示的6个；共 串，表示数 。
方法总结
拼接题的计数对象是字符串，先证明所有分词歧义，再校正表示的重数。
为什么评为 F4（会透露解法方向）
不同的排列可能拼成同一串，必须按合法的两种重新分词关系合并。
已记下，谢谢！