Bell数的递推公式的详细过程

Bell数的递推公式可以通过斯特林数的递推公式推导得出。

首先，我们需要定义一个函数$S(n,k)$表示从$n$个不同元素中选出$k$个元素并将它们分成不同的非空集合的方案数。根据斯特林数的定义，$S(n,k)$可以表示为：

$$S(n,k) = kS(n-1,k) + S(n-1,k-1)$$

其中，第一项表示将第$n$个元素加入到已有的$k$个非空集合中，第二项表示将第$n$个元素单独分成一个新的非空集合。

接下来，我们将$S(n,k)$拆分成两部分，即：

$$S(n,k) = kS(n-1,k) + S(n-1,k-1)$$

$$= k(S(n-1,k-1) + S(n-2,k-1)) + S(n-1,k-1)$$

$$= kS(n-1,k-1) + (k-1)S(n-2,k-1)$$

现在，我们可以将Bell数定义为：

$$B_n = \sum_{k=1}^{n} S(n,k)$$

将$S(n,k)$的递推公式代入上式中，得到：

$$B_n = \sum_{k=1}^{n} (kS(n-1,k-1) + (k-1)S(n-2,k-1))$$

$$= \sum_{k=1}^{n} kS(n-1,k-1) + \sum_{k=1}^{n} (k-1)S(n-2,k-1)$$

$$= \sum_{k=0}^{n-1} (k+1)S(n-1,k) + \sum_{k=0}^{n-2} (k+1)S(n-2,k)$$

注意到$k+1$可以表示为$(k+1)!/k!$，故上式可以进一步化简为：

$$B_n = \sum_{k=0}^{n-1} \frac{(k+1)!}{k!}S(n-1,k) + \sum_{k=0}^{n-2} \frac{(k+1)!}{k!}S(n-2,k)$$

$$= \sum_{k=0}^{n-1} (k+1)S(n-1,k) + \sum_{k=0}^{n-2} (k+1)S(n-2,k)$$

$$= (n-1)S(n-1,n-2) + \sum_{k=0}^{n-2} (k+1)(S(n-1,k) + S(n-2,k))$$

$$= (n-1)S(n-1,n-2) + \sum_{k=0}^{n-2} (k+1)B_k$$

这就是Bell数的递推公式。从上式可以看出，Bell数的计算需要用到斯特林数，因此，计算Bell数的时间复杂度为$O(n^2)$