不论是在数论中，还是在组合数学中，都有着一些特殊的数列——斐波那契数、欧拉数，斯特林数、卡特兰数，这篇文章，笔者将带领读者去探寻历代数学家是如何从一些简单基本的问题中提炼出这些特殊的数列。

 

  斯特林数：

  斯特林数有两类，分别基于这不同情境的问题，我们首先介绍第二类斯特林数。

  第二类斯特林数基于这样一个问题模型：将含有n个元素的集合分成k个非空子集(用S2(n,k)表示)，有多少张种情况？

  首先我们从几个简单的例子开始，显然，对于任意n>0,k=1,有S2(n,k) = S2(n,n) = 1。

  而当n = 0时呢？S2(0,1) = ?我们用文字描述一下这个式子想要表达的东西，空集分成一个非空集合的情况数，显然是不存在的，即S(0,1) = 0。

  让我们进一步讨论k = 2的情况，对于S2(n,2)，我们可以将其看成将第n个元素加入到前n-1个元素构成集合的一个任意子集中，由于这种选择最终不能形成空集，因此需要排除一种情况，即S2(n,2) = 2^(n-1) - 1.

  分析了k两种特殊取值，我们尝试用分析k=2时的思路进行推广式的分析。考察S2(n,k)，我们可将其看成在n-1个元素的集合上进行一系列操作。对于第n个元素，无非有如下两种情况：

  1.第n个元素单独一组，此时出现S2(n-1，k-1)种情况。

  2.第n个元素不是单独一组，此时出现k*S2(n-1,k)种情况。

  综合起来，得到第二类斯特林数的递推公式S2(n,k) = S2(n-1,k-1) + k*S2(n-1,k)。

  那么这里我们结合刚刚学到的第二类斯特林数，来一道实战的应用。

  Q：当前有n场比赛以及m个桌子，组织每一场比赛需要一些桌子，那么现在请问，完成这n场比赛，有多少种不同的分配桌子的方法？(每个桌子至少要用一次。)

  我们能够看到，在应用第二类斯特林数的时候，S2(n,k)中两个参量分别表示元素数和集合数，在具体的问题中如何恰到好处的找到这两个参量，是用好它的关键。在这个问题当中，我们首先会很自然的考虑将m个桌子看成元素，然后分配到n个集合当中，但是这里不能够忽视的一个重要细节是，对于每个桌子，它是可以在不同的比赛中多次出现的，因此这就与第二类斯特林数给出的模型渐行渐远了，但是不要气馁，我们这里可以反过来思考，如果将n场比赛当做元素呢？即这里给出m个集合，将第i场比赛往第j个集合里填，表示第i场比赛中会用到j，显然这里n个元素仅能够出现一次，这就与第二类斯特林数呼应了起来，即这里有S2(n,m)种情况。应考虑到，第二类斯特林数基于划分的k个集合无序排列，而在这个问题当中，m个桌子是互不相同的，因此最终的结果应该是S2(n,m)*m!。

  下面我们来讨论第一类斯特林数，它基于这样一个问题模型，将含有n个元素分成k个轮换的所有方法数，为了与第一类斯特林数进行区别和比较，我们用S1(n,k)来表示。

  这里需要解释一下什么是轮换，就是元素之间构成了一个环，例如我们用A、B、C做一个轮换，可是是A->B->C->A，还可以是A->C->B->A，这是两种本质不同的轮换，而轮换B->C->A->B显然是与A->B->C->A本质相同的一种轮换。

  我们先从特殊情形入手，我们容易看到，对于m元素，它们能够组成的轮换数是要大于等于它们构成的集合数的，即有S1(n,k) >= S2(n,k),而当某个轮换只有1个或2个元素的时候，这时轮换是与集合相对应的，即有S1(n,n)=S2(n,n)，S1(n,n-1) = S2(n,n-1)。

  我们再从更一般的情况来寻求第一类斯特林数的递推计算公式。当前模拟求解S1(n,k)的过程，其实非常类似在求得第二类斯特林数递推式中的思维过程，我们基于n-1个元素的第一类斯特林数来实现，现在添加第n个元素，无非有如下两种情况：

  1.第n个元素单独形成一个轮换，则有S1(n-1,k-1)种方法。

  2.第n个元素不是单独形成一个轮换，则有(n-1)*S1(n-1,k)种方法。(即将第n个元素插入n-1个元素构成的轮换形成的n-1个间隔中)

  由此我们可以得到第一类斯特林数的递推公式：S1(n,k) = S1(n-1,k-1) + (n-1)*S1(n-1,k)。

  

  

  欧拉数：

  欧拉数基于这样一个简单模型，对于整数1~n的一个排列记作p1p2p3……pn，我们考察n-1个pi和p(i+1)的大小关系，如果其中满足p(i+1) > pi的组数为k(i∈[1,n-1])，则用E(n,k)来表示。

  类似于对斯特林数的分析，我们从几种特殊的情况入手。

  k = 0 ， 对于E(n,0)，显然有E(n,0) = 1.

  k = n , 对于E(n,n) ,通过上文的描述我们可知，p(i+1)与pi至多有n-1组，因此有E(n,n) = 0。

  下面我们探讨如何用递推关系来得到所有的欧拉数。

  模拟计算E(n,k)的过程，我们基于n-1个元素的排列p1p2p3p4p5……pn中添加n，n-1个元素的排列会形成n+1个可以插入整数n的空挡，整数n的位置无非有如下两种情况。

  情况一：整数n插入到第1个空挡，或者插入第j个空挡并且满足p(j-1)<pj，在表明这种操作在原来排列的基础上没有增加满足p(i+1)>pj的组数，因此考虑建立其与C(n-1,k)之间的联系，综合这两种情况，有k+1个满足的地方，因此我们得到(k+1)*E(n-1,k)种情况。

  情况二：整数n插入到第n+1个空挡，或者插入第j个空挡并满足p(j-1)>pj，容易看到，这种操作使得满足p(i+1)>pi的组数在原来的基础上增加了1，因此我们考虑建立其与E(n-1,k-1)之间的关系，结合在情况一中寻求满足情况的方法，这里其实就是用总数减去满足情况一的空挡。(之所以这样做是因为我们可以从E(n,k)值得得到满足情况一的空挡数)。即，满足情况二的空挡数为 n - (k-1) - 1，得到(n-k)E(n-1,k-1)种情况。

  综合两种情况看，我们得到欧拉数的递推公式：E(n,k) = (k+1)E(n-1,k) + (n-k)E(n-1,k-1).

 

  调和数：

  调和数首先基于这样一个有趣的谜题。将n张扑克牌堆在一张桌子上，在满足重力定理的情况下(即扑克的摆放不会使其从桌子上掉下来)，求解这n张能够伸出桌子边缘的最大长度。

 

  为使问题分析起来简便，扑克的摆放中应使扑克边缘和桌子边缘平行，并记每个扑克的长度为2，重量为1.

  对于这个过程的模拟，我们用一个"贪心"的策略，给出n张扑克，我们将桌子视为第n+1张扑克，而前n张扑克的最优搭法应该是这n张扑克的重心刚好落在第n+1扑克的边缘，这使得这n张扑克不会掉落而且将“伸出”最长的距离，我们记dn表示牌堆最上面的一张牌的右侧边缘到从上数第n张牌右侧边缘的距离，那么对于有n张牌的上述谜题，d(n+1)即为谜题的答案。

  为了实现我们的贪心策略，我们借助重心的位置公式——(w1p1+w2p2+w3p3……w3p3)/(w1+w2+w3……wn)，其中wi、pi分别表示第i个物体的重量和位置。

  则有d(n+1) = [(d1+1) + (d2+1)…… + (dn+1)]/n。

  通过化简，我们得到nd(n+1) = n + d1 + d2 +……+dn (n>=0)  ①

  (n-1)d(n) = (n-1) + d1 + d2 +……+d(n-1) (n>=1)               ②

  两式相减，可得d(n+1) = d(n) + 1/n。

 

 

  伯努利数：

  关于伯努利数，本篇文章暂时给出其来源，其递归式及其证明涉及比较高深的数学方法，笔者目前暂时还力不能及。

  伯努利数基于这样一个函数Sm(n) = 0^m + 1^m + 2^m + …… + (n-1)^m = ∑k^m(k∈[0,n-1]),将S1(n)、S2(n)、S3(n)一直到S10(n),得到以下一系列多项式。

 

  伯努利凭借其观察力，找到了这一系列多项式系数与组合数C(m+1,k)之间的联系并给出了通式，记Bi是第i个伯努利数，则Sm(n)可以表示成如下和伯努利数相关联的形式。

  Sm(n) = 1/(m+1) ∑ C(m+1 , k)*Bk*n^(m + 1 - k)  ,其中k[0,m]。这是伯努利根据观察和归纳给出通式，并没有给出证明，而该通式的证明需要扰动法，这里暂且不提。

 

  斐波那契数：

  众所周知，斐波那契数起源于意大利斐波那契的生兔子问题，其在自然界广泛的统治力和其中蕴含的“黄金”让人震惊，接下来我们来就《具体数学》中呈现出的内容，讨论几条关于斐波那契数列的性质。这里我们用F[n]表示第n个斐波那契数。

  卡西尼恒等式：F[n+1]*F[n-1] - F[n]^2 = (-1)^n  (n >= 1) 

  证明：利用归纳法。

  当n = 1时，显然成立。

  假设，当n = k的时候该等式成立，则有F[k+1]*F[k-1] - F[k]^2 = (-1)^k   ①, 即我们需要证当n = k + 1的时候，该等式仍然成立。

  基于斐波那契数列最基本的递推式，F[n] = F[n-1] + F[n-2] ,(n >= 2),我们从n = k + 1时的等式开始入手。

  F[k+2]F[k] - F[k+1]^2     =   (F[k+1]+F[k])F[k] - F[k+1]^2

                                        =    F[k]^2 - F[k+1]^2 + F[k+1]F[k]

                                        =    F[k]^2 - (F[k] + F[k-1])^2 + F[k+1]F[k]

                                        =    (F[k+1] + F[k])F[k] - F[k-1]^2 - 2F[k]F[k-1]

                                        =    F[k]^2 - F[k]F[k-1] - F[k-1]^2

                                        =    F[k]^2 - F[k-1]F[k+1]

                                        =      (-1)^(k+1) 

  证毕。

  基于这个恒等式，我们能够很好的了解卡西尼悖论的机理了。

 

  即对于F[n]*F[n]的棋盘，我们切两个上底是F[n-2]，下底和高均为F[n-1]的直角梯形，切两个直角边分别为F[n-2]、F[n]的直角三角形，然后分别将梯形和直角三角形长为F[n-2]的边重合构成直角三角形，会给人一种形成了一个直角边分别为F[n+1]、F[n-1]的视觉错觉，基于这种错觉人们会觉得拼出了F[n-1]*F[n+1]的矩阵，这便可以解释为什么会少一个小矩形。(从卡西尼恒等式看，也可以多一个，这取决于n的奇偶性。)