五二小说网

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

05 计数的数 Numbers That Count（第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个子集。