五二小说网

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

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

这个递推关系并不难解释。

我们的推理类似于二项式系数的递归，给出的递推式也与那里的形式一致，只是相差了一个乘数。

为了将一个n元素集合分成r个非空子块，我们可以采取两种不同的方法。

我们可以取集合的前n-1个元素，并将其分成r-1个非空块，共有S（n-1，r-1）种方法，最后一个元素将构成第r个块。

或者，我们可以将集合的前n-1个元素分成r个非空块，这有S（n-1，r）种方法，接下来再决定将最后一个元素放进r个块的哪一个，这就需要用r乘以目前的方法数。

因此有S（n，r）=S（n-1，r-1）+rS（n-1，r），这里n=2，3，….

用这个递归公式，我们就可以基于上一行计算每一行斯特林三角形的值。

如，设n=7和r=5我们得到：

S（7，5）=S（6，4）+5S（6，5）=65+5×15=65+75=140.

可以用定义直接计算S（n，2）和S（n，n-1）。

将一个n元素集合分割成两个子集，这一过程可以由一个长度为n的二进制字符串来描述，其中1表示相应位置的元素在第一个子集中，而0则表示该元素属于第二个子集（类似于我们证明n元素集合的子集个数是2n）。

于是，有2n个这样的有序子集对。

但是因为分割与块的次序无关，我们将这个数目除以2，便可得到将n元素集合分成两个子集的方法个数，即2n-1。

最后，还需要从中减掉1，去除掉其中一个子集为空的情况。

因此，S（n，2）=2n-1-1。

对照图5，你可以检查看看，这个公式给出了右上到左下方向第二对角线上的数，即1，3，7，15，31，63，…。

算术三角形中任意一行的和给出了对应2的幂次——一个集合的子集数量。

类似地，斯特林三角形的第n行的和给出的是将n个物体分成任意个数子块的方法总数，这被称作第n个贝尔数（Bellnumber）。

分拆数

另一方面，如果待分割集合中的n个物体是一模一样、无法区分开的，将整个集合分拆为子块的方法数就变得小得多了。

这称为第n个分拆数[8]（partitionnumber）。

每一个特定的分拆对应于将n写成一些不考虑次序的正整数的和。

例如，1+1+1+1+1是5的一个分拆，还有6种其他分拆，因为我们还可以将5表示成1+1+1+2，1+2+2，1+1+3，2+3，1+4，或直接就是5。

因此第5个分拆数为7（对比第5个贝尔数，后者可由斯特林三角形计算，即1+15+25+10+1=52）。

没有简单的精确公式可以计算第n个分拆数，但有一个复杂的公式。

该公式基于印度天才数学家斯里尼瓦瑟·拉马努金（SrinivasaRamanujan）给出的一个优美近似。

分拆具有一种简单的对称性，那就是将n分拆为m个数的方案数等于将n分拆后所得数中最大值恰为m的方法个数。

要想看到这一结论的正确性，一种方法是通过分拆的费勒斯图像（Ferrar’sgraph）——或称杨表[9]（Youngdiagram）。

这个图表并不神秘，无非是将分拆表示成元素逐行减少的点阵。

在图6的例子中，我们把17拆分为5+4+4+2+1+1。

注意到从左向右各列也以降序排布。

如果我们绕着左上到右下的对角线翻转整个点阵，我们就得到图示的第二个费勒斯图像，这个图像可以阐释为分拆17=6+4+3+3+1。

对第二个图像做同样的翻转，又会回到第一个图像。

我们称这两种分拆互为共轭（dual）。