集合上的一个等价关系决定了几何的一个划分,反之亦然,这直观上是不难理解的。但是,如果我要问一个有$n$个元素的有限集合,共有多少种不同的划分呢?以前感觉这也是一个很简单的问题,就没去细想,但前天抽象代数老师提到这是一个有相当难度的题目,于是研究了一下,发现里面大有文章。这里把我的研究过程简单分享一下,读者可以从中看到如何“从零到有”的过程。

以下假设有$n$个元素的有限集合为$\{1,2,\dots,n\}$,记它的划分数为$B(n)$。

前期:暴力计算

$n=3$的情况不难列出:
$$\begin{aligned}&\{\{1,2,3\}\},\{\{1,2\},\{3\}\},\{\{1,3\},\{2\}\},\\
&\{\{2,3\},\{1\}\},\{\{1\},\{2\},\{3\}\}\end{aligned}$$
所以$B(3)=5$。$B(4)$就比较大了,不易列出。基于整数的分拆,我得到了一个复杂的集合划分数计算公式。在此以$S(4)$为例,它有以下的分拆方式:
\begin{aligned}&4=1+1+1+1\\
&4=1+1+2\\
&4=1+3\\
&4=4\\
&4=2+2\end{aligned}
每一种分拆方式代表着$\{1,2,3,4\}$的一种划分方式:它告诉我们分为多少块以及每块有多少个元素。比如4=1+1+1+1表示将$\{1,2,3,4\}$分为4块,每块一个元素,这种方式的可能划分数为
$$\frac{1}{4!}\binom{4}{1}\binom{3}{1}\binom{2}{1}=1$$
除以$4!$是因为每个1的地位都是对等的,不同的顺序只能算一种。同理我们有
\begin{aligned}&4=1+1+2:\quad \frac{1}{2!}\binom{4}{1}\binom{3}{1}=6\\
&4=1+3:\quad \binom{4}{1}=4\\
&4=4:\quad \binom{4}{4}=1\\
&4=2+2:\quad \frac{1}{2!}\binom{4}{2}=3\end{aligned}
所以$B(4)=1+6+4+1+3=15$。用类似的方法可以得出(我是手算的)$B(5)=52,B(6)=203$,完整地列出5和6的所有分拆对于手算来说还是可以接受的。

中期:漫天撒网

现在我们已经得到一部分序列了:5, 15, 52, 203。看上去并无规律,而且直觉告诉我们这数列比指数增长还快。我们把这数列输入OEIS?,找到了该数列(number of ways to partition a set of n labeled elements)

1, 1, 2, 5, 15, 52, 203, 877, 4140, 21147, 115975, 678570, 4213597, 27644437, 190899322, ...

其中在FORMULA那里列出了很多奇特的公式。但由于只有公式没有推导,我也看不懂里边的公式。于是只好另寻他路。在Google中输入“集合的划分数”之类的关键词,可以得到一大批类似的结果。这些内容都给了我一定的帮助,比如,通过引入$S(n,k)$来计算$B(n)$,其中$S(n,k)$表示将$n$个元素的集合划分为$k$块的划分数,根据这定义,显然就有
$$B(n)=\sum_{k=1}^n S(n,k)$$
计算$S(n,k)$则是通过递推的。考虑往$n-1$个元素的集合中添加1个元素,有两种可能:

1、新元素自成1块,$n-1$个元素划分为$k-1$块,此种情况数目为$S(n-1,k-1)$;
2、$n-1$个元素划分为$k$块,新元素放进其中的任一块,此种情况数目为$k S(n-1,k)$

于是有递推公式
$$S(n,k)=S(n-1,k-1)+k S(n-1,k)$$
这大概是最方便编程的计算公式了,用Python代码写出为


def sp(n,m):
  if m>n:
    return 0
  elif m==1 or m==n:
    return 1
  else:
    return sp(n-1,m-1)+m*sp(n-1,m)

