从计数问题中自然产生的数很重要，因此它们已经被研究得很深入了。这里我将介绍二项式系数，以及卡特兰、斐波那契和斯特林所发现的数。这些数被用于枚举某些自然形成的集合。不过，还是让我们从一些非常基本的数列开始吧。

三角形数、算术数列和几何数列

因为它们在二项式系数里还会出现，让我们花点时间复习一下三角形数(triangular numbers)。这一数列的第n项，记为tn，定义为前n个正整数的和。它的值依赖于n，可以用下面这个技巧来计算。我们将刚刚提到的和的形式写作tn，接着以倒序再写一遍：

tn=1+2+3+…+(n-2)+(n-1)+n.

tn=n+(n-1)+(n-2)+…+3+2+1.

例如，取a=1和b=2，则前n个奇数之和为n+n(n-1)=n+n2-n=n2，即n的平方。

如果把加法操作替换为乘法，算术数列就变成了几何数列[1](geometric series)。算术数列中，相邻两项相差一个公差(common difference)，即我们的b。换句话说，从一项到下一项，我们要加上b。几何数列中，我们还是取一个任意数a为首项，但是通过乘一个固定的数——称为公比(common ratio)，来得到下一项。这个比值记为r。也就是说，典型的几何数列具有a，ar，ar2，…的形式，其第n项为arn-1。就像算术数列一样，几何数列的前n项和也有一个公式[2]：

要想看出这一公式的正确性，最快的方法是将等式两边同乘(r-1)并将括号展开。等式左端我们有：

(ar+ar2+ar3+…+arn)-(a+ar+ar2+…+arn-1).

这一表达式可以裂项相消(telescope)，即一个括号中，几乎每一项都可以与另一括号中的一项互相消去，仅剩下arn-a=a(rn-1)。由此可见我们的求和公式是正确的。举个例子，设a=1，r=2，我们得到2的各次幂之和：

1+2+4+…+2n-1=2n-1.

第3章中欧几里得通过梅森素数导出了偶完全数，这里的公式恰好可以让你验证他的方法。

阶乘、排列和二项式系数

我们已经看到，第n个三角形数来自于对1到n之间所有的数求和。这个过程中，倘若将加法换成乘法，我们就得到了所谓的阶乘。这一概念已经在第2章中出现过。

阶乘常常现身于计数和概率问题中，比如打扑克时抽到特定牌的概率。因而它有单独的记号：n的阶乘记为n!=n×(n-1)×…×2×1。随着n的增长，三角形数的大小增长得相当快，增长率差不多能达到n2的一半，然而阶乘变大还要快得多——很快就能增大到百万量级。比如10! = 3 628 800。阶乘由感叹号来代表，恰恰提醒着我们那令人惊叹的增长速度!

在关于计数的问题——或称为枚举(enumerations)问题中，最特殊的一类数便是二项式系数(binomial coefficients)。之所以叫这个名字，是因为它们是将二项式(1+x)n展开后x的各阶幂次前的系数。二项式系数C(n，r)代表了我们从n个元素中挑选出r个元素一共有多少种不同的方法。例如，C(4，2)=6，因为从4个元素中取一对有6种方法(不在乎这两者的次序)。再具体些，假设我们有4位儿童：A，B，C和D。那么有6种方法从中选出1对：AB，AC，AD，BC，BD和CD。

这个用阶乘计算二项式系数的公式确实提供了一种简便的代数方法，使我们能够证明这些系数的许多特殊性质。然而，如果我们用第二种方法来导出这些整数，这些性质的演化会更清楚。这种方法基于算术三角形[3](Arithmetic triangle)(如图2)，又称为帕斯卡三角形(Pascal’s triangle)，以纪念17世纪法国数学家和哲学家布莱士·帕斯卡(Blaise Pascal)。算术三角形在过去的1000年里被波斯、印度和中国数学家各自发现。它出现在1303年朱世杰[4]所著《四元玉鉴》的封面上。

算术三角形的结构能够给出正确的答案，这一点不难理解。每一行都由上一行所产生。我们可以轻松看出前三行是正确的：例如，第三行中央的2告诉我们从一对人当中选出一位总共有两种方法。顶端的1表明从空集中选出0个元素就只有一种方法。实际上，从任意集合中选出0个元素的方法都是一种，这就是为什么每行都从1开始。我们重点看刚才的例子——共有21 = 15+6种方法从7人中选出5人。这21种选法自然地分成两类。第一类，有15种方法从前6人中选出4人，我们可以再加上第七位凑成5人组。或者如果我们不选第七位，则要从前6人中一次选出5人，共有6种方法。这个例子告诉我们一行是如何生成下一行的：每个元素都是上面两数之和，按照这一模式从上到下建立起整个三角形。这个规则可用符号表示成以下形式：

