5层高彩立方塔搭建方式计数问题（容斥原理求解尝试）

嗨，我来帮你梳理清楚这个问题的解法——你想用容斥原理的思路完全没问题，咱们一步步拆解：

首先明确问题：我们有5层立方体，每层可选红、黄、蓝、绿4种颜色，要求每一对相邻立方体中至少有一个是蓝或绿色（换句话说，不能出现相邻两个都是红/黄的情况）。

容斥原理的核心思路 #

我们先定义事件：

• $A_i$：第$i$个和第$i+1$个立方体组成的相邻对中，没有蓝色或绿色（也就是这两个都是红/黄），其中$1\le i\le4$（因为5层有4个相邻对）。

我们要求的是所有$A_i$都不发生的情况数，也就是$|\bigcap_{i=1}^4 \overline{A_i}|$。根据容斥原理，公式是：
$$
|\bigcap_{i=1}^4 \overline{A_i}| = \text{总情况数} - \sum|A_i| + \sum|A_i\cap A_j| - \sum|A_i\cap A_j\cap A_k| + |A_1\cap A_2\cap A_3\cap A_4|
$$

接下来我们逐个计算每一项：

1. 总情况数

每层4种选择，5层的总方式数是：
$$4^5 = 1024$$

2. $\sum|A_i|$：单个$A_i$的情况数之和

每个$A_i$只限制第$i$和$i+1$层为红/黄（各2种选择），剩下3层可以任意选4种颜色。所以单个$|A_i|=2\times2\times4\times4\times4=256$。

一共有4个这样的$A_i$，所以：
$$\sum|A_i|=4\times256=1024$$

3. $\sum|A_i\cap A_j|$：两个$A_i$同时发生的情况数之和

这里要分两种子情况：

• 相邻的$A_i$和$A_j$（比如$A_1$和$A_2$）：这会限制第$i, i+1, i+2$层都是红/黄（因为$A_i$限制$i$和$i+1$，$A_j$限制$i+1$和$i+2$），剩下2层任意选。每个这样的交集情况数是$2^3\times42=8\times16=128$，共有3组（$(A_1,A_2),(A_2,A_3),(A_3,A_4)$）。
• 不相邻的$A_i$和$A_j$（比如$A_1$和$A_3$）：两个限制不重叠，分别限制两对相邻层为红/黄，剩下1层任意选。每个这样的交集情况数是$2^2\times22\times4=4\times4\times4=64$，共有3组（$(A_1,A_3),(A_1,A_4),(A_2,A_4)$）。

加起来总和是：
$$\sum|A_i\cap A_j|=3\times128 + 3\times64=384+192=576$$

4. $\sum|A_i\cap A_j\cap A_k|$：三个$A_i$同时发生的情况数之和

总共有$\binom{4}{3}=4$组组合，分两种子情况：

• 三个连续的$A_i$（比如$A_1,A_2,A_3$）：限制第1-4层都是红/黄，第5层任意选，情况数是$2^4\times4=16\times4=64$，这样的组合有2组（$(A_1,A_2,A_3),(A_2,A_3,A_4)$）。
• 非连续的三个$A_i$（比如$A_1,A_2,A_4$）：会限制所有5层都是红/黄（前三个限制1-3层，$A_4$限制4-5层，覆盖全部），情况数是$2^5=32$，这样的组合有2组（$(A_1,A_2,A_4),(A_1,A_3,A_4)$）。

总和是：
$$\sum|A_i\cap A_j\cap A_k|=2\times64 + 2\times32=128+64=192$$

5. $|A_1\cap A_2\cap A_3\cap A_4|$：四个$A_i$同时发生的情况数

这意味着所有相邻对都是红/黄，也就是5层全部是红/黄，情况数是：
$$2^5=32$$

代入容斥公式计算最终结果 #

把所有项代入公式：
$$
|\bigcap_{i=1}^4 \overline{A_i}| = 1024 - 1024 + 576 - 192 + 32 = 416
$$

用递推法验证结果 #

为了确保正确，我们用递推思路再算一遍：

• 设$a_n$为$n$层塔满足条件的方式数，$b_n$为$n$层塔最后一层是红/黄的方式数，$c_n$为最后一层是蓝/绿的方式数，显然$a_n=b_n+c_n$。
• 递推关系：
  • $b_n=2\times c_{n-1}$（最后一层选红/黄时，前一层必须是蓝/绿，否则违反条件，前一层有$c_{n-1}$种，当前层2种选择）
  • $c_n=2\times a_{n-1}$（最后一层选蓝/绿时，前一层可以任意，前一层有$a_{n-1}$种，当前层2种选择）
• 初始条件：$a_1=4$，$b_1=2$，$c_1=2$
• 计算到$n=5$：
  • $a_2=4+8=12$，$a_3=16+24=40$，$a_4=48+80=128$，$a_5=160+256=416$

和容斥结果一致，说明答案正确。

内容的提问来源于stack exchange，提问作者Noy