Partitions over permutationsPartitions over permutations

我进一步思考了关于高斯函数的余弦近似

exp(−z²) ≈ (1 + cos(sin(z) + z))/2

这是我上周曾写过的内容。上述两个表达式在实轴上非常接近，但在虚轴上却相差甚远。

如果 z = iy，右侧的增长速度远快于左侧，其表现类似于 exp(exp(y))。

这促使我去查阅了双指数函数 exp(exp(y)) 的幂级数。这是一个非常有趣的级数，因为其 x^n 的系数为

e Bn / n!

其中 Bn 是第 n 个贝尔数，等于将包含 n 个带标签元素的集合进行划分的方法数 [1]。当然，n! 是对 n 个带标签元素的集合进行排列的方法数。因此，exp(exp(y)) 幂级数的第 n 个系数，就是 n 个带标签元素的划分数与排列数之比，再乘以 e。

随着 n 的增加，划分 n 个元素集合的方法数增长得非常快，几乎与排列数的增长速度相当，因此双指数函数的级数收敛极其缓慢。

计算

SymPy 提供了一个用于计算贝尔数的 bell 函数，因此你可以通过以下方式计算划分数与排列数的比值。

from sympy import bell, factorial
f = lambda n: bell(n)/factorial(n)

这会返回一个 sympy.core.numbers.Rational 类型的数值，因此结果是精确的。为了方便起见，你可以将其转换为浮点数。

渐近分析

如果我们仅考察 log Bn 和 log n! 的渐近级数中随 n 增长的项，可以得到

log Bn ~ n log n − n log log n; log n! ~ n log n − ½ log n

因此

log( Bn / n! ) ~ ½ log n − n log log n

log( Bn / n! ) 还有一个包含 Lambert W 函数的渐近级数：

log( Bn / n! ) ~ n/r − 1 − n log r

其中 r = W(n)。

相关文章

[1] 重要的是这些元素是带标签的。划分数（Partition numbers）是指对无标签集合进行划分的方法数。划分数要比贝尔数小得多。