C(n，r) =C(n-1，r)+C(n-1，r-1) .

算术三角形蕴含着丰富的规律。比如：将每行的数分别相加可以得到倍增数列1， 2， 4， 8， 16，32，…，即2的各次幂。以1， 8， 28， 56，…这行为例，我们是在将从8个元素中选出0个、1个、2个、3个……元素的方法个数相加，最后得到的是从8个元素中一次选取任意个数的元素共有多少种方法。这一数字为28，因为一般一个有n个元素的集合拥有2n个子集。

上面这一事实也可以直接推出，原因是一个n个元素集合的任意一个子集可以使用长度为n的二进制字符串来识别。方法如下：我们考虑一个集合，比如{a1，a2，…，an}，则一个长度为n的二进制字符串定义了它的一个子集，因为字符串中的每个1表示相应的元素ai存在于我们的子集中。例如，假设n=4，字符串0111和0000分别代表{a2，a3，a4}和空集。由于二进制字符串的每个位置都有两种取值选择，因此共有2n个这样的字符串，一个n元素集合便含有2n个子集。

卡特兰数

这种数有种最简单的图形表达，是用n段上斜线段和n段下斜线段能画出多少组不同的“山脉”(见图3)。

每种不同的山脉构型都对应一组有意义的括号，因此将n对括号有意义地排列起来的方法个数，恰好是第n个卡特兰数。例如，(())()和((()))是有意义的括号方法，但())(()不是：有意义是指从左向右数时，左括号的个数从不小于右括号的个数。这对应于山脉始终位于地面上方这一自然条件。比方说，图3中第一个和最后一个山脉的构型分别对应于()(())和()()()这两种括号排列。

第n个卡特兰数还代表将n+2边的正多边形被互不相交的对角线分成三角形的方法个数。沿着这一思路，卡特兰数还有其他解读方法。正如二项式系数，也有公式联系了卡特兰数和更小的卡特兰数，这使对它们的计算变得很简便。

斐波那契数列

恐怕没有第二个数列像斐波那契数列(Fibonacci sequence)那样使普罗大众着迷了，它是如下的数列：

1， 1， 2， 3， 5， 8， 13， 21， 34， 55， 89，144， 233， 377， 610，…

在起始的两个数之后，每个数都是其之前两数之和。在这一点上，二项式系数与其有相似之处，因为那里每一项也是之前两数之和。但是斐波那契数列的组成方式更简单：

fn=fn-1+fn-2

这里fn表示第n个斐波那契数，并且我们规定f1=f2=1。我们将这种用先行项来定义当前项的公式叫作递归(recursion)或递推关系(recurrence relation)。

这一数列是从哪里来的呢？它最先是由比萨的莱昂纳多(Leonardo of Pisa)——更有名的称呼是斐波那契——在他著名的兔子问题中引入的。一只雌兔出生两个月后达到生育年龄，并在这之后的每个月生下一只雌兔。那么每个月初雌兔的总数由斐波那契数列给出。第一个和第二个月初当然只有一只兔子。第三个月初雌兔生下一只雌兔，因而我们有2只雌兔。到了下个月，它又生下一只，于是共有3只雌兔。再下个月，雌兔总数达到5只，因为雌兔和它的大女儿都能够生育。一般地，在这之后的每个月初，新生雌兔的数量等于两个月前雌兔的总数，因为此刻只有它们处于生育年龄。于是，每月初雌兔总数等于上月雌兔的数量与上上个月雌兔数量之和(斐波那契的雌兔是永生的)。因而斐波那契数列的产生方式完全符合他的雌兔繁殖的方式。

尽管真实世界的兔子并不是以这种异想天开的方式来繁殖的，斐波那契数列依然换着面孔出现在自然界中，包括植物的生长。我们对这一现象的原因已经有了透彻的理解，这与该数列的更微妙的性质有关，即黄金分割比(Golden Ratio)。我们这就来谈谈它。

最简单的数列类型便是我们在本章第一部分介绍的算术和几何数列。虽然斐波那契数列并非它们中的一种，它却与后者有惊人的联系。当计算斐波那契数列邻项之差并将它们也排成一列时，我们得到0， 1， 1， 2， 3， 5， 8， 13，…，于是又得到了一组斐波那契数列，只是这次是从0开始的!其中的原因正是这个数列形成的方式：两个相邻斐波那契数之差恰好等于它俩之前的那个数，(想要代数地证明这一点，可以将上面的斐波那契递推公式两边同时减去fn-1)所以它不是算术数列。它也不是几何数列，因为相邻两项斐波那契数之比并不是常数。但我们观察邻项之比的时候，它似乎在一个极限值附近稳定下来，而且这个比值很快就趋于稳定了。让我们将每个斐波那契数除以它前一个数：

这个逐渐显露的神秘的数，1.6180…，到底是什么呢？这个数τ被称为黄金分割比，它也会出现在一些几何问题中，而这些问题看起来跟斐波那契的兔子相差十万八千里。例如，τ是正五边形的对角线与边长之比(如图4)。任意两条对角线的交点将它们各自分成两段，这两段长度之比也是τ∶1。一对相交的边和一对相交的对角线构成一个菱形(一个“正方的”平行四边形)，即如图4中的ABCD。所有对角线的交点又组成了一个小的倒立的五边形。

另一种获得τ的值的方法是通过它的连分数。连分数能将τ和斐波那契数列直接联系起来，我们将在第7章中探索这一方法。

不断数下去，斐波那契数列看起来就像一个几何数列，它的公比是黄金分割比。正是由于这一性质和它简单的构成规则，斐波那契数列无处不在。

斯特林数和贝尔数

像二项式系数一样，斯特林数[6](Stirling numbers)经常在计数问题中出现。它依赖于两个变量，n和r。斯特林数S(n，r)是将一个有n个元素的集合分割成r个子块的方法的个数，每一块都非空，且无关于块的次序和块内部元素的顺序。(严格地说这些称为第二类斯特林数。第一类斯特林数与此相关，但代表了非常不同的东西，即将n个物体排列成r个环的方法总数。)例如，含有元素a，b，c的集合只能以一种方式分成三块：{a}，{b}，{c}；或是以三种方式分成两块，分别是{a，b}，{c}和{a}，{b，c}和{a，c}，{b}；或是以唯一一种方式分成一块：{a，b，c}。因此S(3，1) = 1，S(3，2) = 3以及S(3，3) = 1。由于将一个n元素集合分割为一块或是n块都只有一种方式，因此S(n，1) = 1 = S(n，n)。如果我们仿照帕斯卡三角形，也将斯特林数放置在一个三角形中，将得到如图5所示的阵列。现在我们来解释这个三角形是如何产生的。

这些数也满足了一个递推关系，意味着每个数都联系到阵列中之前的数。就像二项式系数一样，每个斯特林数都可以由它上方的两个数生成，但这次不再是简单的加和。另外，我们看到二项式系数生成的算术三角形具有行对称性，这在斯特林三角形中不再成立。如S(5，2) = 15，然而S(5，4) = 10。不过递推规则依然简单。比如，90这一项等于15+3×25。这其实揭示了一般情形：要找到三角形中的某个数，取其上方的两个数，将第二个数乘以当前未知数所在的(自身行内的)列数，再加上第一个数。(不同于算术三角形，这次列数从1开始计。)用类似的方法，S(5，4) = 10 = 6+4×1。以上计算规则中只有加粗的部分跟算术三角形的情形不同，但这足以使对斯特林数的研究难度大大超过二项式系数。举个例子，我们推导出了一个简单的、基于阶乘的显式公式，可以计算所有二项式系数。类似地，第n个斐波那契数也有一个基于黄金分割比的幂次的通项公式[7]，但是对于斯特林数，还没有这类公式为人所掌握。

这个递推关系并不难解释。我们的推理类似于二项式系数的递归，给出的递推式也与那里的形式一致，只是相差了一个乘数。为了将一个n元素集合分成r个非空子块，我们可以采取两种不同的方法。我们可以取集合的前n-1个元素，并将其分成r-1个非空块，共有S(n-1，r-1)种方法，最后一个元素将构成第r个块。或者，我们可以将集合的前n-1个元素分成r个非空块，这有S(n-1，r)种方法，接下来再决定将最后一个元素放进r个块的哪一个，这就需要用r乘以目前的方法数。因此有S(n，r) =S(n-1，r-1)+rS(n-1，r)，这里n= 2，3，… .

用这个递归公式，我们就可以基于上一行计算每一行斯特林三角形的值。如，设n = 7和r = 5我们得到：

S(7， 5) = S(6， 4)+5S(6， 5) = 65+5×15 = 65+75 = 140 .

可以用定义直接计算S(n， 2)和S(n， n-1)。将一个n元素集合分割成两个子集，这一过程可以由一个长度为n的二进制字符串来描述，其中1表示相应位置的元素在第一个子集中，而0则表示该元素属于第二个子集(类似于我们证明n元素集合的子集个数是2n)。于是，有2n个这样的有序子集对。但是因为分割与块的次序无关，我们将这个数目除以2，便可得到将n元素集合分成两个子集的方法个数，即2n-1。最后，还需要从中减掉1，去除掉其中一个子集为空的情况。因此，S(n， 2) = 2n-1-1。对照图5，你可以检查看看，这个公式给出了右上到左下方向第二对角线上的数，即1， 3， 7， 15，31， 63，…。

算术三角形中任意一行的和给出了对应2的幂次——一个集合的子集数量。类似地，斯特林三角形的第n行的和给出的是将n个物体分成任意个数子块的方法总数，这被称作第n个贝尔数(Bell number)。分拆数

另一方面，如果待分割集合中的n个物体是一模一样、无法区分开的，将整个集合分拆为子块的方法数就变得小得多了。这称为第n个分拆数[8](partition number)。每一个特定的分拆对应于将n写成一些不考虑次序的正整数的和。例如，1+1+1+1+1是5的一个分拆，还有6种其他分拆，因为我们还可以将5表示成1+1+1+2， 1+2+2，1+1+3， 2+3， 1+4，或直接就是5。因此第5个分拆数为7(对比第5个贝尔数，后者可由斯特林三角形计算，即1+15+25+10+1 = 52)。没有简单的精确公式可以计算第n个分拆数，但有一个复杂的公式。该公式基于印度天才数学家斯里尼瓦瑟·拉马努金(Srinivasa Ramanujan)给出的一个优美近似。

分拆具有一种简单的对称性，那就是将n分拆为m个数的方案数等于将n分拆后所得数中最大值恰为m的方法个数。要想看到这一结论的正确性，一种方法是通过分拆的费勒斯图像(Ferrar’s graph)——或称杨表[9](Young diagram)。这个图表并不神秘，无非是将分拆表示成元素逐行减少的点阵。

在图6的例子中，我们把17拆分为5+4+4+2+1+1。注意到从左向右各列也以降序排布。如果我们绕着左上到右下的对角线翻转整个点阵，我们就得到图示的第二个费勒斯图像，这个图像可以阐释为分拆17 = 6+4+3+3+1。对第二个图像做同样的翻转，又会回到第一个图像。我们称这两种分拆互为共轭(dual)。这一对称性表明两种类型的分拆方案数是相等的：一种是m为结果中最大的数的分拆(即顶端行有m个点)，它的共轭是一个有m行的分拆，即拆分为m个数。例如，将17拆分为6个数的方案数，等于将17拆分使得最大数为6的方案数。

冰雹数

尽管不是一种计数工具，冰雹数(hailstone numbers)仍然耐人寻味，因为它也是被递推定义的，不过这个数列更像我们在第3章中遇到的真因数和数列。以下问题有好几个名字，考拉兹算法(Collatz algorithm)、叙拉古问题(Syracuse problem)，或者有时就叫3n+1问题[10]。它基于一个简单的观察，即从任意数n开始，经过以下步骤似乎最终总是得到1：若n是偶数，将其除以2；若n是奇数，用3n+1代替它。例如，从n = 7开始，我们按照这些规则得到以下数列：

7→22→11→34→17→52→26→13→40

→20→10→5→16→8→4→2→1.

于是这一猜想对n = 7成立。实际上该猜想已经被证实对于直到一万亿以上的某个数都是正确的[11]。但是如果你乱动了规则，事情就大不一样了。比如，用3n-1代替3n+1会导致一个循环：

7→20→10→5→14→7→….

考拉兹算法产生的数列类似于冰雹，在很长一段时间内它们的取值大起大落，但最终似乎总会降落到地面。在前1000个正整数中，有超过350个数上升到最大高度9232，而后则迅速跌落到1。一旦你遇到2的幂次，就会最终得到1，因为之后这些数不会经历任何爬升，只能一路衰减到底。

所有这些奇妙的特性都可以在基于冰雹数列的图像中被发现，这让人不禁联想起数学和物理中出现的其他混沌现象。在搜索引擎中输入“冰雹数”，你会找到一大堆信息，这些信息往往看上去奇妙异常，有时候是猜想性质的，但通常不能给出一个确定的结论。

[1]　即等比数列。

[2]　该公式中r≠1。

[3]　即杨辉三角形。

[4]　朱世杰，字汉卿，号松庭，元代数学家和教育家。

[5]　尤金·查理·卡特兰(Eugène Charles Catalan)，法国和比利时数学家。

[6]　詹姆斯·斯特林(James Stirling)，苏格兰数学家。埃里克·坦普尔·贝尔(Eric Temple Bell)，英国数学家、科幻小说家。

[7]　如果可以将数列{an}的第n项用一个含参数n的式子表示出来，则称该式为该数列的通项公式。

[8]　又称拆分数或分割数。

[9]　又称杨氏矩阵。

[10]　又名考拉兹猜想、叙拉古猜想、3n+1猜想、奇偶归一猜想、冰雹猜想、角谷猜想、哈塞猜想、乌拉姆猜想。

[11]　世界各地的数学爱好者们利用分布式计算，不断地提高这个极限。已知的猜想成立的最大整数似乎已超过1020(一亿亿的一百倍)，而仍未找到反例。有兴趣的读者可以参考以下网站：https://boinc.thesonntags.com/collatz/， http://www.ericr.nl/wondrous/。