培玉 · 一试
2011 年辽宁预赛 · 第 12 题
F3填空题经典的计数模型
将凸五边形 的每个顶点染上 种颜色之一，使每条对角线的两个端点颜色不同的染色方式共有种（用数字作答）。
作答
分数写 a/b，根号写 √ 或 sqrt，π 写 pi 也可以。
标准答案：
解析
思路
五边形的五条对角线也是一个五边形环，只须计算这个环的合法着色。
解答
按 的顺序看，对角线组成五点环。固定第一个顶点的颜色。令 为前j个顶点依次相邻异色，且末点分别与首点同色、异色的方案数。则
逐次得 。最后还要末点与首点异色，故方案数为 。
复核
首色有5种且顶点有标号，不将旋转或反射的染色视为同一方案；只约束对角线，不额外约束原来的边。
方法总结
环着色可用末色是否等于首色的两状态递推。
为什么评为 F3（会透露解法方向）
按相邻顶点同色的可能结构分类并计数，得到 。
已记下，谢谢！