深入理解斯特林数（用Python实现第二类斯特林数算法详解）

什么是第二类斯特林数？

第二类斯特林数记作 S(n, k)，表示将 n 个互不相同的元素划分为 k 个非空、无序子集的方法数。

举个例子：

• S(3, 2) = 3：把 {A, B, C} 分成 2 个非空子集，有以下三种方式：
  { {A}, {B, C} }, { {B}, {A, C} }, { {C}, {A, B} }
• S(4, 2) = 7

递推公式

第二类斯特林数满足如下递推关系：

S(n, k) = k × S(n−1, k) + S(n−1, k−1)

其中边界条件为：

• S(0, 0) = 1
• S(n, 0) = 0 （当 n > 0）
• S(0, k) = 0 （当 k > 0）
• S(n, k) = 0 （当 k > n）

这个公式的直观理解是：

1. 考虑第 n 个元素：
   • 它可以单独成为一个新子集 → 对应 S(n−1, k−1)
   • 也可以加入已有的 k 个子集中的任意一个 → 对应 k × S(n−1, k)

Python 实现方法一：递归（适合理解）

我们可以直接根据递推公式写出递归函数：

def stirling_second_recursive(n, k):    # 边界条件    if n == 0 and k == 0:        return 1    if n == 0 or k == 0 or k > n:        return 0        # 递推公式    return k * stirling_second_recursive(n - 1, k) + \           stirling_second_recursive(n - 1, k - 1)# 测试print(stirling_second_recursive(4, 2))  # 输出: 7

⚠️ 注意：递归方法虽然直观，但效率很低（指数级时间复杂度），只适合小规模计算。

Python 实现方法二：动态规划（推荐）

为了避免重复计算，我们使用动态规划（DP）自底向上构建表格：

def stirling_second_dp(n, k):    # 创建 (n+1) x (k+1) 的 DP 表    dp = [[0] * (k + 1) for _ in range(n + 1)]        # 初始化边界条件    dp[0][0] = 1        for i in range(1, n + 1):        for j in range(1, min(i, k) + 1):            dp[i][j] = j * dp[i - 1][j] + dp[i - 1][j - 1]        return dp[n][k]# 测试print(stirling_second_dp(5, 3))  # 输出: 25

这个方法的时间复杂度是 O(n×k)，空间复杂度也是 O(n×k)，效率高很多。

完整实用函数（带缓存优化）

我们可以结合 functools.lru_cache 实现记忆化递归，兼顾可读性与效率：

from functools import lru_cache@lru_cache(maxsize=None)def stirling_second(n, k):    if n == 0 and k == 0:        return 1    if n == 0 or k == 0 or k > n:        return 0    return k * stirling_second(n - 1, k) + stirling_second(n - 1, k - 1)# 打印一个小型斯特林数表for n in range(1, 6):    row = [stirling_second(n, k) for k in range(1, n + 1)]    print(f"S({n}, k) = {row}")

输出结果：

S(1, k) = [1]S(2, k) = [1, 1]S(3, k) = [1, 3, 1]S(4, k) = [1, 7, 6, 1]S(5, k) = [1, 15, 25, 10, 1]

应用场景

掌握第二类斯特林数后，你可以在以下场景中应用它：

• 计算等价关系的数量
• 解决分组问题（如将学生分组）
• 在机器学习中用于聚类分析的理论基础
• 作为组合数学竞赛题的解题工具

总结

本文详细讲解了斯特林数的概念、递推公式，并提供了三种Python算法实现方式：递归、动态规划和记忆化递归。无论你是算法初学者还是需要复习组合数学知识，希望这篇教程都能帮助你轻松掌握第二类斯特林数的计算方法！

动手试试吧！修改代码中的 n 和 k 值，观察结果变化，加深理解。