★ FEATURED ARTICLE 从来没想过一个看起来人畜无害的环形染色问题能把我在纸上绕了两圈才推对。这问题的描述短到一句话就能说完给一个环上的 n 个位置染色每个位置有 m 种颜色可选要求任意相邻两个位置颜色不同问一共有多少种方案。但它完美诠释了什么叫越简单的题越容易在边界翻车——直线染色的答案一眼就能写出来换成环首尾接上的那一刻之前的直觉全都不好使了。这篇文章我想把整个推导链路完整摊开从递推、通项公式到 Burnside 引理处理旋转算同一种的情况再到程序实现和几个让人拍大腿的边界条件。适合正在啃组合数学、刷算法题或者做化学计数、排班安排时碰到同类问题的人直接参考。1. 从直线到环只差一个首尾相邻推法为什么全变了1.1 先把问题说精确环形染色问题这个说法在 OI、ACM 和组合数学教材里都出现过但不同场合下默认的规则有细微差别讨论前一定要先对齐口径。本文讨论的模型是有 n 个位置围成一个环位置之间有 n 条边最后一条边连接第 n 个位置和第 1 个位置给每个位置染一种颜色颜色总数为 m要求每条边连接的两个端点颜色不同求染色方案数。这里先不讨论旋转后算不算同一种也就是说 n 个位置是有编号或者有固定方位的染完之后精确到每个位置的颜色。这种情况下环染色的方案数是一个确定的整数记作 K(n, m)。等到了第 4 节再打开另一个开关——如果环可以旋转甚至翻转旋转后重合的方案只算一次那就得借助 Burnside 引理来数本质不同的方案数。这两者经常被混在一起说但实际是两个完全不同的问题。1.2 直线染色是送分题先拿它当参照物在一条直线或者说一条链上染 n 个点相邻不同色方案数很容易推第一个点任意选有 m 种第二个点只要避开第一个点的颜色有 m-1 种第三个点避开第二个点又有 m-1 种依次类推。所以直线染色方案数是L(n, m) m × (m-1)^(n-1)比如 m3、n3直线染色的方案数是 3 × 2 × 2 12 种。这个公式从小学奥数到大学离散数学翻来覆去出现几乎不会有人记错。但环不是链。环的首尾之间多了一条边最后一个点既要避开前一个点的颜色又要避开第一个点的颜色。第 n 个点的可选颜色数取决于第 n-1 个点和第 1 个点是否同色。这个条件分支一下子就打破了直线公式里那种每步独立的感觉。换句话说直线染色时每个位置都是向前看就好到了环上最后一个位置必须同时向后看和向前看。1.3 拿小环手算一遍体会首尾约束的威力直接看 m3、n3 的最小情形一个三角形三个顶点三种颜色相邻顶点不能同色。因为三角形任意两个顶点都相邻每对点之间都有一条边所以三个顶点只能两两不同色。三色全排列一下3 × 2 × 1 6 种。这个数字没问题。对比一下直线情形下的 12 种。为什么少了一半因为直线染色的 12 种里面有 6 种是首尾同色的第 1 个点选一个颜色第 2 个点从剩下两色里选一个第 3 个点被迫等于第 1 个点的颜色。这种方案在直线上合法一旦把第 3 个点和第 1 个点用一条边接起来就变成了相邻同色非法。所以环形染色不能简单地在直线公式后面乘个避开首色的系数因为最后一个点能选的颜色数量本身就是不确定的。这种不确定性正是整道题的核心难点。2. 两行递推救场把首尾关系拆成两个序列分别算2.1 为什么要引入 h_n 和 k_n 两个辅助量既然末尾点的可选数取决于首尾是否同色那就干脆把首尾同色和首尾不同色拆成两个相互独立的计数问题分别记作 h_n 和 k_n。定义如下考虑直线上 n 个点相邻不同色。h_n首尾同色的方案数k_n首尾不同色的方案数。那么一个简单的恒等式立刻成立h_n k_n m × (m-1)^(n-1)但光有总数不够我们需要的是 h_n 和 k_n 之间的转移关系这样才能从 n 推到 n1。这时候回过头看问题环染色方案数等于哪个把环从某一条边剪开展开成一条直线。展开后这条直线必须满足剪口两端颜色不同否则没法重新接回去。所以环染色方案数 K(n, m) k_n。这是一个非常重要的观察后面所有推导都建立在这个剪开的操作上。2.2 在序列末尾扩展一位推导状态转移假设计算出了长度为 n 的直线序列中 h_n 和 k_n 的值现在往末尾加第 n1 个点看它如何影响首尾状态。第一种情况原序列首尾同色数量为 h_n。此时第 n 个点等于第 1 个点。新加的第 n1 个点想要让整个序列首尾同色它必须等于第 1 个点但这会让它与第 n 个点同色违反相邻不同色所以这种情况对 h_{n1} 的贡献是 0。想要让整个序列首尾不同色新点只需要避开第 n 个点等于首点的颜色有 m-1 种选择。第二种情况原序列首尾不同色数量为 k_n。此时第 n 个点和第 1 个点颜色不同。新点想要让整体首尾同色只能选第 1 个点的颜色而且这个颜色恰好不等于第 n 个点不违反相邻约束所以贡献为 1 种。新点想要让整体首尾不同色要同时避开第 1 个点和第 n 个点的颜色这两个颜色不同所以有 m-2 种。整理成两个递推式h_{n1} k_nk_{n1} (m-1) × h_n (m-2) × k_n这个方程组就是整个环形染色问题递推解法的地基。h 和 k 就像一对咬合的齿轮一个转另一个跟着转。2.3 消元得到二阶递推初值不要想当然有了 h_{n1} k_n立刻得到 h_n k_{n-1}在 n≥2 时成立。把它代入 k_{n1} 的式子就只剩一个未知序列k_{n1} (m-2) × k_n (m-1) × k_{n-1}这是一个标准的二阶线性递推。定初值的时候有个常见的坑。n2 时两个点相邻首尾关系取决于这两个点本身是否同色。由于相邻不同色两个点必须异色所以k_2 m × (m-1)即第一个点 m 种第二个点避开第一个点 m-1 种h_2 0。注意这里是 0不是某个人直觉里以为的 m。我最初推的时候就在这里写错过以为两个点同色就首尾同色忘了相邻不同色的硬约束直接把这个情况干掉了。有了 k_2 和 k_3递推就可以一路算下去。例如 m3 时k_2 6k_3 (3-2)×6 (3-1)×0 6k_4 1×6 2×6 18k_5 1×18 2×6 30。这个数列 6、18、30、66……其实就是三色固定环染色的方案数序列可以在网上查到也可以自己枚举验证。3. 通项公式为什么答案长成 (m-1)^n (-1)^n (m-1)3.1 特征方程破解二阶递推递推式 k_{n1} (m-2) × k_n (m-1) × k_{n-1} 是线性齐次常系数递推解通项有标准套路写出特征方程。x^2 (m-2)x (m-1)移项x^2 - (m-2)x - (m-1) 0。因式分解一下(x - (m-1)) × (x 1) 0所以两个特征根是 m-1 和 -1。于是通项具有形式k_n A × (m-1)^n B × (-1)^n用初值确定系数。k_2 m(m-1)k_3 m(m-1)(m-2)。代入后解得 A 1B m-1。于是得到优美的闭式解K(n, m) k_n (m-1)^n (-1)^n × (m-1)这个公式值得记住。它同时说明了几个现象方案数主要由 (m-1)^n 主导后面的 (-1)^n (m-1) 只是一个符号修正项颜色越少修正项的影响越明显。3.2 另一个更直观的推导用直线方案做容斥如果不喜欢特征方程还可以用更直观的容斥思路再推一遍。环形染色方案数等于直线染色的总方案数减去首尾同色的方案数K(n, m) m(m-1)^(n-1) - h_n前面又知道 h_n k_{n-1}也就是长度为 n-1 的环染色方案数。于是立刻得到一个自我递归的方程K(n, m) m(m-1)^(n-1) - K(n-1, m)从 n2 出发反复代入K(n) m(m-1)^(n-1) - m(m-1)^(n-2) m(m-1)^(n-3) - ... (-1)^(n-2) m(m-1) (-1)^(n-1) K(1)这里如果按 K(1, m) 约定为 0即单点自环相邻不允许就能得到一个等比交错级数求和K(n, m) (m-1)^n (-1)^n (m-1)和特征方程的结果完全一致。这条路线我觉得更适合讲给学生听因为它每一步都有明确的组合意义减掉首尾同色的首尾同色的又可以看成一个缩短了一号的环于是环和直线之间形成了一个递归关系。3.3 用通项公式快速验证前面的手算结果拿通项公式回验第 1 节的三角形例子m3、n3 时(3-1)^3 (-1)^3 × (3-1) 8 - 2 6和枚举结果一致。再验 m3、n42^4 (-1)^4 × 2 16 2 18和递推得到的 18 一致。这套公式对 n2 也成立m3 时 2^2 2 6正好是两个点必须异色的 3 × 2 种。到这里固定位置环形染色问题已经彻底解决。如果只需要这个结果看完上面就可以拿去用了。剩下的问题都围绕它展开。4. 如果旋转算同一种Burnside 引理接管4.1 先分清编号环和本质环现实场景里经常遇到另一种问法一个环有 n 个位置染完色后可以旋转旋转后看起来一样的方案只算一种问一共有多少种本质不同的染色。这就是等价类计数问题。举一个最小的例子三角形三色相邻不同色。前面算过固定位置方案是 6 种——三个位置分别涂上三种颜色。如果允许旋转那么位置1红、位置2黄、位置3蓝和位置1蓝、位置2红、位置3黄可以通过旋转重合算同一种。三个点的问题怎么数把 6 个固定染色方案放在旋转群 C3 下看每个染色方案的旋转轨道大小都是 36 ÷ 3 2所以旋转等价下有 2 种本质不同方案。如果再允许翻转群变成二面体群 D3每个方案的轨道大小变成 6本质不同方案变成 1 种。你看同一个问题对称群选多大答案就变几次。所以拿到题第一件事永远是确认哪些变换算等价。4.2 旋转下的不动点周期片段决定一切要数本质不同方案用 Burnside 引理本质不同方案数 (1/|G|) × Σ 每个变换下的不动点数对旋转群来说有 n 个变换旋转 0 格、1 格、……、n-1 格。旋转 k 格的不动点怎么数假设把环旋转 k 格后染色方案不变。设 d gcd(n, k)那么旋转 k 的操作在位置上产生了 d 个独立循环轨每个循环轨里的位置必须染成同一种颜色。换句话说这个染色方案完全由前 d 个位置的颜色决定并且第 i 个位置的颜色必须等于第 id 个位置的颜色即整个染色呈周期 d。这个周期片段本身必须合法片段内部相邻颜色不同同时片段最后一个位置和第 1 个位置也要不同因为它们是环上的邻居。所以周期片段本质上就是一个长度为 d 的合法环染色方案数正好是 T(d) (m-1)^d (-1)^d (m-1)。因此旋转 k 格的不动点数为 T(gcd(n, k))。特别地旋转 0 格k0dn的不动点数就是全部固定环染色方案数。4.3 用欧拉函数合并同类项给出能算的样子把所有旋转的不动点数加起来按 d 分组统计。n 个旋转里满足 gcd(n, k) d 的 k 的个数是 φ(n/d)其中 φ 是欧拉函数。所以本质不同方案数 (1/n) × Σ_{d|n} φ(d) × T(n/d)来算一个具体的三色六边形旋转等价。m3、n6。n 的因子是 1、2、3、6。d1φ(1)1T(6)66d2φ(2)1T(3)6d3φ(3)2T(2)6d6φ(6)2T(1)0。括号内总和 66 6 12 0 84除以 6得到 14 种。这就是三色六边形在旋转等价下的本质不同染色数。这个例子我建议想深入理解 Burnside 的同学亲手验一遍。把 66 个固定染色按轨道路径分解会出现一批大小为 6 的轨道还有少数大小为 3 甚至 2 的对称染色最后轨道总数正好是 14。验完你会对不动点数目为什么能决定轨道数量有非常直观的体感。5. 程序实现从朴素递推到 O(log n) 的快速幂5.1 朴素 DP理论上最简单如果 n 不大比如 n ≤ 10^6直接按递推式滚动求解就够了。这里用滚动数组只存 k_{n-1} 和 k_{n-2}。def ring_count_dp(n, m): if n 1: return m # 按约定讨论 k2 m * (m - 1) # n2 if n 2: return k2 % MOD k1 0 # 对应 k_1辅助占位 for i in range(3, n 1): cur (m - 2) * k2 (m - 1) * k1 k1, k2 k2, cur % MOD return k2 % MOD注意这里的 k1 只是递推式子在第 3 项时用到的 k_1它的值取决于你如何处理单点环。如果按自环相邻不允许来约定k_1 0这样 k_3 算出来是 m(m-1)(m-2)和通项公式一致。如果按单点无邻居约定k_1 就另说。这个细节写代码前最好确认清楚。5.2 通项公式真正实用的 O(log n)n 一旦达到 10^9、10^18递推就彻底没戏了。这时候直接用闭式公式K(n, m) (m-1)^n (-1)^n × (m-1)用快速幂求 (m-1)^n整个复杂度是 O(log n)。def ring_count_formula(n, m, MOD): if n 1: return m % MOD # 按约定 p pow(m - 1, n, MOD) sign 1 if n % 2 0 else -1 return (p sign * (m - 1)) % MOD一个小坑在取模环境下Python 的 % 运算符对负数会返回非负结果所以直接写% MOD没毛病。但 C 写的时候(p sign * (m-1)) % MOD可能出现负数要记得加 MOD 再取模。5.3 矩阵快速幂不想背通项就构造转移矩阵如果不想推通项也可以用矩阵快速幂直接求二阶递推。递推式k_{n1} (m-2) × k_n (m-1) × k_{n-1}写成矩阵形式[k_{n1}] [m-2 m-1] [k_n ] [k_n ] [1 0 ] [k_{n-1}]初始向量是 [k_2, k_1]^T矩阵的 n-2 次幂乘以初始向量就能得到 k_n。矩阵快速幂的时间复杂度同样是 O(log n)而且代码模式固定在很多竞赛代码库里可以直接套模板。三种方法里我自己最推荐通项公式代码最短逻辑最清晰而且不容易把矩阵构造错。6. 容易翻车的边界条件m1、m2、n2 这些坑6.1 一张表看穿特殊参数行为环形染色问题的坑集中在几个小参数上。下面这张表总结了不同参数下的行为参数情况结果说明m1n≥20只有一种颜色必然出现相邻同色无解m1n11 或 0取决于单点环约定题目里必须讲清楚m2n为奇数0两色交替在奇数环上无法闭合m2n为偶数2只有正反两种交替染色n2m(m-1)两个点互为邻居必须异色n3m(m-1)(m-2)三点两两相邻等价于三色全排列看到 m2 这一行很有意思。用通项公式K(n, 2) 1^n (-1)^n × 1。n 是偶数时为 2n 是奇数时为 0。这个结果对应一个很朴素的直觉你把两种颜色轮流往环上放偶数环刚好能绕一圈回来不冲突奇数环绕回来的时候必然撞车。6.2 一个真实的踩坑记录我最初写通项公式代码时犯过一个很低级的错误直接套pow(m - 1, n, MOD)忘了考虑m - 1为 0 的情况。当 m1 时0^n在 Python 里对 n0 结果是 0这没问题但如果 n0有些题会问空环就变成0^0 1直接把答案带偏。后来形成习惯所有快速幂之前先特判 m1 和 n1把边界情况提前拦下来。这两个参数虽然看着幼稚但几乎所有题目踩坑都从这里开始。另一个容易被忽略的是通项公式在 m0 时的不合理性。颜色数为 0 的环染色问题本身没有定义因为连一个可用的颜色都没有但公式硬套可能出现负数次幂。所以颜色数至少从 1 开始。6.3 环形问题在更大染色版图里的位置理解环形染色后可以顺手把视野拉宽一点。直线染色是 m(m-1)^(n-1)树染色也是这个表达式——树的每个节点往下扩展时只需要避开父节点的颜色。环染色因为多了一条收尾相接的边复杂度提升了一档但还是有闭式解。一旦走到完全图或者一般图染色问题就变成 NP 困难没有这种漂亮公式了。环形结构之所以特殊是因为它是 2-正则图每个点的度数都是 2结构足够简单。同样是一维结构链和环的计算难度差别很大这个对比对理解图的结构如何决定图染色问题的复杂度很有帮助。7. 现实应用化学同分异构体、圆桌排座与一般图上染色7.1 化学环状分子取代基计数化学里经常要数环状分子的同分异构体比如苯环上有若干个取代基时有多少种不同的结构。苯环是六元环六个位置等效取代基的种类和位置决定异构体数量。这时候数本质不同的染色方案对称群不光是旋转还包括镜面翻转所以组合对象是二面体群 D6而不是旋转群 C6。举例来说苯环上一取代只有 1 种二取代有邻、间、对 3 种。这两个结论用 Burnside 引理都能系统算出来。如果不小心只用了旋转群二取代会被数成 2 种漏掉了镜面对称造成的等价。这个例子非常能说明对称群的选择直接影响分母的大小。7.2 圆桌排座与环形排班会议排座也是个典型场景n 个单位代表围圆桌坐相邻座位不能安排同一个单位的人。如果每个单位只有一个人出席这直接就是环形染色如果考虑座位旋转等价就用 Burnside如果还考虑左右手方向有些场合镜像视为不同因为左右邻不同那又是另一套对称性。环形排班同理比如周期性的值班表相邻班次不能由同一组人负责本质上也在做环染色。多试几个 m、n 的组合就会发现公式给出来的数值增长率非常快手工枚举基本不可能必须靠递推或通项。7.3 从环到一般图染色问题的世界观环形染色是图染色的一个优美特例。从环出发往两个方向延伸一个是把环拉直变成链得到 m(m-1)^(n-1)一个是把环加边变成完全图染色条件迅速收紧比如 K_n 上相邻不同色等于要求所有点两两不同色方案数直接退化成排列数 m!/(m-n)!。图结构每加一条边自由度就少一块计数难度也可能从多项式跳到指数。所以如果你是一个竞赛选手或者数学爱好者遇到环形染色不要只背公式把它当做一个理解图结构如何影响计数复杂度的标本收获会大很多。等哪天遇到环上加弦、多环并在一起的问题你会感谢当初对这个简单模型的一次次拆解。最后分享一点个人经验面对这类组合计数问题最实用的思路永远是先找破口。剪开一条边把环变成链把首尾关系做成状态塞进递推如果需要去重再把对称群搬出来。这套组合技在环形染色上用一遍在别的环形结构问题上还能再用十遍。
阅读完成 · 觉得有帮助？
