五二小说网

手机浏览器扫描二维码访问

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

卡特兰数

这种数有种最简单的图形表达，是用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）。

我们这就来谈谈它。

最简单的数列类型便是我们在本章第一部分介绍的算术和几何数列。

虽然斐波那契数列并非它们中的一种，它却与后者有惊人的联系。

当计算斐波那契数列邻项之差并将它们也排成一列时，我们得到0，1，1，2，3，5，8，13，…，于是又得到了一组斐波那契数列，只是这次是从0开始的!其中的原因正是这个数列形成的方式：两个相邻斐波那契数之差恰好等于它俩之前的那个数，（想要代数地证明这一点，可以将上面的斐波那契递推公式两边同时减去fn-1）所以它不是算术数列。