天才一秒记住【狂风中文网】地址：https://www.kfzw.net
我们可以取集合的前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，1887——1920）给出的一个优美近似。
分拆具有一种简单的对称性，那就是将n分拆为m个数的方案数等于将n分拆后所得数中最大值恰为m的方法个数。
要想看到这一结论的正确性，一种方法是通过分拆的费勒斯图像（Ferrar'sgraph）——或称杨表[9]（Youngdiagram）。
这个图表并不神秘，无非是将分拆表示成元素逐行减少的点阵。
在图6的例子中，我们把17拆分为5＋4＋4＋2＋1＋1，注意到其从左向右各列也以降序排布。
如果我们绕着左上到右下的对角线翻转整个点阵，我们就得到图示的第二个费勒斯图像，这个图像可以阐释为分拆17=6＋4＋3＋3＋1。
对第二个图像做同样的翻转，又会回到第一个图像。
我们称这两种分拆互为共轭（dual）。
这一对称性表明两种类型的分拆方案数是相等的：一种是m为结果中最大的数的分拆（即顶端行有m个点），它的共轭是一个有m行的分拆，即拆分为m个数。
例如，将17拆分为6个数的方案数，等于将17拆分使得最大数为6的方案数。
图6共轭分拆，17=5＋4＋4＋2＋1＋1=6＋4＋3＋3＋1
本章未完，请点击下一章继续阅读！若浏览器显示没有新章节了，请尝试点击右上角↗️或右下角↘️的菜单，退出阅读模式即可，谢谢！