6.1 计数原则：加法、乘法、容斥与抽屉原理
“系统一共有多少种配置”听起来只是算数字，真正困难的往往是先确定什么算一个状态、不同步骤是否独立、两类方案是否重叠。模型错了，公式算得再快也没有意义。
计数先定义对象
权限系统有：
- 5 个角色；
- 20 个资源；
- 3 种操作：读、写、执行。
若每个角色、资源和操作的组合都独立选择允许或拒绝，共有：
5×20×3=300 个布尔决策
状态数=2³⁰⁰若产品规定每个角色与资源的配对只能从“只读、读写、无权限”三种套餐中选一种，才是：
3^(5×20)=3¹⁰⁰两个数字都可能正确，取决于状态模型。计数题第一步永远是写清对象与约束。
加法原理：互斥方案相加
若一个任务可以通过互不重叠的方案集合 A₁,...,A_k 完成：
|A₁∪...∪A_k|=|A₁|+...+|A_k|例如一个请求只能从三种互斥来源进入：
Web 入口 120 种测试样例
CLI 入口 40 种
定时任务 15 种
总计 120+40+15=175 种“互斥”不能省略。若同一个样例可同时属于 Web 和定时任务标签，直接相加会重复计数。
乘法原理：连续选择相乘
若构造一个对象分为 k 个阶段，并且对每个已形成的前缀，第 i 阶段都有 n_i 种选择，则：
n₁n₂...n_k三个独立部署维度：
4 个区域 × 3 种实例规格 × 2 种存储后端 = 24 种如果某区域不支持某存储，阶段选择数依赖前面的结果，不能直接 4×3×2。可以分类相加，或统计允许的配对关系。
乘法原理不要求概率独立；它是构造对象的计数规则。关键条件是每个分支的后续选择数是否按模型给定。
补集计数：先数全部，再减坏情况
长度为 8 的十进制字符串，允许前导零，共 10⁸ 个。至少含一个数字 7 的字符串：
全部 - 完全不含 7
=10⁸-9⁸“至少一个”常适合补集法。直接按“第一个 7 出现在哪个位置”分类也能计数，但更容易漏掉或重复。
容斥原理修正重叠
两个有限集合：
|A∪B|=|A|+|B|-|A∩B|三集合：
|A∪B∪C|
=|A|+|B|+|C|
-|A∩B|-|A∩C|-|B∩C|
+|A∩B∩C|先加单集合时，落在两个集合中的对象被数两次；减去两两交集后，三重交集被减得过多，所以再加回来。
例：1 到 100 中能被 2 或 5 整除的整数：
⌊100/2⌋ + ⌊100/5⌋ - ⌊100/10⌋
=50+20-10
=60容斥的困难随集合数增长很快。若约束结构特殊，动态规划、生成函数或求解器可能更适合。
除法原理：每个对象被等量重复计算
若一个计数过程把每个目标对象恰好数 k 次，其中 k 为正整数，则：
目标数量=过程计数/k从 n 人中选无序两人组。先选第一人再选第二人有 n(n-1) 种，但每组 {a,b} 被 (a,b)、(b,a) 各数一次：
n(n-1)/2只有“每个目标对象恰好重复 k 次”时才能除。重复次数不均匀，简单相除会错。
双重计数：从两个方向数同一集合
一场会议中，统计所有握手事件。若第 i 人握手次数为 d_i：
Σ d_i = 2|E|左边按参与者统计，每次握手在两端各出现一次；右边按握手事件统计，每次贡献 2。这就是握手定理，也会在图论章出现。
双重计数常用于证明恒等式。选择一个对象集合，用两种分类方式计数，结果必然相等。
抽屉原理：容量不足必然碰撞
若把 N≥0 个对象放入 k≥1 个盒子，至少有一个盒子包含：
⌈N/k⌉个对象。
例：哈希函数把超过 2⁶⁴ 个不同输入映射到 64 位输出，必然有碰撞。抽屉原理只证明碰撞存在，不说明容易找到，也不说明哈希函数不安全；安全性还涉及碰撞搜索成本和攻击模型。
“366 人中必有至少两人生日相同”需要只允许 365 个日期的模型。若包括 2 月 29 日，367 人才保证有一对生日相同。这里比较月日，不比较出生年份；概率很高与必然发生也是两个结论。
软件状态空间不能只乘参数个数
三项参数：
browser ∈ {Chrome, Firefox, Safari}
auth ∈ {password, passkey}
region ∈ {CN, EU, US}无约束笛卡尔积有：
3×2×3=18设本例产品部署策略排除 Safari/passkey/CN 这一组合，其他组合全部允许，则合法状态为 18−1=17。这是示例产品规则；Python 3 标准库枚举可以直接核对它：
from itertools import product
states = list(product(("Chrome", "Firefox", "Safari"),
("password", "passkey"), ("CN", "EU", "US")))
def allowed(state):
return state != ("Safari", "passkey", "CN")
valid = [state for state in states if allowed(state)]
print(len(states), len(valid)) # 18 17
print(sum(i % 2 == 0 or i % 5 == 0 for i in range(1, 101))) # 60测试设计还要区分：
- 配置是否可达；
- 不同配置是否行为等价；
- 状态转换路径是否也属于覆盖目标；
- 并发调度是否引入新的顺序空间。
计数给出规模，不自动给出合理测试集。
完成检查
- 计算长度为 6、至少含一个大写字母的字母数字字符串数量，并写清字符集；
- 用容斥计算 1 到 500 中能被 3 或 7 整除的数；
- 证明任意 13 个整数中至少两个模 12 同余；
- 为一个三维配置矩阵写出全部约束，再计算可达状态；
- 找一个直接乘法会错的依赖选择例子。