有 个字母 、 个字母 、 个字母 (相邻字母没有区别),将它们 排成一排,要求每个 的左侧或右侧相邻的位置至少有一个 。则所有满足条件的 排列总数为。
分数写 a/b,根号写 √ 或 sqrt,π 写 pi 也可以。
先删去两个 ,按 的连续段数分类骨架;插回时区分两个不同空隙与同一个空隙。
删去两个 后,得到由四个 、八个 组成的骨架。设 恰有 个非空连续段,其中 。把四个 分成 段有 种,再从八个 的九个空隙中选 个放入这些段,故骨架数为
骨架中有 个 内部空隙;与至少一个 相邻的空隙总数为 。 若把两个 放在不同空隙,选法为 。若放在同一空隙,要使两个 各自仍与 相邻,必须形成 ,选法恰为 。因此所求为
同一个首尾空隙只能让一个相邻的 接触 ,所以不能容纳两个 ;同空隙情形仅保留 内部空隙。删除操作唯一恢复骨架及插入位置,因此不同段数、不同插法之间没有重计;相同字母的副本未加标号。
特殊字符的邻接计数可先删去特殊字符,但插入多个字符时要重新检查它们是否互相隔开所需的邻居。
需按普通字符连续段数分类骨架,再分别计两个特殊字符放不同空隙与同一空隙;共享邻接和相同字符去重是主要难点。
核心工具:把对象唯一编码后分类计数
已记下,谢谢!