千米小说网

05 计数的数 Numbers That Count（第1页）

05计数的数t

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

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

因为它们在二项式系数里还会出现，让我们花点时间复习一下三角形数（triangularnumbers）。这一数列的第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]（geometricseries）。算术数列中，相邻两项相差一个公差（ondifference），即我们的b。换句话说，从一项到下一项，我们要加上b。几何数列中，我们还是取一个任意数a为首项，但是通过乘一个固定的数——称为公比（onratio），来得到下一项。这个比值记为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!=3628800。阶乘由感叹号来代表，恰恰提醒着我们那令人惊叹的增长速度!

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

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

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

，r）=-1，r）+-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边的正多边形被互不相交的对角线分成三角形的方法个数。沿着这一思路，卡特兰数还有其他解读方法。正如二项式系数，也有公式联系了卡特兰数和更小的卡特兰数，这使对它们的计算变得很简便。

斐波那契数列

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

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。我们将这种用先行项来定义当前项的公式叫作递归（re）或递推关系（recerelation）。

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

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