天才一秒记住【狂风中文网】地址：https://www.kfzw.net
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的一半，然而阶乘变大还要快得多——很快就能增大到百万量级。
本章未完，请点击下一章继续阅读！若浏览器显示没有新章节了，请尝试点击右上角↗️或右下角↘️的菜单，退出阅读模式即可，谢谢！