动机
许多计数问题都问:从较大的集合中选出一些对象,不考虑选取顺序,有多少种选法?例如,从一组人中选委员会,在二进制串中选择放置 的位置,或者在乘积中选择贡献某个变量的因子。这些问题具有相同的数学结构:都是在计算指定大小的子集的个数。
本章直接把二项式系数定义为这样的计数,再把阶乘公式作为定理证明,而非用它作定义。这样做很重要:下面每个恒等式首先都是关于集合的陈述。每个证明给出一个双射、一个不相交的分类,或对同一集合的两种计数;代数运算只在这些计数允许的情况下使用。
以下用 表示集合 ,约定 。有限集合 的元素个数记为 。我们使用两个基本计数原理:
- 加法原理:有限集合若是不相交部分的并,其大小等于各部分大小之和。
- 乘法原理:如果分阶段作选择,而且每一阶段的可选项个数不依赖之前的选择,那么总选法数等于各阶段选项数的乘积。
定义
定义 2.5.1
(二项式系数)
设 , 为任意整数。固定一个满足 的集合 。二项式系数 ,也记为 ,是满足 的子集 的个数。这种子集称为 的 元子集。
两点说明使这一定义更加精确。
首先,个数与所选的 元集合 无关。双射 通过 把 的 元子集映到 的 元子集, 给出逆映射。因此我们总可以取 。
其次,定义允许 是任意整数。 元集合的子集不可能有负数个元素,也不可能超过 个元素。因此
这称为越界取零约定。在这里它是定义的结果,并非额外添加的规则。它允许我们对所有整数 求和而不必单独处理边界,因为非零项只有有限多个。
定义 2.5.2
(阶乘与下降乘积)
当 时, 是乘积 。当 时,这是空乘积,值为 ,故 。对 ,下降乘积 恰有 个因子。当 时它也是值为 的空乘积。
定理 2.5.3
(阶乘公式)
对整数 ,
证明
(计数有序选择)
令 是由 中互不相同的元素构成的有序 元组 的集合。我们用两种方法计数。
直接计数。 有 种选择; 必须不同于 ,有 种选择。如此继续,到 时有 种选择。由乘法原理,
最后的等式来自 。
通过子集计数。 把每个元组映到其元素集合 。由于各项不同,这确实是一个 元子集。反过来,每个 元子集 恰好来自把 的元素按不同顺序排列得到的元组。由乘法原理,这样的顺序有 个。因此元组分成 个互不相交的组,每组大小为 。由加法原理,。
比较两个计数得到 。除以正整数 即得公式;这里的除法在有理数中进行,因而合法。
边界情况。 当 ,集合 恰有一个元素,即空元组,对应唯一的 元子集 。两种计数都等于 ,与 一致。当 时必有 ,而 ,因为 恰有一个子集,即它自身。上述论证无需修改即可涵盖两种情况。
定理 2.5.4
(对称性)
对 和任意整数 ,。
证明
(取补集)
映射 把 元子集映成 元子集。应用两次会回到原集合,因此它是两类子集之间的双射。如果 或 ,则分别有 或 ,两边均为 ;此时仍可把该映射看作两个空集合族之间的双射。
定理 2.5.5
(帕斯卡法则)
对 和任意整数 ,
证明
(指定一个元素)
以 为指定元素,计数 的 元子集 。每个 恰好属于以下两种情况之一。
- :此时 是 的 元子集;反之每个这样的子集都属于此情况,共有 个。
- :移除 得到 的 元子集 ;逆映射为 。此情况共有 个子集。
两种情况互不相交,因为一个元素不可能同时属于和不属于 ;它们也穷尽所有情况。由加法原理得到恒等式。
边界值。 即使集合族为空,上述双射仍然有效,不过直接检查极端情况也有帮助。
- 若 ,三项都为 。
- 若 ,等式为 。唯一的 元子集不含 ,而大小为 的子集不存在。
- 若 ,等式为 。全集含有 。
- 若 ,所有项都为 。
二项式定理
设 为含单位元 的交换环。对 和非负整数 , 表示 个 相加,且 。此外, 是空乘积。这里不需要除以 ,而且这种除法不一定可行,因为 中可能没有相当于 的元素。
定理 2.5.6
(二项式定理)
对交换含幺环 中的元素 和每个 ,
证明
(组合模型与归纳)
模型。 将 写成 个因子的乘积。反复使用分配律得到 个词 的和,其中每个 是 或 。令 为 的位置集合。因为 可交换,可以重排字母,使该词等于 。词与子集 一一对应,恰有 个词满足 ,合并这些项便得到系数。下面用归纳法证明同一结果,避免只依靠对“展开”的非形式描述。
基础情况 。 左边是空乘积 ,右边是 。
归纳步骤。 假设结论对 成立。将求和范围保持为 ,使下面所有幂的指数都非负:
第一项乘以 得到 ,令 。第二项乘以 得到 ;这一步使用了 。由分配律,整数倍与每个环元素可交换,因此系数不会造成困难。换元后两个和为
为使两式都在 的范围内,第一式添加了 项,第二式添加了 项。两项的系数均为 ,而涉及的指数均非负。合并并应用帕斯卡法则得到
这正是 的结论,完成归纳。
证明透视
交换性与零约定在哪里进入
这个归纳只有一步真正不平凡,另有两个假设在明确的位置使用。这一步是在第一个和式中作指标平移 等于 加一,使两个和式对齐,帕斯卡法则才可以逐个系数地合并它们。交换性只用了一次:把 乘 的 次方改写为 的 次方乘 ;其他地方因子的次序都无关紧要。范围外为零的约定则用来把两个和式延伸到共同范围 0 至 加一而不改变其值,使帕斯卡法则在两个端点也可使用。合并后的系数恰好就是 加一时的结论,基础情形则是空积,论证因此闭合。下面的反例拿走交换性那一步,说明其他条件都不能代替它。
证明依赖所选元素满足 。若没有这个关系,上述恒等式可能不成立,如下例所示。
反例模式
不可交换的矩阵
在实数 矩阵环中取
则
因此 。又 ,且 ,故 。另一方面,
正确展开是 。两个混合乘积是不同矩阵,不能合并成 。
来自子集的恒等式
定理 2.5.7
(行和与奇偶性)
当 ,。当 ,
证明
(两种计数与切换双射)
行和。 用两种方法计数 的子集。首先由乘法原理,每个元素可独立选择放入或不放入,共有 个子集。其次,按大小分类并使用加法原理,得到 。当 ,两个计数均为 ,因为 是唯一的子集。
奇偶性,。 固定元素 ,它因 而存在。定义切换映射 :如果 就移除它,否则加入它。由于 , 是 的子集族到自身的双射。它使 恰好改变 ,所以反转奇偶性。因此 限制为偶数大小子集与奇数大小子集之间的双射。两族大小相等,合起来包含全部 个子集,各有 个。
不同。 偶数项之和为 ,奇数项之和为 。此时没有元素可切换,因此上述双射不存在。从代数上说,在二项式定理中取 、 得到 :当 时为 ,但 时是空乘积 。
定理 2.5.8
(加权和)
当 ,。当 ,该和为 。
证明
(计数有序对)
令 是所有满足 、 的有序对 的集合。可以把 想成委员会, 想成主席。
先选委员会。 元子集 有 个可能的主席,按大小求和得 。
先选主席。 有 种选择。委员会其余成员可以是剩下 个元素的任意子集 ,并令 。 有 种选法,因此 。
两种计数描述同一个有限集合,因此相等。当 ,不存在这样的有序对,和为 。此时 不是任何对象的计数,所以要单独陈述 的情况。
定理 2.5.9
(范德蒙德(Vandermonde)恒等式)
对 及任意整数 ,
证明
(拆分委员会)
设 为不相交集合,、。计数 的 元子集 ,共有 个。
每个 确定一个数 。不同的 给出不相交的情况,所有情况合起来包含每个 。
固定 。映射 是到如下有序对集合的双射:第一项为 的 元子集,第二项为 的 元子集。逆映射是 。由于 , 可分别从 和 恢复,因此逆映射是单射。由乘法原理,该情况有 个子集;再由加法原理得到恒等式。
若 或 ,相应项为 ,正确地计数了不可能发生的情况。若 或 ,左边每项及右边都为零。
取 、,并利用对称性 ,得到
在范德蒙德恒等式的证明中,所选的 是一个无序集合。拆分 只是记录每位成员来自哪个原组,没有赋予成员顺序,也没有创造新对象。 与 是固定且有标签的,所以有序对 定义明确。
概念视角代数
把范德蒙德恒等式看成多项式的乘积
同一恒等式也是系数比较。由多项式环 中的二项式定理,
左边 的系数汇集所有 的乘积,正是范德蒙德恒等式中的和;右边则是 。双射证明中的拆分 ,在这里变成第一个因子贡献的指数。
例题
例题 2.5.10
(从 人中选 人)
从 位数学家和 位物理学家中选出 人。按所选数学家的人数 分类:
各项对应 ,即 。总数与 一致。
例题 2.5.11
(有指定成员的三元子集)
以 为指定元素,帕斯卡法则给出 。 的三元子集中,有 个不含 ,另有 个含 。
现在计数满足 、 的有序对 。先选委员会得到 。先选主席: 有 种选择,再从余下 个元素中选 个,有 种,得到 。两种计数一致。
例题 2.5.12
(第 行与奇偶性)
时 的值为 ,和为 。偶数 项的和为 ,奇数 项的和为 ,都等于 。
固定元素 的切换映射说明这个双射。例如,它把 ,并把 。
例题 2.5.13
( 时的平方和)
的值为 。平方和为 ,而 。项 等于 ,它计数一个 元集合中从前一半恰选一个、从后一半选两个的三元子集。
常见错误
反例模式
把重叠情况直接相加
计数 中含 或 的二元子集。含 的有 个,含 的也有 个,但答案不是 ,因为子集 同时属于两类,被计算了两次。
正确列表为 ,共 个。容斥原理得到相同结果 ;取补集也一样:,因为只有 同时避开两个元素。加法原理要求各情况不相交。帕斯卡法则和范德蒙德恒等式的证明有效,是因为情况分别由一个元素的归属或数字 唯一确定。
常见错误
(有标签与无标签)
计数从 人中选“甲队”、其余人为乙队的方法,不是将 人分成两个无标签人对的方法。每个无标签划分对应两种有标签选择,因此只有 种划分。
常见错误
(在 时使用奇偶恒等式)
该恒等式需要一个可切换的元素,所以不适用于 :此时偶数项之和为 ,奇数项之和为 。
常见错误
(在环中除以 )
二项式定理中的系数作为整数作用于环元素。证明不需要在 中除以 ,这样的除法也可能不可行。
练习
快速检查
(由定义及阶乘公式分别计算 。)
数一数空集的子集。
解答 · 答案
空集恰有一个子集,即 自身,其大小为 ,故 。阶乘公式给出 ,其中 是空乘积。
快速检查
(求 ,并对 、 验证帕斯卡法则。)
利用范围外为零的约定。
解答 · 答案
不存在含 个元素的子集,所以 。帕斯卡法则为 ,即 。 唯一的 元子集是 ,它不含 。
快速检查
(分别计算 和 时偶数项与奇数项的行和。)
检查是否有可切换的元素。
解答
当 ,偶数项之和为 ,奇数项之和为 ;二者不等,因为没有元素可切换。
当 ,偶数项之和为 ,奇数项之和为 ,均等于 。切换映射交换 和 。
快速检查
(直接计算 ,与加权和公式比较。)
利用第四行 。
解答 · 答案
。公式给出 ,两者一致。
快速检查
(求 中 的系数。)
把 的指数与 对应。
解答 · 答案
在 中取 、,系数为 。
快速检查
(验证 、、 时的范德蒙德恒等式。)
对 求和。
解答 · 答案
,与 一致。
快速检查
(验证 时的平方和恒等式。)
利用第二行 。
解答 · 答案
,与 一致。
快速检查
(令 、,证明 且 。)
逐个元素计算各个乘积。
解答
两个乘积为
因此 。接着 ,故 。平方为 和 ,所以
二者之差为 ,与正确展开 一致。