组合证明的艺术

3.2 二阶递推恒等式 41
3.3 三阶递推恒等式 43
3.4 k 阶递推恒等式 47
3.5 来点实在的! 任意权重与初始
条件 48
3.6 注记 50
3.7 练习 50
第 4 章 连分式 53
4.1 连分式的组合解释 53
4.2 恒等式 56
4.3 非简单连分式 62
4.4 再来点实在的 64
4.5 注记 64
4.6 练习 64
第 5 章 二项式恒等式 67
5.1 二项式系数的组合
解释 67
5.2 基本恒等式 68
5.3 更多二项式系数恒
等式 73
5.4 可重复选择 76
5.5 帕斯卡三角形中的
奇数 82
5.6 注记 86
5.7 练习 86
第 6 章 正负号交错的二项式
恒等式 89
6.1 奇偶性讨论与容斥
原理 89
6.2 正负号交错的二项式系数
恒等式 92
6.3 注记 99
6.4 练习 99
第 7 章 调和数与斯特林数 101
7.1 调和数与排列数 101
7.2 第一类斯特林数 103
7.3 调和数的组合解释 108
7.4 调和数恒等式的证明 110
7.5 第二类斯特林数 115
7.6 注记 119
7.7 练习 119
第 8 章 数论 122
8.1 算术恒等式 122
8.2 代数与数论 128
8.3 重提最大公因数 132
8.4 卢卡斯定理 134
8.5 注记 137
8.6 练习 138
第 9 章 进阶斐波那契和卢卡斯
恒等式 140
9.1 更多斐波那契和卢卡斯
恒等式 140
9.2 着色恒等式 145
9.3 一些 “随机” 恒等式与
黄金分割 153
9.4 斐波那契和卢卡斯
多项式 158
9.5 负数 160
9.6 开放问题和瓦伊达
(Vajda) 数据 160
章节练习中部分习题的提示与
解法 164
参考文献 190

