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

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

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

用数字组成的位数中，满足数字出现次数不超过次的总个数为______．

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

的展开式中项的系数．

一般地，在用数字组成的位数中，设满足数字出现次数不超过次的总个数为．

一个非常有趣的现象是：

• 当时，，例如时，，与实际计数完全一致
• 当时，该等式不再成立

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

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

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

则不符合条件的数的集合为，因此：

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

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

对于任意两个不同的数字，非空的充要条件是：存在一个位数，其中出现至少次，出现至少次．此时总位数至少为：

当时，最小的两个数字是和，它们的最小违反次数和为：

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

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

这也说明，在时，不再有上述简单的表达式．

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

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

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

铺垫：简洁代数证明

1. 单个集合的大小为：
2. 交换求和顺序：
3. 利用组合恒等式，代入二项式定理：

核心：双射证明

恒等式左边不是“违反限制的数的个数”，而是所有数的“违反限制总次数”：每个数违反个限制，就被计数次．

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

定义：带违反标记的位数是一个有序对，其中，是用组成的位数；是违反的一个限制，即数字在中出现至少次．

我们的目标：建立集合

与集合之间的双射．

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

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

核心定义：是中第次出现数字的位置．

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

1. 前个位置中恰好有个
2. 前个位置中恰好有个

因此，每个带违反标记的数都唯一对应一个带位置标记的数，反之亦然．集合与集合

是一一对应的．

双射的具体构造

给定带位置标记的数，令（即违反限制的数字），按以下规则构造：

规则说明：

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

双射的严格验证

1. 合法性： 中所有数字都在到之间．特别地，当时，，此时，即，没有到的位置，不会出现的情况．
2. 单射性： 不同的会映射到不同的．若，则中第个的位置与第个的位置矛盾；若，则可唯一还原．
3. 满射性： 任意都有唯一原像．对每个找第个的位置，恰好存在一个这样的，按规则逆推即可得到唯一的．

具体例子演示（）

• 正向映射： （违反），第2次出现1的位置，，构造得
• 逆向映射： ，唯一的（第2个1在位置3），逆推得

结合前面的结论，当时：

四、总结

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