C++ Stirling 数

有趣的数字是特殊的组合对象，它们触发了许多计数问题。在严格的数学意义上，第一类和第二类**斯特林数**可以看作是两个不同的实体。然而，它们有其可理解的版本。存在这两种类型的数字是因为它们计算不同的组合结构，并且都可以解决分区和排列问题。

第一类斯特林数

第一类斯特林数 c(n,k) 表示将 n 个元素排列成 k 个循环的方式数。换句话说，相同的数字表示我们可以排列 n 个对象的方式数，使得恰好有 k 个排列循环。

第二类斯特林数

将 n 个元素分成 k 个非空、无序集合的方式数称为第二类斯特林数，表示为 **S(n,k)**。当事物被分成组，并且分组内对象的顺序不重要时，这些数字就会出现。

递归公式

1. 第一类斯特林数 c(n,k) 通过使用此递归关系，即：

带有其基本情况

2. 第二类斯特林数 S(n,k) 通过使用此递归关系，即：

带有其基本情况

斯特林数的应用

C++ 中斯特林数的几个应用如下：

• 斯特林数用于分区、排列和组合问题。
• 第一类数字可以用于促进带循环排列的分析。
• 当对事物进行分组或子集化时，第二类斯特林数通常被使用。

第一类示例代码

让我们以一个例子来说明 C++ 中的斯特林数。

输出

 
Stirling number of the first kind c(5, 2) is: 50   

说明

• **动态规划表：** C(i,j) 中的 C 值存储在二维表 C[i][j] 中。
• **基本情况：** 表格用 C(0,0) = 1 初始化，然后使用递归关系填充值。
• **复杂度：** 对于小到中等范围的 n 和 k，此实现的时间复杂度为 O(n⋅k)，因此效率很高。

第二类示例代码

让我们以一个例子来说明 C++ 中的斯特林数。

输出

 
Stirling number of the second kind S(5, 3) is: 25   

说明

• **动态规划表：** S(i,j) 中的 S 值存储在名为 S[i][j] 的二维表中。
• **基本情况：** 表格用 S(0,0) = 1 初始化，未来值使用递归关系填充。
• **复杂度：** 对于小到中等范围的 n 和 k，此实现的时间复杂度为 O(n⋅k)，这使其效率很高。

结论

总之，**斯特林数**（第一类和第二类）在解决关于排列、分区和循环的组合问题时经常出现。斯特林数有两种类型：一种可以将元素排列成循环，另一种可以将事物分成非空子集。在计算机科学和数学的各种应用中，使用递归公式和动态规划来计算值以实现高效实现，如 C++ 中的示例所示。组合枚举、概率和图论以及许多其他数学研究领域都需要斯特林数，因为它们构成了离散数学。