为什么计数法则需要模型
题目里有几个数字,并不足以证明应该把它们相乘。计数前要先说明一个答案究竟是什么,以及一串选择怎样确定它。每个合法答案都能产生吗?不同的选择过程会产生同一个答案吗?只有解决这些问题后,计数法则才能回答原题。
分类与纤维
定义 2.4.1
(不相交分类与纤维)
集合 的子集族 称为 的一个不相交覆盖,如果它们两两不相交且并集是 ;这里允许成员为空集。对函数 , 上的纤维是 。纤维可以是空集。
定理 2.4.2
(加法法则与纤维法则)
若有限集 有由有限多个集合 组成的不相交覆盖,则 。若 是有限集之间的函数,则
特别地,如果每个纤维都有 个元素,那么 。
证明
(为什么没有遗漏或重复计数)
在加法法则中,各部分覆盖 ,所以每个元素至少属于一部分;各部分不相交,所以每个元素至多属于一部分。把各部分分别计数并相加,恰好把每个元素数一次。对于纤维法则,每个 恰好属于以 为标记的纤维。因此所有纤维构成 的不相交覆盖,其中允许空纤维。若纤维大小均为 ,相加便有 个相同的项。 时公式仍成立:这时 也必须为空。
映射的方向很重要。从描述到对象的编码映射可能把多个描述送入同一个纤维。如果每个对象恰有 个描述,就可以把描述总数除以 得到对象数。满射只保证纤维非空,并不保证纤维同样大。
例题 2.4.3
(大小不一的纤维不能统一相除)
设描述是 ,函数 把 送到 ,把 送到 。共有五个描述和两个对象,纤维大小分别为 和 。将五除以 或 都得不到对象数;正确的关系是 。必须先证明共同的纤维大小,才有理由用它作除数。
乘法与依赖先前结果的选择
定理 2.4.4
(有条件选择的乘法法则)
假设有限构造有 个阶段。第一阶段有 种选择;对每个长度为 的合法前缀,第 阶段都恰有 种选择,其中 。则完整合法选择序列共有 个。当 时,只有一个序列,即空序列,因此空积为 。
可选内容可以依赖先前选择;每一阶段只要求可选项的数目恒定。
证明
(对前缀归纳)
令 为长度为 的合法前缀集, 只含空前缀。删去最后一步给出从 到 的映射。每个前缀恰有 种延伸,故均匀纤维法则给出 。反复使用即得乘积。若某个因子为零,就没有完整序列;如果已经没有前缀能到达后续阶段,关于这些前缀的延伸条件便是真空成立的。
证明透视
均匀延伸数在哪里用到
证明沿着前缀集 逐步归纳,而假设只在一处进入:截断映射 的每个纤维都必须恰有 个元素。选择本身可以随前缀而改变,纤维法则只看它们的数目。若某个前缀有 种延伸,另一个却有不同的数目,则 只能写成对 中各前缀的延伸数求和,即下一段的分支树计数,而不是乘积。
两个退化情形不需额外处理便能完成论证。 只有空前缀一个元素,这正是空积等于 的原因。若某个 ,则 ,其后各阶段的纤维条件都真空成立,公式正确地给出 。归纳从未用到不同选择序列给出不同对象;那是另一个问题,由下一节的纤维法则处理。
若后续选择的数目不恒定,应对前缀求和。设第一步选 之后有 种完成方式,则两阶段序列总数为 。更长的构造也可以看成分支树:把每个第一分支之下的完整序列数相加。乘法是有关纤维大小相等时的特殊情形。
例题 2.4.5
(限制条件改变分支数)
从 中选不同的数,组成有序对 ,要求 为偶数。若 为奇数, 必须是另一个奇数;若 为偶数, 必须是另一个偶数。四种 各有一种延伸,所以共有 对:。
若改为要求 为奇数且 ,则 时的延伸数分别是 。相加得 ;此时分支数不相等,不能未经证明就用某个分支数乘以 。
例题 2.4.6
(各位不同且个位为偶数的三位整数)
有多少个三位整数的各位数字互不相同,且个位为偶数?首位不能是零。按个位是否为零分类,因为零与非零数字在首位的角色不同。
若个位是 ,百位有 种选择,十位有剩余的 种选择,本类共有 个。若个位是 之一,则个位有 种选择。百位既不能是零,也不能与个位相同,所以有 种选择;十位可取余下的任意 个数字,包括零。本类共有 个。
两类互不相交且覆盖所有情况,因此总数为 。每类内部的分支数都恒定,但两类之间不同。先选个位很方便;若把 乘上一个统一的后续选择数,就会忽略这个区别。
常见错误
(以错误顺序选择位置)
若先选百位(九种),再选十位(九种),个位剩下可用的偶数个数是五减去前两位已用的偶数个数,可能是 、 或 ,视先前的选择而定。最后一个阶段写不出单一因子,所以按这个顺序不能用乘法法则;要么按情形求和,要么像上例一样先选受限制的位置。
从序列到对象
例题 2.4.7
(委员会与有序职位)
从六人中选三人组成委员会。先数三个不同人的有序名单:共有 个。把顺序忘掉,就得到一个委员会。每个委员会恰有 种排列,因此纤维法则给出 ,委员会数为 。相反,如果三个职位分别是主席、秘书和财务,交换顺序会改变任命, 个序列就是不同答案,不应再相除。
反例模式
不能自动假设纤维均匀
两名不同的人各选三个无标记盒子中的一个,允许空盒。无标记的分配只有两种:两人在一起,或者分开。若先给盒子标记,则有 种分配。忘掉标记后,在一起的情况有三个描述,分开的情况有六个。把 除以 得 ,并非 。
应固定一个对象,数清它实际有多少个描述。本例中,两人在一起时交换两个空盒的标记不会改变分配。相反,对于非空且彼此不同的块,每种标记方式都产生不同分配。非空条件解释了为什么相邻的满射计数讨论中可以除以阶乘。
从两边计数同一个关联集合
前面我们把集合分成大小已知的纤维来计数。现在考虑相关的情形:同一个有限有序对集合,可以按第一坐标分组,也可以按第二坐标分组。两种划分都给出正确的计数。把它们并列便得到一个等式,有时不用逐一搜索各种配置,就能借这个等式排除某些可能性。
假设一群学生报名参加工作坊。我们可以询问每位学生参加了多少场,然后把答案相加;也可以询问每场有多少位学生参加,再把答案相加。每次报名在两种方法中都恰好计数一次,所以总数必须相等,即使两张清单中的各个数字可能很不一样。
设定
设 是有限学生集合, 是有限场次集合。关联集合是任意子集 。我们把 读作“学生 参加场次 ”。每个有序对要么属于 ,要么不属于,因此同一学生参加同一场次不会被记录两次。对 和 定义
称 为 的左度数, 为 的右度数。二者都可以是 。
命题 2.4.8
(双重计数)
对有限集合 及任意 ,
推论 2.4.9
(两边度数均匀时)
若每个 都满足 ,则 。若另外每个 都满足 ,则 。当 时,由此得到 ;当 时,等式只说明 ,不能除以 。
证明
(为什么两个和计数的是同一集合)
令 把 映到 。 上方的纤维是 。由于第一坐标固定,映射 给出从 到 的双射,所以 。
纤维 两两不交,因为一个有序对只有一个第一坐标。它们的并集是 ,因为每个有序对的第一坐标都属于 。因此纤维计数法则给出 。
对 应用同样的论证,得到 。
边界情形无需另作处理:
- 若 ,则 ,所以 。两个和都等于 :一个是空和,另一个是若干个零之和(若 也为空,则它也是空和)。
- 没有参加任何场次的学生对应空纤维,贡献 。
对于推论,常数之和为 。令 的两个表达式相等,便得 。
概念视角代数
双重计数就是矩阵求和的两种方式
把 记为关联矩阵 :行以 标记,列以 标记,当且仅当 时元素为 。于是 是所有元素之和。各行之和是左度数,;各列之和是右度数,。命题正是结合律 :先加各行总数或先加各列总数,得到的总和相同。
常见错误
(两个和不是两个阶段)
这两种划分是切分同一个集合 的不同方式,不是选择过程中的两个独立阶段,所以不能把两个和相乘。我们相加的是各纤维的大小,而这些大小可以随纤维而改变。
例题 2.4.10
(四位学生,三个场次)
令 ,,并设
左度数。
- Ada 参加 和 ,所以 。
- Bo 参加 ,所以 。
- Cy 参加 和 ,所以 。
- Di 参加 ,所以 。
和为 。
右度数。
- 有 Ada 和 Cy,所以 。
- 有 Ada 和 Bo,所以 。
- 有 Cy 和 Di,所以 。
和为 ,与 一致。
平均数。 右度数的平均值是 ,而在此例中,每个场次确实都有度数 。这是我们从数据中核实的事实,不能仅由平均值推出。左度数的平均值是 ,但没有学生参加了 场。每个 都是整数,实际取值是 和 。平均数描述的是总数平分后的结果,并不描述任何特定顶点。
反例模式
应该相加时误用乘法
人们可能会说:“四位学生,三个场次,所以共有 次参加。”但 计算的是所有可能的有序对。其中包括 ,而 Bo 并不参加 。事实上,十二对中有六对不存在。只有当 时,乘积 才等于 。
第二种错误朝相反方向发生。假设报名表在 之下把 Ada 列了两次。数表格的行会得到 ,但关联集合仍只有 个元素,因为 是同一个有序对。双重计数说的是集合 ,而不是可能含重复项目的清单。
习题
快速检查
(四位学生每人恰好参加两个场次,共有五个场次。证明不可能每个场次都有相同的正整数 位学生。然后给出一个具体安排,使每位学生仍参加两个场次。)
解答 · 答案
按学生计数得到 。如果每场都有 位学生,按场次计数便得到 ,因此 。由于 ,不存在合适的正整数 ,所以这样的配置不可能存在。
场次人数不等的安排则可以存在。取学生 和场次 ,使
- 参加 ,
- 参加 ,
- 参加 ,
- 参加 。
每个左度数都是 。右度数分别为 、、、、。它们的和为 ,符合命题。
快速检查
(设 ,,。计算所有度数,验证两个和,并求两边的平均度数。说明为什么给定的两个坐标纤维划分都不是等大小纤维。)
解答 · 答案
左度数是 、、、;右度数是 、、。两个和都等于 。
左边平均值为 。即便如此, 参加了两场,而 一场也没参加。
右边平均值为 ;能这样计算是因为 。若 ,右边便没有平均值,写 没有意义。
两边都不均匀:左度数取值 、、,右度数取值 、、。不存在每个场次共有的度数 ,所以本例不能使用等大小纤维法则;不能把平均值当作每个度数。
练习
快速检查
(有多少个三位十进制数字串的各位互不相同且末位为偶数?允许首位为零。)
先选末位,再检查前两位各剩下多少选择。
解答 · 答案
末位有五种选择,然后首位有九种,中间一位有八种。每个数字串恰由一个这样的过程确定,因此总数为 。首位允许为零对九种选择至关重要;三位整数有不同的限制。
快速检查
(集合 有 个元素,一个从 到三元素集的函数的纤维大小为 、、。求 ;此函数的纤维大小能相同吗?)
使用纤维求和,而不是乘法法则。
解答 · 答案
纤维法则给出 ,所以 。已有两个纤维大小不同,故不可能全都一样;另外, 也不能被 整除。
快速检查
(求满足 且 的整数有序对数目。为什么不能把第一步的三个选择乘以第二步的三个选择?)
分别数每个 对应的 值。
解答 · 答案
当 时, 分别有 个可能值,故总数为 。 所得的九个有序对会包括 等违反 的对;第二阶段的选择数并不恒为三。
快速检查
(从空集到三元素集有多少个函数?三个纤维的大小是多少?这个函数是满射吗?)
函数须为每个输入指定一个值;想想没有输入时这要求什么。
解答 · 答案
恰有一个函数:它是图像为空集的空函数。它的三个纤维都是空集,纤维大小之和 等于定义域大小。它不是到非空目标集的满射。这个函数对应一个空的选择序列;不要把它误认为空定义域中的一个元素。