def setpart(n):
  return sum([sp(n,m) for m in range(1,n+1)])

print(setpart(7))

但这样的代码计算速度其实是非常慢的。在PyPy上计算$B(30)$已经很勉强了。我昨天计算了好久,想从递推公式中计算$B(n)$的生成函数,但是条件不足,无法得到完整的结果。

中后期:分析计算

在中期的搜索中,得到的大多数文章都是类似的,只介绍了概念和递推,没有更详细的描述,但有一个网站的文章末尾提到这种数叫做“贝尔数”,于是顺藤摸瓜,搜索到了维基百科:
http://zh.wikipedia.org/zh-cn/贝尔数

维基上有很多有价值的资料,也让我知道了通用的记号为$B_n$,而上面引入的$S(n,k)$被叫做“第二类Stirling数”。维基给出了递推公式
$$B_{n+1}=\sum_{k=0}^{n}{{n \choose k}B_k}$$
该公式的组合解释可以直接在维基上看到,在此不赘述。我昨晚计算了好久,都不能由该公式能够带来进一步的信息(是我看错公式了,晕),比如计算生成函数。于是搜索英文维基“Bell Number”,得到比中文维基更详细的结果,但是还是没有推导过程。今天根据英文维基上的提示再计算了一番,得出了生成函数。记
$$f(x)=\sum_{n=0}^{\infty}\frac{B_n}{n!}x^n$$
对它求导,并代入递推公式,交换求和号:
\begin{aligned}f'(x)&=\sum_{n=1}^{\infty}\frac{B_n}{(n-1)!}x^{n-1}=\sum_{n=0}^{\infty}\frac{B_{n+1}}{n!}x^n\\
&=\sum_{n=0}^{\infty}\sum_{k=0}^{n}\frac{1}{n!}{n \choose k}B_k x^n\\
&=\sum_{n=0}^{\infty}\sum_{k=0}^{n}\frac{1}{(n-k)!k!}B_k x^k x^{n-k}\\
&=\sum_{k=0}^{\infty}\sum_{n=k}^{\infty}\frac{1}{(n-k)!k!}B_k x^k x^{n-k}\\
&=\sum_{k=0}^{\infty}\frac{B_k x^k }{k!}\sum_{n=k}^{\infty}\frac{1}{(n-k)!}x^{n-k}\\
&=\sum_{k=0}^{\infty}\frac{B_k x^k }{k!}e^x\\
&=f(x)e^x\\
\end{aligned}
如此一来,算得$f(x)=e^{e^x-c}$,由$f(0)=1$算得$c=1$,于是
$$\sum_{n=0}^{\infty}\frac{B_n}{n!}x^n=f(x)=e^{e^x-1}$$
这是一个简洁漂亮的生成函数,是一个“指数的指数”的函数,由此可见$B_n$的递增之快。根据生成函数,可以推导出$B_n$的一个无穷级数公式,因为
\begin{aligned}e^{e^x}&=\sum_{m=0}^{\infty}\frac{1}{m!}e^{mx}\\
&=\sum_{m=0}^{\infty}\frac{1}{m!}\sum_{n=0}^{\infty}\frac{1}{n!}m^n x^n\\
&=\sum_{n=0}^{\infty}\frac{1}{n!}\sum_{m=0}^{\infty}\frac{1}{m!}m^n x^n
\end{aligned}
通过对比$f(x)$两端,就可以得出
$$B_n=\frac{1}{e}\sum_{m=0}^{\infty}\frac{m^n}{m!}$$
这就是Dobinski公式。

后期?
学习永无止尽,没有后期。与大家共勉~


转载到请包括本文地址:http://spaces.ac.cn/archives/2985/

如果您觉得本文还不错,欢迎点击下面的按钮对博主进行打赏。打赏并非要从中获得收益,而是希望知道科学空间获得了多少读者的真心关注。当然,如果你无视它,也不会影响你的阅读。再次表示欢迎和感谢!