Partitions over Permutations：双指数函数幂级数中的组合数学之美

背景

这篇文章源于作者对上周讨论过的一个高斯函数近似公式的深入思考。该近似公式为：

$$ \exp(-z^2) \approx \frac{1 + \cos(\sin(z) + z)}{2} $$

虽然这个近似在实轴（real axis）上表现良好，但在虚轴（imaginary axis）上却存在显著差异。当 $z = iy$ 时，近似公式右侧的增长速度远快于左侧，其行为类似于双重指数函数 $\exp(\exp(y))$。

这一发现促使作者去查阅双重指数函数 $\exp(\exp(y))$ 的幂级数展开式，从而引出了一种有趣的数学结构，将组合数学中的“划分”（Partitions）与“排列”（Permutations）联系起来。

核心内容

双重指数函数的幂级数系数

双重指数函数 $\exp(\exp(y))$ 的幂级数展开具有一个非常特殊的性质。其 $x^n$ 项的系数可以表示为：

$$ \frac{e \cdot B_n}{n!} $$

其中：

• $B_n$ 是第 $n$ 个贝尔数（Bell number）。
• $n!$ 是 $n$ 的阶乘。

组合数学的解释

这个公式背后有着深刻的组合数学含义：

1. 贝尔数 $B_n$：代表将一个包含 $n$ 个有标签（labeled）元素的集合进行划分（partition）的方法总数。
2. 阶乘 $n!$：代表将一个包含 $n$ 个有标签元素的集合进行排列（permute）的方法总数。

因此，双重指数函数幂级数中的第 $n$ 个系数，本质上等于“将 $n$ 个有标签物品进行划分的方法数”与“进行排列的方法数”之比，再乘以常数 $e$。

收敛性分析

随着 $n$ 的增加，集合划分的方法数（贝尔数）增长得非常快，几乎与集合排列的方法数（阶乘）一样快。由于分母和分子的增长速度相当，导致幂级数的收敛速度非常缓慢。

计算实现

在使用 Python 的 SymPy 库时，可以通过 bell 函数计算贝尔数。以下代码展示了如何计算划分与排列的比率：

from sympy import bell, factorial

# 定义比率函数
f = lambda n: bell(n)/factorial(n)

SymPy 返回的结果类型为 sympy.core.numbers.Rational，这意味着结果是精确的有理数。如果需要浮点数结果，可以将其转换为 float 类型。

渐近分析（Asymptotics）

为了理解比率 $B_n / n!$ 的行为，我们可以分析其对数的渐近展开式。

仅考虑随 $n$ 增长的主要项：

• $\log B_n \sim n \log n - n \log \log n$
• $\log n! \sim n \log n - \frac{1}{2} \log n$

由此可得： $$ \log\left(\frac{B_n}{n!}\right) \sim \frac{1}{2} \log n - n \log \log n $$

此外，还存在一个涉及朗伯 W 函数（Lambert W function）的渐近级数： $$ \log\left(\frac{B_n}{n!}\right) \sim \frac{n}{r} - 1 - n \log r $$ 其中 $r = W(n)$。

重要注记

必须强调的是，上述讨论中的“划分”是指对有标签集合的划分。如果是对无标签集合的划分，其数量（Partition numbers）远小于贝尔数，两者不能混淆。

关键要点

• 近似函数的局限性：高斯函数 $\exp(-z^2)$ 的三角函数近似在虚轴上失效，表现为双重指数增长 $\exp(\exp(y))$。
• 系数的组合意义：双重指数函数 $\exp(\exp(y))$ 的幂级数系数 $\frac{e B_n}{n!}$ 是贝尔数（划分数）与阶乘（排列数）的比值乘以 $e$。
• 收敛缓慢的原因：由于集合划分的方法数与排列的方法数增长速度相近，导致该幂级数收敛极慢。
• 精确计算：使用 SymPy 的 bell 函数可以得到精确的有理数结果，避免了浮点误差。
• 渐近行为：比率的对数渐近行为主要由 $-n \log \log n$ 主导，表明随着 $n$ 增大，划分数相对于排列数的比例迅速减小。
• 标签的重要性：贝尔数针对的是有标签集合的划分，这与无标签集合的划分数（Partition numbers）有本质区别。

意义与影响

这篇文章虽然篇幅短小，但它巧妙地连接了分析学（幂级数、渐近分析）与组合数学（贝尔数、排列）。

1. 数学直觉的深化：它揭示了一个非直观的事实：双重指数函数的泰勒系数直接编码了集合划分的组合信息。这种联系展示了数学不同分支之间的深层统一性。
2. 计算复杂性启示：通过指出收敛速度慢，文章暗示了直接通过幂级数计算双重指数函数在数值上的困难，为数值分析提供了理论依据。
3. 渐近工具的展示：引入朗伯 W 函数作为渐近展开的一部分，展示了在处理快速增长的组合数时，特殊函数的重要性。

对于从事算法分析、组合数学或数值计算的读者来说，理解贝尔数与阶乘之间的比率行为，有助于更准确地评估涉及集合划分的算法复杂度或概率模型。