计算科学 - 数值计算第二类斯特林数的有效方法？ - 吾爱随笔录

数值计算第二类斯特林数的有效方法？

计算科学算法特殊功能

2021-12-03 18:30:22

有没有一种有效的方法来数值计算第二类斯特林数？

一个近似（不精确）的方法就足够了。类似于阶乘和伽马函数之间的联系的东西对我有用。

我用谷歌搜索了一下，没有发现任何有用的东西。

2个回答

您可以使用以下递归关系

$\mathop{S}\nolimits\left(n,k\right)=k\mathop{S}\nolimits\left(n-1,k\right)+\mathop{S}\nolimits\!\left(n-1,k-1\right)$

见 DLMF 方程 26.8.E22

并建立（三角形）表。

接受的答案需要 $O(kn)$ 乘法和加法。还有一种方法使用 $O(k\log n)$ 加法、乘法和除法，使用下面的恒等式。

S (n, k) = \frac{1}{k!} \sum_{j = 0}^{k} (- 1)^{j} (\binom{k}{j}) (k - j)^{n}

$S(n,k)=\frac1{k!}\sum_{j=0}^k(-1)^j\binom{k}j(k-j)^n$

我们可以使用DLMF 方程 26.3.E6作为递推关系，以大大减少计算二项式系数所需的计算量。

(\binom{m}{n}) = \frac{m - n + 1}{n} (\binom{m}{n - 1})

$\binom{m}{n} = \frac{m-n+1}{n}\binom{m}{n-1}$

伪代码：

accum ← 0
k_choose_j ← 1
for j = 0,1,...,k-1:
  accum ← accum + (-1)^j * k_choose_j * (k - j)^n
  k_choose_j ← k_choose_j * (k-j) / (j+1)
return accum / factorial(k)

请注意，在上面的伪代码中，我们k_choose_j在每次迭代结束时更新，所以我们需要在上面的关系中j + 1替换n。

其它你可能感兴趣的问题

上一篇根据电荷位置计算电场的工具？下一篇不可微的全局优化问题