培玉 · 一试
2023 年北京预赛
F3填空题经典的计数模型
现有 位同学报名博物馆的志愿讲解活动，活动从上午 点开始到下午 点结束，每小时安排一场公益小讲堂，每场需要 位同学为参观的游客提供讲解服务。为避免同学们劳累，馆方在排班时不会让同一人连续讲解 场，并且第一场与最后一场需要两位不同的同学负责。则馆方共有种排班方式。
作答
分数写 a/b，根号写 √ 或 sqrt，π 写 pi 也可以。
标准答案：
解析
思路
把八场讲解看作八个顶点，相邻场次及首尾场次相连，安排等价于十一种颜色对八边形正常着色。
解答
上午九点至下午五点共有八场。固定第一场的一位同学，记 为前 场相邻不同且末场与首场相同的排法数。相邻不同的全部前 场有 种；只有末场不等于首场的排法可以再接首场同学，故
归纳或展开得 。于是固定首场后，满足末场不同的八场排法数为 。首场有十一种选择，最终
复核
同一学生可在不相邻场次重复出现，题目没有要求11人全部上场。首尾不同正是补上八边形的闭合边；不是把一条八顶点路径的着色数 直接作为答案。
方法总结
首尾也有禁邻条件时，把排班闭合成环，并按末色是否等于首色递推。
为什么评为 F3（会透露解法方向）
须识别首尾约束把八次排班闭合为环，并用末位是否等于首位的两状态递推计数。
已记下，谢谢！