一月6场间隔至少2天的考试排布方式计数问题求解题提示

嘿，这个问题用**转化法（变量替换+组合数）**会比容斥简单太多，容斥在这里确实容易踩重复计数的坑，我来给你拆解下思路：

第一步：明确核心条件 #

首先把题目要求转化为数学条件：设6场考试的日期为 (d_1 < d_2 < \dots < d_6)（均为1-31的整数），题目要求任意两场考试之间至少隔2天空闲，也就是下一场考试最早在上一场的3天后，即：
[d_{i+1} - d_i \geq 3 \quad (i=1,2,\dots,5)]

第二步：变量替换消除间隔限制 #

我们可以通过调整日期变量，把带间隔限制的选数问题转化为普通的组合选数问题：

• 令 (d_1' = d_1)
• (d_2' = d_2 - 2)（减去第一场和第二场之间必须的2天空闲）
• (d_3' = d_3 - 4)（减去前两个间隔各2天）
• ...
• (d_6' = d_6 - 2 \times 5 = d_6 - 10)

此时你会发现，原来的间隔条件 (d_{i+1} \geq d_i + 3) 等价于：
[d_{i+1}' = d_{i+1} - 2i \geq (d_i + 3) - 2i = (d_i - 2(i-1)) + 1 = d_i' + 1]
也就是 (d_1' < d_2' < \dots < d_6')——完全没有间隔限制了！

第三步：确定调整后日期的范围 #

• 最小的 (d_1' \geq 1)
• 最大的 (d_6' = d_6 - 10 \leq 31 - 10 = 21)

现在问题就简化成：从1到21这21个数字中任选6个不同的数，有多少种选法？

第四步：计算结果 #

这是标准的组合数问题，答案就是组合数 (C(21,6))，计算得：
[C(21,6) = \frac{21 \times 20 \times 19 \times 18 \times 17 \times 16}{6 \times 5 \times 4 \times 3 \times 2 \times 1} = 54264]

为什么不推荐用容斥？ #

容斥在这里的复杂度很高：你需要先算所有无限制的6场考试排列，再减去至少有一组间隔不足的情况，加上至少有两组间隔不足的情况……但“间隔不足”包含间隔1天或0天两种情况，且多组间隔不足的重叠情况非常容易重复计数，远不如转化法直接高效。

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