本书作者采取对话式的风格讲述了关于组合数学的有趣的内容，使读者能感受到阅读的愉悦。书中时不时会有一些惊喜，比如用图像化的处理方法以及用易于推广的证明方式，证明了许多组合数学中重要的恒等式。
全书共有 ９ 章: 第 １ 章介绍了斐波那契数列的组合解释；第 ２ 章介绍了广义斐波那契数列和卢卡斯数列；第 ３ 章通过对平铺进行着色，引入了线性递推的组合解释；第 ４ 章介绍了连分式；第 ５ 章介绍了有关二项式系数的内容；第 ６ 章讨论了正负号交错的二项式恒等式；第 ７ 章探究了调和数与*类斯特林数之间的关系；第 ８ 章介绍了连续整数和、 费马小定理、 威尔逊定理以及一部分拉格朗日定理的逆定理；第９ 章介绍了进阶斐波那契恒等式和其他一些恒等式。
本书可作为组合数学课程的补充读物，读者无论是高中生还是数学方面的研究人员，均会不同程度地受益。

本书的每一个证明最终都可以归纳为一个计数问题, 通常用两种不同的方法数数. 计数会给出美丽, 通常基本, 且简洁的证明. 虽然它不一定是最简单的方法, 但它却提供了另一种理解数学事实的途径. 对于一个组合数学
研究者, 这种证明方法才是唯一正确的. 我们把这本书献给各位读者, 作为罗杰􀅰 内尔森的著作 «数学写真集Ⅰ ———无需语言的证明» (机械工业出版社出版) 相应的计数版本.
为什么计数?
作为人类, 我们在很小的时候就学会了如何数数. 一般一个两岁的孩子就会自豪地数到 10, 以得到父母的称赞. 虽然很多成年人说自己数学很差,但却没有人承认自己不会计数. 计数是我们最早用到的工具之一. 物理学家恩斯特􀅰 马赫甚至说: “在数学中不存在不能通过直接计算解决的问题.”[36]
组合证明可以尤其强大. 至今, 我 (A􀆰 T􀆰 B􀆰 ) 仍记得当我还是一名大
一新生时, 第一次接触组合证明时的情形. 我的教授通过 ( x + y)n =
(x + y)(x + y)􀆺(x + y)
üïïïïïýïïïïïþ
n次 证明了二项式定理
(x + y)n = ∑
n
k = 0
(nk )xkyn - k.
在证明定理的过程中, 他问大家有多少种方法可以得到 xkyn - k项. 忽然一切都清楚了. 是的, 我之前见过很多种二项式定理的证明, 但他们看起来十分笨拙, 我那时常想一个思维正常的人是怎么创造出这么一个结果的. 但现
在, 这看起来非常自然. 我永远也不会忘记这个结果.
数什么?
我们选择了我们最喜欢的, 使用数学中常出现数字的 (二项式系数､ 斐波那契数､ 斯特林数等) 恒等式, 并且选用了优雅的计数证明. 在一个典型的恒等式中, 我们提出一个计数问题, 分别用两种不同的方法回答. 一种方法的答案是恒等式的左边, 另一种方法是恒等式右边. 由于两个答案解决的
是同一个计数问题, 所以它们必须相等. 恒等式可以看作是从两个不同的角度解决的计数问题. 我们用恒等式 nk = 0(nk ) = 2n 来举例说明本书的证明结构. 计算 (nk )不需
要使用公式 n􀆱k􀆱 (n - k) 􀆱 . 取而代之, 我们用 (nk )表示由 n 个元素组成的集合中任意选取 k 个元素组成的子集的个数, 或是更形象地, 其表示从有 n 个人的班级中选出 k 名学生组成一个班委会的方法数.
问题 从有 n 个人的班级中组成一个班委会有多少种选法?
答 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􀆰 迈克尔､迈克􀅰 欧瑞森､ 罗伯􀅰 普拉特､ 吉姆􀅰 普罗普､ 詹姆斯􀅰 坦顿､ 道格􀅰 韦斯特､
比尔􀅰 兹维克尔, 尤其是弗朗西斯􀅰 苏, 为我们提供了思路､ 恒等式､ 结果或是其他珍贵的信息.
如果没有唐􀅰 阿尔伯斯的鼓励, 丹􀅰 威尔曼的工作以及美国数学协会的道奇阿尼委员会, 我们将不会完成本书.
最后, 我们永远感激我们的家人所给予的爱与支持.

前 言
第 1 章 斐波那契恒等式 1
1.1 斐波那契数的组合
解释 1
1.2 恒等式 2
1.3 有趣的应用 13
1.4 注记 15
1.5 练习 16
第 2 章 广义斐波那契恒等式
和卢卡斯恒等式 19
2.1 卢卡斯数的组合解释 19
2.2 卢卡斯恒等式 21
2.3 广义斐波那契数 (Gibonacci
数) 的组合解释 26
2.4 广义斐波那契 (Gibonacci)
恒等式 26
2.5 注记 36
2.6 练习 36
第 3 章 线性递推 38
3.1 线性递推的组合解释 38
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