6.1 加法、乘法与双射原理
第 5 章计算了算法执行某种操作的次数。有些循环容易计数，因为迭代区域形成直线、矩形或三角形。第 6 章将建立更一般的规则，不必逐个列出，也能计算可能性集合。
核心问题是：
> 有多少个对象满足给定描述？
使用公式前，必须明确什么算作一个对象，以及两条构造路径是否可能产生同一个对象。
集合与结果的计数
对有限集合 ，元素个数记作
如果
那么 。
所有可能结果组成的集合常称为结果空间。对结果空间计数，就是构造互不相同结果组成的有限集合，再求其基数。
例如，咖啡馆提供茶、咖啡或果汁，饮料选择集合为
所以 。
加法原理计算互斥选择
假设一个结果可以通过若干个互斥情况之一产生。若情况 1 有 种可能，情况 2 有 种可能，那么总数为
这称为加法原理。
用集合语言表示，如果有限集合 不相交，
那么
示例：选择一场工作坊
一名学生恰好参加一场工作坊：
- 场数学工作坊之一；或者
- 场设计工作坊之一。
没有工作坊同时属于两个类别。因此共有
种选择。
“恰好一个”和“或者”提示我们在处理替代情况，但只有“或者”并不能保证情况互斥。
重叠为什么造成重复计数
假设 名学生学习数学， 名学生学习计算机科学，其中 人两者都学。直接相加 会把这 人计算两次。
至少学习一门的人数应为
第 6.4 节会把这种修正发展为容斥原理。现在，只有确认各情况不会重叠后，才能直接使用简单加法原理。
乘法原理计算连续选择
假设一个完整结果分两个阶段构造：
1. 第一阶段有 种选择；
2. 对第一阶段的每一种选择，第二阶段都有 种选择。
那么完整结果共有
个。这称为乘法原理。
示例：搭配服装
从 件上衣中选一件，再从 条裤子中选一条。每件上衣都能与任意裤子搭配，因此共有
套服装。
每个结果是一个有序选择对：
这正是第 1 章的笛卡尔积：
多于两个阶段
假设密码有三个位置：
- 第一位有 个符号可选；
- 第二位有 个符号可选；
- 第三位有 个符号可选；
并且允许重复。那么共有
个密码。
一般地， 个位置各有 种选择，会产生
个字符串。
这里的“独立”只表示先前选择不会减少后面位置的可选项。它不是概率中的独立性，后续章节才会介绍概率独立。
决策树揭示何时加、何时乘
决策树表示一系列选择：
- 每条分支表示一个可选项；
- 从根到叶的一条路径表示一个完整结果；
- 同一条路径上的连续阶段用乘法；
- 分离的终止情况用加法。
假设套餐分为：
- 只选汤，有 种汤；或者
- 选择主菜与甜点，有 种主菜、 种甜点。
汤类情况贡献 ，两阶段情况贡献
两种套餐类型互斥，因此总数为
括号可以把结构写得更明确：
所以计数并不是寻找关键词，而是为完整结果怎样被构造建立模型。
搭建一棵节庆方案树，决定哪些门代表互斥替代，哪些门代表连续选择。铸造场会展开所有完整路径、检测重复叶子，并把树结构转换成和的乘积表达式。
双射原理通过可逆翻译计数
有时一个集合难以直接计数，却与一个已经会数的集合具有相同结构。
有限集合 之间的双射是函数
并且它既是单射又是满射。第 4.1 节说明，这表示 的每个元素都恰好对应 的一个元素。
因此：
这称为双射原理。
方法分三步：
1. 定义正向编码，把 中每个对象变成 中的对象；
2. 定义怎样反向恢复；
3. 由此确认不会碰撞，也不会遗漏目标。
二进制字符串与子集
令
每个子集 都能编码成长度为 的二进制字符串：
- 若 ，第 位写 ；
- 若 ，第 位写 。
对 ，子集
对应
编码可以反向恢复：读取值为 的位置，就得到原子集。
个位置各有 种选择，乘法原理给出
个二进制字符串。由双射原理，
这证明了第 1 章出现过的幂集计数。
为什么可逆性不可缺少
如果多个源对象映射到同一个编码，就不能直接转移计数，因为编码不是单射。
如果有些编码永远不会被使用，也不能建立集合大小相等，因为编码不是满射。
有效计数双射要求每个源对象恰好得到一个编码，并且每个允许编码都恰好解码为一个源对象。
示例：固定大小子集与二进制字符串
中恰含 个元素的子集，对应长度为 且恰有 个 的二进制字符串。
正向映射用 标记成员，反向映射读取所有 的位置。因此两个集合大小相同。
第 6.2 节会为这个共同数量引入标准记号：
现在最重要的是结构：可逆表示能把难数的集合转化为熟悉集合。
切换实时集合中的元素，观察二进制通行证同步变化；也可以直接编辑通行证来恢复集合。挑战包含长度错误的编码与固定重量编码，让单射、满射和可逆性都变成可观察条件。
本节衔接
当每个位置始终保留相同选择时，乘法原理可以直接计算字符串。如果先选的对象会从后续选择中消失，或者结果根本不关心顺序，会发生什么？第 6.2 节将用排列与组合回答这两个问题。