文墨小说

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

05 计数的数（第1页）

05计数的数

banner"

>

从计数问题中自然产生的数很重要，因此它们已经被研究得很深入了。

这里我将介绍二项式系数，以及卡特兰、斐波那契和斯特林所发现的数。

这些数被用于枚举某些自然形成的集合。

不过，还是让我们从一些非常基本的数列开始吧。

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

因为它们在二项式系数里还会出现，让我们花点时间复习一下三角形数。

这一数列的第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-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的一半，然而阶乘变大还要快得多——很快就能增大到百万量级。