2008-重庆卷理-16 填-排列组合

本题导读

本题是一道结合空间几何体（三棱柱）顶点的图论染色计数题，属于排列组合板块的压轴题。解题核心在于处理好“相邻顶点不同色”与“4种颜色至少各用一次”的双重约束。

📌【题干】

Question

（2008年重庆卷(理)） 某人有 4 种颜色的灯泡（每种颜色的灯泡足够多），要在如图所示的 6 个点 $A、B、C、A_1、B_1、C_1$ 上各装一个灯泡，要求同一条线段两端的灯泡不同色，则每种颜色的灯泡都至少用一个的安装方法共有 $\underline{}$种.（用数字作答）

🔍【思路分析】

破题导航

1. 识别图形几何结构：该图本质上是一个三棱柱。顶部 $ABC$ 构成一个三角形（三阶完全图 $K_3$），底部 $A_1{B}_1{C}_1$ 亦然，上下对应点有连线。
2. 优先对上底面 $ABC$ 的 3 个顶点进行染色。由于它们两两相连，必须使用 3 种不同的颜色。
3. 在上底面颜色确定的情况下，对下底面 $A_1{B}_1{C}_1$ 进行染色。利用容斥原理或分类讨论法计算满足“对应点不同色”且“下底面必须引入第 4 种颜色”的方案数。

✅【答案】

点击查看答案

$216$

✍【详细解析】

Abstract

第一步：先对上底面三角形 $ABC$ 的 3 个顶点染色。 从 4 种颜色中任选 3 种涂在 $A,B,C$ 上，方法数为： $A_4^3=4\times 3\times 2=24\text{ 种}$ 不妨设 $A,B,C$ 染上的颜色分别为 1, 2, 3。此时第 4 种颜色暂未使用。

第二步：对下底面 $A_1,B_1,C_1$ 进行染色。 根据题意，下底面 3 个顶点也两两相连，故必须异色。且满足临界限制：$A_1\ne 1,B_1\ne 2,C_1\ne 3$。 为确保“4种颜色都至少用一个”，下底面 $\{A_1,B_1,C_1\}$ 这一组颜色中必须包含颜色 4。 我们可以用**间接法（总数减去不合题意数）**来计算下底面的合法染色方案：

1. 不考虑是否包含颜色 4，仅满足相邻及对应限制的总方案数： 下底面 3 个不同的颜色相当于从 $\{1,2,3,4\}$ 中任选 3 个进行排列，总排列数为 $A_4^3=24$ 种。 需要排除不满足 $A_1\ne 1,B_1\ne 2,C_1\ne 3$ 的情况，由包含排斥原理：

• $A_1=1$ 的情况：$B_1,C_1$ 从剩余 3 种颜色中任选 2 种排列，有 $A_3^2=6$ 种；同理 $B_1=2$ 有 6 种，$C_1=3$ 有 6 种。
• $A_1=1$ 且 $B_1=2$ 的情况：$C_1$ 可选其余 2 种颜色，有 2 种；同理两两重叠各 2 种。
• $A_1=1,B_1=2,C_1=3$ 的情况：只有 1 种。 满足对应点不同色的下底面总染色数为：$24-(6\times 3)+(2\times 3)-1=11$ 种。

2. 在这 11 种方案中，找出未包含颜色 4 的方案： 若不包含颜色 4，则下底面只能由 $\{1,2,3\}$ 组成。满足 $A_1\ne 1,B_1\ne 2,C_1\ne 3$ 的排列即为 $\{1,2,3\}$ 的全错位排列，方案数为 $D_3=2$ 种（即 $(2,3,1)$ 和 $(3,1,2)$）。
3. 因此，下底面包含颜色 4 的合法方案数为：$11-2=9$ 种。

第三步：综合两步，根据分步计数原理，总安装方法数为： $\text{总数}=24\times 9=216\text{ 种}$ 故答案为 216。

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

Danger

1. 核心考点：完全图染色模型的计数，有限制条件的排列组合，包含排斥原理。
2. 核心方法：先局部再整体（分步法），正面分类不易时采用全集减去补集的间接法。
3. 避坑指南：本题极易漏掉“每种颜色至少用一个”的限制，直接算出来 $24\times 11=264$ 而掉入陷阱。必须将没有用到第 4 种颜色的错位情况扣除。

📖【试题探源与推广】

Tip

1. 试题探源：本题是经典的图论色多项式（Chromatic Polynomial）计数问题在立体几何框架下的投影映射。
2. 结论推广：对于侧棱数为 $n$ 的正 $n$ 棱柱顶点的 $k$ 着色问题，可借助递推数列或容斥原理给出一般化的染色通项公式。

🔗【关联脉络】

Multi column

知识锚点 (Nodes)

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

类题演练 (Links)

• 2009-北京卷理-07 单-排列组合
• 2009-四川卷理-11 单-排列组合
• 2009-大纲卷II理-10 单-排列组合