天才一秒记住【做客中文网】地址：https://www.zk01.net
由于将一个n元素集合分割为一块或是n块都只有一种方式，因此S（n，1）=1=S（n，n）。
如果我们仿照帕斯卡三角形，也将斯特林数放置在一个三角形中，将得到如图5所示的阵列。
现在我们来解释这个三角形是如何产生的。
这些数也满足了一个递推关系，意味着每个数都联系到阵列中之前的数。
就像二项式系数一样，每个斯特林数都可以由它上方的两个数生成，但这次不再是简单的加和。
另外，我们看到二项式系数生成的算术三角形具有行对称性，这在斯特林三角形中不再成立。
如S（5，2）=15，然而S（5，4）=10。
不过递推规则依然简单。
比如，90这一项等于15+3×25。
这其实揭示了一般情形：要找到三角形中的某个数，取其上方的两个数，将第二个数乘以当前未知数所在的（自身行内的）列数，再加上第一个数。
（不同于算术三角形，这次列数从1开始计。
）用类似的方法，S（5，4）=10=6+4×1。
以上计算规则中只有加粗的部分跟算术三角形的情形不同，但这足以使对斯特林数的研究难度大大超过二项式系数。
举个例子，我们推导出了一个简单的、基于阶乘的显式公式，可以计算所有二项式系数。
类似地，第n个斐波那契数也有一个基于黄金分割比的幂次的通项公式[7]，但是对于斯特林数，还没有这类公式为人所掌握。
这个递推关系并不难解释。
我们的推理类似于二项式系数的递归，给出的递推式也与那里的形式一致，只是相差了一个乘数。
为了将一个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）。
本章未完，请点击下一章继续阅读！若浏览器显示没有新章节了，请尝试点击右上角↗️或右下角↘️的菜单，退出阅读模式即可，谢谢！