.　　 答 1 由 0 个学生组成的班委会为 (0n )个, 由 1 个学生组成的班委会为(1n )个, 总而言之, 由 k 个学生组成的班委会的种类是 (nk )种. 因此, 班委会的种类的总和为 ∑
　　n
　　k = 0
　　(nk )种.
　　 答 2 为了组建一个任意学生数目的班委会, 我们需要决定每个学生是否属于班委会. 因为这 n 个学生中的每一个学生要么在班委会, 要么不在,所以每个学生都有两种可能性, 因此有 2n 种方法.
　　 我们在这两个答案上的逻辑都无懈可击, 因此它们一定是相等的, 即恒等式成立.
　　 另一个有用的证明技巧是把一个恒等式的左边表示为一个集合的大小,右边表示为另一个不同的集合的大小, 然后在两个集合之间建立一个一一对应关系. 我们用如下恒等式说明证明结构
　　∑k≥0
　　(2nk ) = ∑k≥ 0 (2kn+ 1 ), n > 0.
　　 这两个求和都是有限的, 因为当 i > n 时, 有 (ni ) = 0. 因此很容易看出等式两边计数的意义, 关键是找出它们之间的对应关系.
　　 集合 1 从有 n 个人的班里选偶数个人组成一个班委会, 这个集合的大小是 ∑k≥0(2nk ).
　　 集合 2 从有 n 个人的班里选奇数个人组成一个班委会, 这个集合的大小是 ∑k≥0(2kn+ 1 ).
　　 对应关系: 假设班里有一名学生叫作沃尔多, 那么任何一个有偶数个成员的班委会都可以通过问 “沃尔多在哪儿” ∗ 变成一个有奇数个成员的班委会.如果沃尔多在班委会里, 那就去掉他ꎻ 如果他不在班委会里, 那就加上他. 无论哪种方法, 班委会的成员数都将由偶数变成奇数. 由于 “去掉或加上沃尔多” 的过程是完全可逆的, 所以我们在这些集合间得到
　　 一个一一对应的关系. 因此, 这两个集合必须大小相等, 于是恒等式成立.
　　 如果我们认为另一种证明方法会给问题的解决带来新的思路, 通常我们会用不止一种方法证明恒等式. 例如, 上面的恒等式也能通过直接计算偶数子集数来证明. 参见恒等式 129 及后续讨论.
　　 在阅读本书时, 你会期待看到哪些内容呢? 第 1 章介绍了一种斐波那契数列的组合解释, 即用方砖和多米诺砖进行平铺的问题, 它是第 2 ~ 4 章的基础.我们从此处切入是因为斐波那契数列本身很有趣, 并且作为组合学的内容, 它
　　的证明过程对于许多读者来说也将是一种意外的愉悦. 与所有章节一样, 本章以基本的恒等式和简单的论证开始, 这将有助于读者在接触更多复杂材料前熟悉概念. 推广斐波那契平铺将允许我们探究涉及广义范围的斐波那契数的恒等式, 包括卢卡斯数 (第 2 章)､ 线性递推 (第 3 章) 和连分式 (第 4 章).
　　 第 5 章介绍的是二项式系数的经典组合内容. 对集合计数的计重或不计重会得出有关二项式系数的恒等式. 第 6 章介绍了含有交错正负号的二项式恒等式. 通过在两个含有奇数个元素的集合和偶数个元素的集合间寻找对应关系,
　　我们可以通过 “容斥原理” 避免使用已熟知的过度计数或计数不足的方法.
　　 调和数, 就像连分数, 都不是整数. 因此, 组合解释需要研究具体表达式的分子和分母. 调和数与第一类斯特林数是相互关联的, 第 7 章探究了这种关联以及第二类斯特林恒等式.
　　 第 8 章考虑了更多的经典结果, 它们均来自算术､ 数论和代数学, 包括连续整数之和､ 连续平方和､ 连续立方和及费马小定理､ 威尔逊定理以及拉格朗日定理的一个部分逆定理.
　　 第 9 章我们处理了更为复杂的斐波那契恒等式和二项式恒等式. 这些恒等式需要巧妙的论证, 引入着色平铺或用概率模型等. 它们也许是本书最具挑战的部分, 但的确值得花时间去研究.
　　 我们偶尔会脱离恒等式去证明有趣的应用, 例如, 第 1 章中关于斐波那契数的可除性证明, 第 2 章中一个小魔术, 第 5 章中计算二项式系数奇偶性的捷径以及第 8 章中任意素数同余的推广等.
　　 除了第 9 章, 每一章节都给有兴趣的读者准备了一些对应的练习, 从而帮助他们检测自己的计数技巧. 大多数章节都包含了一些依然在寻求组合证明的恒等式. 书中包括了习题提示, 参考书目, 并且在附录中列出了书中所涉及的全部恒等式.
　　 我们希望每一章节是独立的, 这样您就可以用一种非线性的方式去阅读.
　　谁应当计数?
　　 这个问题最直接的答案是 “每一个人!” , 我们希望本书可以让没有经过数学专业训练的读者来欣赏. 本书的大多数，证明高中水平的学生都可以接受.另一方面, 教师也许可以将这本书作为有用的教学资源, 它侧重了证明的书写过程以及对问题的创造性处理技巧. 我们不将这本书看成是对组合证明的
　　完整概述. 相反, 这只是一个开始. 阅读完之后, 你再也不会用之前的方法看待斐波那契数和连分数之类的数字了, 我们希望例如表示斐波那契数的恒等式f2n + 1 = ∑ni = 0n∑j=0(n -j i ) (n i- j )可以让你感觉到有些东西正在被计数并且有去计数的意愿. 最后, 我们希望这
　　本书能激励那些希望发现旧恒等式的组合学解释或是新的恒等式的数学家. 亲
　　爱的读者, 我们诚邀您在之后的版本中与我们分享你们喜爱的组合学证明.
　　 我们希望为完成这本书的所有努力在某些方面是有价值的.谁对本书的完成做出了贡献?
　　 我们荣幸地感谢为这本书的完成做出直接贡献或间接贡献的人们. 那些早于我们的, 对组合学证明的兴起具有推动作用的人. 以下的书籍是我们不能忽视的, 有丹尼斯􀅰 斯坦顿和丹尼斯􀅰 怀特的 «构造组合学», 理查德􀅰 斯坦利的«计数组合学» 的第一和第二辑, 伊恩􀅰 古尔登和大卫􀅰 杰克逊的 «组合计算»,
　　荣􀅰 雷姆尔特､ 高德纳和帕塔许尼克的 «具体数学». 除了这些数学家, 其他人的工作也启发了我们, 包括乔治 E􀆰 安德鲁斯､ 大卫􀅰 布雷苏德､ 理查德􀅰 布鲁阿尔迪､ 伦纳德􀅰 卡里茨､ 艾拉􀅰 盖赛尔､ 阿德里亚诺􀅰 盖莎､ 拉尔夫􀅰 格里
　　马尔迪､ 理查德􀅰 盖伊､ 斯蒂芬􀅰 米尔恩､ 吉姆􀅰 普罗普､ 玛尔塔􀅰 斯韦德､赫伯特􀅰 维尔夫, 以及多伦􀅰 泽尔博格.寻求组合学定理证明过程的好处之一是能让本科研究者参与进来. 在此感谢罗宾􀅰 鲍尔､ 蒂姆􀅰 加内斯､ 丹􀅰 奇乔､ 卡尔􀅰 马赫博格､ 格雷格􀅰 普勒斯
　　顿以及克里斯􀅰 哈努撒､ 大卫􀅰 盖普勒､ 罗伯特􀅰 盖普勒和杰里米􀅰 劳斯, 他们获得了哈维穆德学院贝克曼研究基金､ 霍华休斯医学研究中心以及珍妮特􀅰迈尔的本科生研究奖励支持. 我们的同行们彼得 G􀆰 安德森､ 鲍勃􀅰 比尔斯､ 杰
　　伊􀅰 科德斯､ 杜安􀅰 德􀅰 唐普勒､ 佩尔西􀅰 戴康尼斯､ 艾拉􀅰 盖塞尔､ 汤姆􀅰哈尔沃森､ 梅尔文 􀅰 豪斯特､ 丹 􀅰 卡尔曼､ 格雷格 􀅰 莱温､ T􀆰 S􀆰 迈克尔､迈克􀅰 欧瑞森､ 罗伯􀅰 普拉特､ 吉姆􀅰 普罗普､ 詹姆斯􀅰 坦顿､ 道格􀅰 韦斯特､
　　比尔􀅰 兹维克尔, 尤其是弗朗西斯􀅰 苏, 为我们提供了思路､ 恒等式､ 结果或是其他珍贵的信息.
　　如果没有唐􀅰 阿尔伯斯的鼓励, 丹􀅰 威尔曼的工作以及美国数学协会的道奇阿尼委员会, 我们将不会完成本书.
　　 最后, 我们永远感激我们的家人所给予的爱与支持.