每日一题[3685]环染色

2023年全国高中数学联赛北京市预赛 #12

现有 $11$ 位同学报名博物馆的志愿讲解活动，活动从上午 $9$ 点开始到下午 $5$ 点结束，每小时安排一场公益小讲堂，每场需要 $1$ 位同学为参观的游客提供讲解服务．为避免同学们劳累，馆方在排班时不会让同一人连续讲解 $2$ 场，并且第一场与最后一场需要两位不同的同学负责，则馆方共有_____种排班方式．

答案    $100000010$．

解析    本质上为用 $11$ 种不同的颜色给含有 $8$ 个部分的圆环染色的问题，根据环染色的计数公式 $^{[1]}$，所求排班方式数为

$$10^8+10\cdot (-1)^8=100000010.$$

备注    $[1]$ $a_n=(k-1)^n+(k-1)\cdot (-1)^n$，其中 $k$ 为颜色数，$n$ 为圆环上的区域数．