动机
计数公式是否可靠,取决于其中的对象与所计数的选择之间的对应是否恰当。有序选取、子集与函数回答的是不同的问题,即使同样的整数出现在它们的公式中也是如此。基本的做法是:先明确对象,再判断各次选择是否相互独立、各种情形是否互不相交,或者被禁止的性质是否相互重叠。
定义
定义 2.1.1
(选取与被禁止的性质)
对于整数 与 ,二项式系数 计数 元集合的 元子集。不允许重复的有序选取共有 种可能。 的一个排列是该集合到自身的一个双射;错位排列是没有不动点的排列。当每个目标元素至少有一个原像时,称该函数为满射。
每个 元子集有 种排列顺序,所以 ,其中 。除以 的依据是各纤维大小一致,而不是仅仅因为出现了重复。如果各对象的编码个数不同,除以单一的因子未必行得通。
定理/命题
定理 2.1.2
(容斥原理)
设 是有限全集 的子集,则不属于任何 的元素个数为
其中 时的交集取为 。
定理 2.1.3
(错位排列与满射)
对于 ,错位排列的个数为 。对于大小为 的定义域与有标号的、大小为 的目标集,满射的个数为
其中在计数从空定义域出发的函数时,约定 。
证明思路
证明
(每个元素贡献一或零)
固定一个元素 ,并设它恰好属于 个被禁止的集合。当且仅当 是这 个指标的子集时, 属于 ,所以它对容斥和的总贡献为 。当 时这个值为 ,否则为 ,恰好计数了被允许的元素。对有限集 把这些贡献相加即证明该定理,而无需假设被禁止的集合互不相交。
证明透视
交换求和次序完成了全部工作
唯一不明显的一步,是不再逐个集合阅读右边,而是逐个元素阅读:各指标集的交集大小之和,等于对每个元素数出包含它的交集有多少个。 有限,这一交换才成立。交换之后,多集合的公式就塌缩为单变量的二项式和。空指标集的交集按约定为 ,它提供了数值 1 的那一项;正因如此, 为零的被允许元素保持权重一。证明从未用到被禁止集合互不相交,所以各层次的重叠一次性得到修正。
证明
(由一般公式得到错位排列与满射)
对于错位排列,取全集为 个排列,并令 表示位置 是不动点。固定指定的 个位置后,其余位置上还有 个排列。这样的位置集合有 个,于是容斥原理给出该公式。
对于满射,全集为全部 个函数。令 表示目标 未被取到。漏掉指定的 个目标后剩下 个函数,因为每个定义域元素独立地在其余目标中选取一个。同样把容斥各项按 分组。
若 ,满射的计数为零:定义域元素更少的函数不可能取遍每个目标。这是对公式结构的检验,而不是额外的修正项。
例题详解
例题 2.1.4
(区分子集与函数)
从七个人中选三名委员:不计顺序,所以共有 个委员会。给不同的人分配主席、秘书与司库:此时职位有标号,共有 种分配方式。如果一个人可以兼任多个职位,则每个职位独立地从七人中选一人,答案变为 。
例题 2.1.5
(完整的错位排列计算)
将四封有标号的信放入四个有标号的信封,
最后两项分别对应三封信固定与四封信固定。三封信固定会迫使第四封也固定,但容斥原理有意保留这些相互重叠的事件;若将它们删去,抵消就会被破坏。
概念视角分析
把错位排列看成截断的指数级数
把公式除以 ,得 ,即 级数的部分和。 之后的交错尾项绝对值小于 ,所以
于是 是最接近 的整数: 时 ,四舍五入得 。错位排列占全部排列的比例趋于 。
例题 2.1.6
(放入有标号盒子的满射分配)
把五个不同的物体放入三个有标号的非空盒子。一种放法就是从物体到盒子的一个满射,所以个数为 。如果盒子没有标号,则每个分成三个非空块的划分恰好对应 种标号方式,得到 。非空性使这一除法是均匀的。
以两种方式计数同一个对象
双重计数的证明从一个明确定义的有限集出发,再用两种不同的分解方式计算它的大小。这一论证的力量来自两次使用的是同样的对象。如果两边计数的是不同种类的有标号或无标号对象,看似成立的恒等式反而可能隐藏着一个遗漏的因子。
例如,计数由一个固定大小的子集与该子集中一个指定元素构成的对。先选子集,得到其二项式计数乘以它的大小。先选指定元素,则需要从其余元素中选取一个较小的子集。使这两个计数相等,就证明了联系相邻二项式系数的那个熟知恒等式。指定的元素并非装饰:它解释了为什么会出现多出来的乘法因子。
另一种有用的双重计数,是按所选子集中来自两个不相交总体的元素个数对它进行划分。从它们的并集中选取子集,给出一个二项式系数。对每一种可行的拆分,把两个总体各自选取方式的乘积相加,得到相同的总数。这些情形互不相交,因为每个子集都有唯一确定的拆分大小。这证明了二项式卷积恒等式,同时说明了为什么只有在把不可能的选取所对应的二项式系数定义为零时,求和范围才可以安全地包含这些选取。
重复选取与隔板法的对应
允许重复的选取与选取子集是不同的模型。设把一个非负整数总量分配到固定正数个有标号的盒子中。每一种分配是一个非负整数元组,其各分量之和等于该总量。
定理 2.1.7
(隔板法)
设 、 为整数。满足 的非负整数元组 共有 个。若要求每个 ,当 时共有 个,当 时为零。
证明
(星号与棒号的串对每种分配恰好编码一次)
用一行 个星号表示各个单位,用 个棒号分隔各盒的内容。相邻的棒号表示一个空盒,位于两端的棒号则允许第一个或最后一个盒子为空。这种排列共有 个位置,所以选取 个棒号的位置就计数了这些串。
这一对应是双射:读出棒号之前、之间与之后的星号个数,恰好恢复出一个计数元组;由元组构造排列,则恰好恢复出一个星号与棒号的串。这证明了第一个公式。
如果每个盒子必须至少得到一个单位,则先从每个盒子中取走一个单位。映射 是到总量为 的非负元组的双射。若 为负,则不存在分配方式;否则以总量 应用第一个公式,得到 。
盒子由它们在排列中的次序来标号。去掉标号会把问题变为整数分拆,并使这一直接的公式失效。下界条件是通过一个可逆的平移来处理的,而不是对最终的计数作临时的扣减。
举一个具体的例子:把八个相同的单位分配到三个有标号的非空盒子。从每个盒子各取走一个后剩下五个单位,在七个位置中选取两个棒号的位置,得到 种可能。若是不同的物体,则需要另一个模型:一个计数元组并不说明具体哪些物体进入了每个盒子。这一缺失的信息正是满射的例子计数大得多的原因。
为什么交错的符号是必然的
容斥原理看起来像是一条需要记住交错符号的规则。它的证明给出了更好的解释。违反若干条件的对象一开始被计数过多;减去两两的交集可以修正这一点,但随后会对更高阶的重叠修正过度。二项式的抵消对每个单独的对象同时检验了所有这些修正。符号之所以是必然的,是因为要求每个被禁止的对象的净贡献为零。
在定义被禁止的性质之前,还应当先确定全集。对于错位排列,全集中只含有双射,所以固定若干位置后,剩下的标号构成一个排列。对于满射,全集包含全部函数,所以漏掉若干目标标号后,每个输入都有独立的选择。混淆这两种全集会把阶乘换成幂,或者反过来,即使完全记住了符号,得到的公式也是错误的。
错位排列的递推观点
还有第二种组织错位排列的方式,与容斥原理互为补充。
命题 2.1.8
(错位排列的递推式)
取 、,则对 ,错位排列数满足 。
证明
(按第一个标号是否位于二循环分情形)
在 的错位排列中,像 可以是其余 个标号中的任何一个。固定 。此时有两种情形:,构成一个二循环;或 。
在二循环的情形中,删去标号 与 。其余 个标号上的排列必须是错位排列,而且在恢复二循环之后,每个这样的错位排列都能被唯一地重建。在另一种情形中,把 从它所在的循环中移走:原来指向 的前驱现在指向 。由于该前驱不是 ,不会产生不动点,于是得到 以外 个标号上的错位排列。反过来,由这样的错位排列出发,把 插入其循环中 的紧前面。这一重建是唯一的,并且属于第二种情形。
因此,对 的 种选择中的每一种,这两种情形共贡献 。当 时,第一种情形用到 ,即空排列,第二种情形用到 。
这个递推式可以与交错和公式作数值上的核对,但双射论证解释了它为什么必然与之一致。这两种方法揭示了同一批对象的不同结构。
何时可以用对称性作除法
有标号盒子的例子之所以除以一个阶乘,是因为每个分成固定个数非空块的无标号划分恰好对应这么多种标号方式。每个块可由它实际包含的元素区分,所以赋予不同的盒子标号会给出全部阶乘个互不相同的有标号分配。空块会破坏这种简单的均匀描述:交换两个空的有标号盒子,并不像交换两个非空盒子的内容那样改变一个分配。
旁注
追问每个编码纤维的大小
在作除法之前,先定义那个忘记标号或顺序的映射。然后证明每个目标对象都有相同个数的原像。如果纤维大小不一,单一的除数就无法成立。更高等的对称性方法可以处理稳定子大小不同的情形,但在这里修正初等的计数模型并不需要它们。
纤维的观点也是检验答案的有用方式。一个被提出的公式在最小的可能输入下应当合理,在要求不可能满足时应当为零。这样的边界检验不能代替证明,但往往能在冗长的算术开始之前就发现错误的模型。
常见错误
常见错误
(把相互重叠的性质的计数直接相加)
相加计数要求各情形互不相交。把 相加,会使每个元素按其具有的性质个数被重复计数,这就是必须修正重叠的原因。反过来,相乘计数要求每一步的选择个数对此前的每种选择都是已知的。计数中的独立性,说的是这些选择个数的性质,而不一定是概率意义上的独立性。
常见错误
(抽屉原理证明存在性,而非计数)
抽屉原理指出,把多于 个物体放入 个盒子,必有某个盒子至少含有 个物体:否则总数至多为 。它证明的是存在性,而不是分配方式的个数。当问题要求精确的总数时,不要用它来代替计数公式。
有标号盒子例子中的除法,是最容易丢掉假设的地方。
反例模式
盒子可以为空时除以标号方式数
断言:把五个不同物体放入三个无标号盒子、允许空盒的方法数,等于有标号的计数除以 3 的阶乘。有标号的计数为 3 的 5 次方,即 243,而 243 除以 6 等于 40.5,不是整数,所以断言不成立。按非空块的个数直接计数:分成一块有 1 种,分成两块有 15 种,分成三块有 25 种,共 41 种。分成一块的划分只有 3 种标号方式,分成两块或三块的划分各有 6 种,确实 3 + 90 + 150 = 243:纤维并不均匀。只有在要求每个盒子非空时,如例题所示,这一除法才成立。
总结
双射与均匀的编码计数为乘法和除法提供了依据。容斥原理通过抵消每个对象的多余贡献,来计数不具有任何被禁止性质的对象。错位排列禁止不动点;满射禁止漏掉目标。
练习
快速检查
(计数由四个字母构成、长度为六、且每个字母都出现的字符串。)
各位置不同,字母有标号。
解答 · 答案
一个字符串就是从六个位置到四个字母的函数,而要求四个字母全部出现,恰好就是满射性。个数为 。最后的 项为零。字母允许重复。
快速检查
(证明任意六个整数中必有两个,它们的差可被五整除。并解释为什么这一结论没有指定唯一的一对。)
用余数类作为盒子。
解答 · 答案
把每个整数放入它模 的余数类中。六个整数放入五个盒子,必有两个落在同一类,它们的差可被 整除。可能有几个盒子各含一对,也可能有一个盒子含有三个或更多个元素,所以这一存在性证明并不断言唯一性。
快速检查
(用递推式计算 ,并用交错和公式核对。)
递推式需要 与 。
解答 · 答案
由 、,递推式给出 、、。交错和给出 ,两者一致。