2003-广东卷-16 填-计数原理

本题导读

本题主要考查分步乘法计数原理及排列组合在图论着色问题中的经典应用。解题的关键在于识别出外部环形区域在首尾相接时的颜色重合风险，通过对相对且不相邻的区域（如区域 2 与区域 4）颜色是否相同进行分类讨论，从而准确规避计数冲突。

📌【题干】

Question

（2003年广东卷） 如图，一个地区分为 5 个行政区域，现给地图着色，要求相邻地区不得使用同一颜色，现有 4 种颜色可供选择，则不同的着色方法共有$\underline{}$种.（以数字作答）

🔍【思路分析】

破题导航

1. 确定核心区域首发：区域 1 与其余 4 个区域均相邻，约束条件最强，应优先对其进行着色。
2. 制定外围环绕顺序：外围区域 2, 3, 4, 5 组成一个首尾相连的环。可按照 2 $\to$ 3 $\to$ 4 $\to$ 5 的顺时针方向依次分步讨论。
3. 识别环形冲突并分类：

   • 区域 2 有若干种选择。

   • 区域 3 与 1, 2 相邻。

   • 区域 4 与 1, 3 相邻。此时区域 4 的颜色选择会直接受到它与区域 2 的颜色是否相同的影响：若 4 与 2 同色，则留给收尾区域 5 的可选颜色就多；若 4 与 2 异色，则留给 5 的可选颜色就少。

   • 因此，核心突破点在于对区域 2 与区域 4 是否同色进行分类讨论。

✅【答案】

Success

$72$

✍【详细解析】

Abstract

根据相邻区域不同色的要求，按照区域 1 $\to$ 2 $\to$ 3 $\to$ 4 $\to$ 5 的顺序分步着色，并对区域 2 与 4 的颜色关系分类讨论：

先对区域 1 着色：从 4 种颜色中任选 1 种，共有 $C_4^1=4$ 种方法。 再对区域 2 着色：不能与 1 同色，从剩下的 3 种颜色中任选 1 种，共有 $C_3^1=3$ 种方法。 再对区域 3 着色：不能与 1, 2 同色，从剩下的 2 种颜色中任选 1 种，共有 $C_2^1=2$ 种方法。

接下来对区域 4 和 5 展开分类讨论：

情况 1：区域 4 与区域 2 选用同一种颜色

• 区域 4：因为 4 与 2 同色，所以 4 的颜色已经由 2 唯一确定，只有 1 种方法。同时，该颜色由于属于 2，自然不与 1 和 3 冲突（区域 2 与 3 已异色）。
• 区域 5：此时 5 与 1, 2, 4 相邻。由于 2 与 4 同色，实际上 5 只是与 2 种不同的颜色（区域 1 的颜色、区域 2/4 的共用色）相邻。因此，5 可从 4 种颜色中排除这 2 种，剩下 $4-2=2$ 种方法。
• 此情况下的着色方法数： $N_1=4\times 3\times 2\times 1\times 2=48\text{ 种}$

情况 2：区域 4 与区域 2 选用不同的颜色

• 区域 4：不能与 1, 3 同色（剩下 2 种可选），且不能与 2 同色，因此只有 $2-1=1$ 种方法。
• 区域 5：此时 5 与 1, 2, 4 相邻。因为 2 与 4 异色，且它们都与 1 异色，所以 1, 2, 4 占用了 3 种不同的颜色。因此，5 只能从 4 种颜色中排除这 3 种，剩下 $4-3=1$ 种方法。
• 此情况下的着色方法数： $N_2=4\times 3\times 2\times 1\times 1=24\text{ 种}$

综合汇总： 根据加法原理，总的着色方法数为两类情况之和： $N=N_1+N_2=48+24=72\text{ 种}$

答案：72

💡【考点归纳与避坑指南】

Danger

1. 核心考点：分步乘法原理与分类加法原理的嵌套结合，环状图着色模型。
2. 核心方法：相对区域关联法。在环形染色中，遇到最后两块区域时，必须向前追溯并按“与不相邻的特定片区同色、异色”划分两条逻辑线。
3. 避坑指南：

   • 极易直接盲目分步计数：$4(\text{区}1)\times 3(\text{区}2)\times 2(\text{区}3)\times 2(\text{区}4)\times 1(\text{区}5)=48$，从而漏掉分类，造成少算。

   • 必须注意图中的空间邻接关系，不要把不相邻的区域误认为相邻。

📖【试题探源与推广】

Tip

1. 试题探源: 本题属于概率与微积分前置内容中“计数原理”的王牌题型，源于图论（Graph Theory）中的“地图着色多项式（Chromatic polynomial）”问题。
2. 结论推广: 对于一个中心为 1、外围有 $n$ 个扇区首尾相连成环的辐射状地图，若提供 $m$ 种颜色，其着色多项式公式为：$P(G,m)=m\cdot [(m-1{)}^n+(-1{)}^n\cdot (m-1)]$。本题中中心加外围 4 个区（$n=4$），颜色数 $m=4$，代入公式可直接验算： $P=4\times [(4-1{)}^4+(-1{)}^4\cdot (4-1)]=4\times [3^4+3]=4\times [81+3]=4\times 84=336\text{ （注：此公式为全图无中心时的环独立染色推广公式）}$ 若中心占用 1 种，外环相当于用 $m-1$ 种色进行 $n$ 阶环染色。代入公式 $P_{\text{外}}=(m-1{)}^n+(-1{)}^n(m-1)$，本题 $m-1=3,n=4$： $P_{\text{外}}=3^4+(-1{)}^4\times 3=81+3=84$ 由于中心有 $m=4$ 种选法，最终总数 = $4\times 84=336\dots$ 等等。 重新校对邻接图矩阵：本题外围 4 个区域并非完全对称的封闭大圆环，区域 2 和 5、3 和 4 的边界分档。2与5相邻、2与3相邻、3与4相邻、4与5相邻。的确构成了一个 4 阶环。 利用 4 阶环公式，当有 3 种颜色可用时，染色种数为 $(3-1{)}^4+(-1{)}^4\times (3-1)=2^4+2=18$。 则总数 = $4\times 18=72$。公式法与代数分类法结果完全交圈。

🔗【关联脉络】

Multi column

知识锚点 (Nodes)

• 22.01 计数原理、排列与组合

类题演练 (Links)

• 1981-全国文-03 解-排列与组合的计数
• 1985-全国文-05 单-排列计数（五位数）
• 1985-广东文-20 单-受限排列计数