一个有趣的计数分界点：为什么 n≤4 时答案如此简洁？

写在前面：本文由我提供完整思路，豆包完善具体过程而成。

今天在阿叶数学公众号上看到一道高考计数题：

用数字1,2,3,4组成的4位数中，满足数字𝑖出现次数不超过𝑖次的总个数为______．

本题难度不大，用指数型生成函数可以很快解决，答案为

的展开式中𝑥^(4)项的系数．

一般地，在用数字1,2,⋯,𝑛组成的𝑛位数中，设满足数字𝑖出现次数不超过𝑖次的总个数为𝑓(𝑛)．

一个非常有趣的现象是：

• 当𝑛≤4时，𝑓(𝑛)=𝑛^(𝑛)−(𝑛−1)^(𝑛)，例如𝑛=4时，𝑓(4)=4^(4)−3^(4)=175，与实际计数完全一致
• 当𝑛>4时，该等式不再成立

本文将完整解释这一现象的成因，重点给出核心恒等式的双射证明（揭示其组合本质）．

一、补集转化与容斥原理框架

总共有𝑛^(𝑛)个可能的𝑛位数．我们定义补集事件：

则不符合条件的数的集合为𝐴_(1)∪𝐴_(2)∪⋯∪𝐴_(𝑛)，因此：

根据容斥原理，补集的大小为：

二、关键观察：𝑛≤4时不存在多重违反限制的情况

对于任意两个不同的数字𝑖,𝑗，𝐴_(𝑖)∩𝐴_(𝑗)非空的充要条件是：存在一个𝑛位数，其中𝑖出现至少𝑖+1次，𝑗出现至少𝑗+1次．此时总位数至少为：

当𝑛≤4时，最小的两个数字是1和2，它们的最小违反次数和为：

这意味着任意两个𝐴_(𝑖),𝐴_(𝑗)的交集都是空集．更高阶的交集（三个及以上集合）的次数和会更大，自然也为空． 因此，容斥原理在𝑛≤4时可以极大简化：

（注：𝐴_(𝑛)恒为空集，因为𝑛位数中𝑛最多出现𝑛次，不可能超过𝑛次）

这也说明，在𝑛>4时，𝑓(𝑛)不再有上述简单的表达式．

三、核心恒等式的双射证明（本文重点）

现在我们需要证明：对任意正整数𝑛，

这个恒等式是𝑛≤4时公式成立的关键．我们先给出简洁的代数证明作为对比，再重点介绍能揭示组合本质的双射证明．

铺垫：简洁代数证明

1. 单个集合的大小为：|𝐴_(𝑖)|=∑_(𝑛)^(𝑘=𝑖+1)((𝑛)/(𝑘))(𝑛−1)^(𝑛−𝑘)
2. 交换求和顺序：∑_(𝑛−1)^(𝑖=1)|𝐴_(𝑖)|=∑_(𝑛)^(𝑘=2)(𝑘−1)((𝑛)/(𝑘))(𝑛−1)^(𝑛−𝑘)
3. 利用组合恒等式(𝑘−1)((𝑛)/(𝑘))=𝑛((𝑛−1)/(𝑘−1))−((𝑛)/(𝑘))，代入二项式定理：

核心：双射证明

恒等式左边∑|𝐴_(𝑖)|不是“违反限制的数的个数”，而是所有数的“违反限制总次数”：每个数违反𝑘个限制，就被计数𝑘次．

因此，我们需要构造一个双射，将所有“带违反标记的𝑛位数”一一对应到所有不含数字𝑛的𝑛位数（共(𝑛−1)^(𝑛)个）．

定义：带违反标记的𝑛位数是一个有序对(𝑆,𝑖)，其中，𝑆是用1,2,…,𝑛组成的𝑛位数；𝑖是𝑆违反的一个限制，即数字𝑖在𝑆中出现至少𝑖+1次．

我们的目标：建立集合

与集合𝑌={1,…,𝑛−1}^(𝑛)之间的双射．

关键转化：标记“第𝑖+1次出现”的位置

对于任意带违反标记的数(𝑆,𝑖)，由于数字𝑖出现至少𝑖+1次，我们可以唯一确定一个特殊位置𝑝：

核心定义：𝑝是𝑆中第𝑖+1次出现数字𝑖的位置．

这个位置𝑝有两个关键性质：

1. 前𝑝个位置中恰好有𝑖+1个𝑖
2. 前𝑝−1个位置中恰好有𝑖个𝑖

因此，每个带违反标记的数(𝑆,𝑖)都唯一对应一个带位置标记的数(𝑆,𝑝)，反之亦然．集合𝑋与集合

是一一对应的．

双射的具体构造

给定带位置标记的数(𝑆,𝑝)∈𝑍，令𝑐=𝑆[𝑝]（即违反限制的数字），按以下规则构造𝑇∈𝑌：

规则说明：

• 核心标记位𝑇[𝑝]=𝑐：用于唯一记录违反限制的数字𝑐
• 关键区分规则：𝑝之后的所有𝑐全部映射为𝑐+1，确保𝑇中前𝑝位恰好有𝑐+1个𝑐，𝑝之后没有𝑐
• 大于𝑐的数字减1：确保𝑇中没有数字𝑛（原数字𝑛会被减为𝑛−1）

双射的严格验证

1. 合法性： 𝑇中所有数字都在1到𝑛−1之间．特别地，当𝑐=𝑛−1时，𝑖=𝑛−1，此时𝑖+1=𝑛，即𝑝=𝑛，没有𝑝+1到𝑛的位置，不会出现𝑇[𝑘]=𝑛的情况．
2. 单射性： 不同的(𝑆,𝑝)会映射到不同的𝑇．若𝑝_(1)≠𝑝_(2)，则𝑇中第𝑐_(1)+1个𝑐_(1)的位置与第𝑐_(2)+1个𝑐_(2)的位置矛盾；若𝑝_(1)=𝑝_(2)，则可唯一还原𝑆．
3. 满射性： 任意𝑇∈𝑌都有唯一原像．对每个𝑐找第𝑐+1个𝑐的位置，恰好存在一个这样的𝑐，按规则逆推即可得到唯一的(𝑆,𝑝)．

具体例子演示（𝑛=4）

• 正向映射： 𝑆=1123（违反𝑖=1），第2次出现1的位置𝑝=2，𝑐=1，构造得𝑇=(1,1,1,2)
• 逆向映射： 𝑇=(1,2,1,3)，唯一的𝑐=1（第2个1在位置3），逆推得𝑆=(1,3,1,4)

结合前面的结论，当𝑛≤4时：

四、总结

1. 在𝑛≤4时公式成立的原因：任意两个数字无法同时违反限制，补集是不交并，且核心恒等式∑|𝐴_(𝑖)|=(𝑛−1)^(𝑛)成立．
2. 核心恒等式的本质：通过双射证明，我们揭示了其组合意义 —— 所有𝑛位数的违反限制总次数，恰好等于不含数字𝑛的𝑛位数的总个数．