先修：02 命题、集合与条件；04 归纳证明
一个配置页有十个功能开关：缓存、压缩、预取，以及另外七项。每项只有“开”和“关”。如果把十项各自的两个取值加起来，得到20；但如果问整个配置页能保存多少种不同配置，答案却是1024。
两个数都能数出东西，只是数的对象不同。20数的是“某个开关取某个值”这样的局部选项；1024数的是十个开关同时确定以后，整张配置表的状态。
第一部关心如何把规则说清楚、把步骤证明清楚。从这一章开始，我们追问数量与代价：到底有多少种情况？增加一个选项，会给系统增加多少需要考虑的可能性？先算清对象，再决定怎样处理它们。
先给一种配置一个唯一名字
固定十个开关的编号，用0表示关、1表示开。例如：
1001000000
表示第1、4项开启，其余关闭。我们只记录某一时刻的最终配置，不记录先点了哪个开关，也不记录同一个开关来回切换过几次。
暂时作三个约定：十个位置各有身份；每个位置恰好有两个值；所有0/1组合都允许保存。这个模型没有“自动”“继承默认值”等第三种状态，也没有功能间的兼容限制。
把所有配置组成的集合记作S₁₀，把所有长度为10的0/1串组成的集合记作{0,1}¹⁰。上面的编码建立了一一对应：每个配置产生一个串，每个串都能还原成一个配置。两个配置只要有一项不同，编码在那个位置就不同，因而不会合并计数；每个十位串也都能还原，因而没有漏项。
所以，数配置可以改成数这些串。还可以改成数“开启了哪些功能”的集合：1001000000对应{1,4}，全关对应空集。开关身份固定以后，集合的写法顺序不影响配置，{1,4}与{4,1}仍是同一个状态。
如果改成只记“开了几个”，记录值只有0到10共11个。但“只开缓存”和“只开压缩”都会变成数字1，已经无法还原。这样的简写丢掉了区别，不能用它的取值数代表配置数。一一对应的价值，就在于换了数法，却保住了原来要区分的对象。
每增加一个开关，都把旧状态复制两份
先只看三个开关。第一个确定后有0、1两种；确定第二个后有00、01、10、11四种。再给每个两位串分别接上0和1，就得到八个三位串。
图1：每一层固定一个位置，每个前缀都能接0或1。每条完整路径得到的三位串互不相同，各层前缀数依次为2、4、8。
把这条规律写成证明。设Nₙ表示n个开关的配置数。没有开关时，仍有一种“什么也不设置”的空配置，所以N₀＝1。
假设n个开关有Nₙ种配置。增加第n＋1个开关后，全部配置可以分成末位为0和末位为1两组。每组删去末位，都与原来的n位配置一一对应，因此各有Nₙ种。两组没有共同元素，并且包含全部新配置，故：
Nₙ₊₁＝Nₙ＋Nₙ＝2Nₙ。
从N₀＝1出发，每次乘2。按照第04章的归纳思路，若Nₙ＝2ⁿ，则Nₙ₊₁＝2×2ⁿ＝2ⁿ⁺¹；起点与传递步骤都有了，因此对每个非负整数n，Nₙ＝2ⁿ。这里2ⁿ表示n个2连乘，2⁰＝1。
十个开关于是有2¹⁰＝1024种配置。这个结论来自“每种旧配置都恰好扩展成两种新配置”，不是因为画出了几层树，就猜测后面也一样。
什么时候才能把选项数相乘
这个推导是乘法计数法则的一种情形。第一步有a种选择；对第一步的每一种选择，第二步都恰好有b种接法；并且这些完整选择路径与要数的对象一一对应，总数就是a×b。
理由仍然是加法：按第一步分成a组，每组b个，合起来是a个b。推广到多步，只要第i步对每一种合法前缀都有同样的aᵢ种接法，总数就是a₁×a₂×…×aₖ。MIT《Mathematics for Computer Science》14.3节的广义乘法法则明确保留了“对每一种先前选择”这个条件。
各步的数可以不同。例如配置有3种日志级别、2种缓存模式；如果每种日志级别都能配这两种缓存模式，便有3×2＝6种配置。不能仅凭界面上存在两个下拉框，就直接乘它们的选项数。
这里数的是允许出现的分支。我们没有假设用户随机选择，也没有给配置分配概率。“所有组合都允许”与“选择在概率上独立”是不同的陈述。用户实际偏爱哪些组合，不改变允许配置的总数。
加上一条依赖，整棵树就变了
现在令A表示缓存开启，B表示预取开启，并增加规则：预取必须依赖缓存，即B → A。合法的二位配置只有00、10、11；01被排除。
如果先确定A，A＝0时，B只能为0；A＝1时，B才有0、1两个选择。第二步的分支数因前一步而异，不能继续写2×2。
图2：合法的A、B前缀共有1＋2＝3种。若其余八个开关仍可自由取值，每个前缀都能接上2⁸个后缀，总数为3×2⁸＝768。
也可以先分别数两类完整配置：A＝0时，B固定为0，其余八位有256种；A＝1时，B及其余八位有512种。合起来仍是256＋512＝768。分类之后，满足条件的部分再用乘法，两种方法得到同一答案。
还有一个交叉检查：不合法的配置恰好满足A＝0、B＝1，剩余八位自由，共256种。从原来的1024种中去掉它们，得到768。这次减法成立，是因为我们准确刻画了被排除的全部配置；如果后面再加其他限制，就必须重新检查排除部分有没有重叠，不能机械地再减256。
这就是加法计数法则：有限集合U、V没有共同元素时，|U∪V|＝|U|＋|V|。竖线表示集合里的元素数。“没有共同元素”保证合并时不重复；若要数整个目标集合，分类还必须覆盖它。Oscar Levin《Discrete Mathematics: An Open Introduction》1.1节同样把互斥作为直接相加的前提。
本例按“A关”与“A开”分类，互斥且穷尽。若改成“A开”与“B开”，11会同时出现在两组，00又不在任何一组；直接相加既重复又遗漏。分类名称听起来合理，并不能代替这两项检查。
增加十项，为什么不是多算十项
在没有兼容限制的模型里，每增加一个二元开关，状态数都会翻倍。10个开关对应1024种，20个对应1,048,576种，30个对应1,073,741,824种。开关数量从10加到20只翻一倍，状态数却乘了1024。
若只给每个开关分别写一条“开”和一条“关”的局部检查，条目数是2n，增加一个开关多两条。这是线性增加。完整配置数是2ⁿ，增加一个开关多出的状态数，等于原来的全部状态数。这是指数增长。两份清单回答的问题不同，不能用局部条目数代表组合空间。
只看两个开关就能看出差别：用00、01、10三个配置做测试，每个开关都已经取过0和1；但11从未出现。如果问题只在两项同时开启时发生，这份“每项都测过”的记录发现不了它。局部取值覆盖，没有自动包含组合覆盖。
假设为了估算预算，每种配置串行运行一次固定用例，恰好耗时1秒，不计切换成本：10项约需17分钟，20项约需12.1天，30项约需34年。它不是某个真实系统的实测性能，只是在相同单次成本下，把数量换成时间。并行执行可以缩短日历时间，却没有自动消除这些待执行的用例。
当顺序也算不同，数量变成阶乘
配置只记录最终状态。但有些任务恰好关心顺序。假设三个互不相同的检查任务P、Q、R都要运行一次，任意顺序都允许。PQR与QPR是不同的执行序列。
第一位可以放三个任务中的任何一个；第二位从没用过的两个中选；第三位只剩一个。因此共有3×2×1＝6种序列。
图3：选定首位后，后续可选任务的身份会改变，但第二位的选择数始终是2，第三位始终是1，因此仍可使用逐步乘法。
对n个互异对象，每个恰好出现一次的有序排列，称为这n个对象的一个全排列。第1位有n种选择，第2位有n－1种，直到最后只剩1种，于是总数为：
n!＝n×(n－1)×…×2×1。
符号n!读作“n的阶乘”。OpenStax《Contemporary Mathematics》7.2节给出了这一记号与排列计数的关系。空列表也只有一种排列，约定0!＝1，与空配置的处理一致。
这里也没有重复计数：任一完整序列都唯一确定各位置选了什么；两条选择路径只要有一步不同，最后的序列就在那个位置不同。任务身份会影响后面能选谁，却不影响后面还剩几个，这正是乘法法则允许的情形。
十个不同任务有10!＝3,628,800种全排列。但如果只是把十个开关从全关逐个打开，这些操作顺序最终都到达同一个“全开”配置。数操作序列与数最终状态，不能混用。若任务还存在先后依赖，n!也只是没有限制时的总数。第09章讨论排序时，会再用到互异对象的这n!种相对次序。
把计数带回配置审查
面对新开关，先问它究竟有几个有效取值，再把依赖、互斥与默认值规则写清楚。原始编码数、允许保存的配置数、某个版本实际可到达的状态数，可能并不相同。让规则校验与配置生成使用同一份约束，至少能避免把禁止组合误列为正常配置。
还要约定“不同”按什么判断。若A关闭时，系统允许保存B＝1，只是在运行时忽略B，那么00与01仍是两份不同的配置记录；至于它们能否视作相同行为，需要另行说明观察范围。不能一边按保存值区分配置，一边又把某些字段当作不存在。
2ⁿ给出一种空间规模，不直接给出测试方案。系统不一定需要对所有配置运行所有测试：可以先验证约束规则，再根据功能交互、已知风险与需求选择用例，并明确留下了哪些未检查的情况。反过来，即使所有配置都跑过一个用例，也没有覆盖全部输入、操作历史和环境，不能据此宣布系统正确。
计数的作用，是让“只加一个开关”背后的范围变得可见。接下来才能具体讨论：哪些情况必须区分，哪些可以有依据地合并，哪些风险愿意暂时承担。
它还帮助我们核对简化是否真的生效：在完全自由的n开关模型中，把一个开关永久固定为0，剩下2ⁿ⁻¹种，数量恰好减半。仅把开关从界面隐藏，若旧配置和接口仍能改变它，便没有获得这个缩减。数量上的收益需要实际约束来支撑，不能只靠界面看起来更简单。
顺手试一下
题目1：两个功能依赖同一个开关
有A、B、C三个二元开关，要求B开启必须有A开启，C开启也必须有A开启，没有其他限制。合法配置有多少？再增加一个完全不受限制的二元开关D后，又有多少？
**提示：**按A的取值分成两类，检查每类里B、C还有多少种接法。
**参考答案：**A＝0时，B、C只能都为0，只有000。A＝1时，B、C自由选择，有100、101、110、111四种。两类互斥且覆盖全部情况，所以共1＋4＝5种。每种旧配置都能接D＝0或D＝1，且接完的串互异，因此变成5×2＝10种。直接算2³，会把不合法的001、010、011算进去。
题目2：先后条件会留下多少排列
四个不同任务P、Q、R、S各运行一次，唯一限制是P必须在Q之前，不要求相邻。合法执行顺序有多少？
**提示：**把任意排列中的P与Q交换位置，会发生什么？
**参考答案：**没有限制时共有4!＝24种。交换P、Q会把“P在Q前”变成“Q在P前”；再交换一次就回到原序列。这建立了两类排列间的一一对应。每个排列恰属于其中一类，两类数量相同，因此各有24÷2＝12种。这里除以2有可验证的配对理由，不能把任意一条限制都当成“删去一半”。
作者：Jiancheng Wang · 数学之美（独立原创）