使用具体数学中提到的"特殊号码"在哪里？

Question

我在网上浏览了具体数学的内容.我至少听过提到的大部分功能和技巧,但有一个关于特殊号码的部分.这些数字包括斯特林数,欧拉数,调和数等.现在我从未遇到任何这些奇怪的数字.他们如何帮助解决计算问题？它们通常在哪里使用？

Answer 1

谐波数几乎出现在任何地方!音乐和声,Quicksort的分析......斯特林数(第一种和第二种)出现在各种组合和分区问题中.欧拉数也出现在几个地方,最值得注意的是多项对数的排列和系数.

Answer 2

这些数字中的大多数都计算某些类型的离散结构（例如，斯特林数计算子集和循环）。这样的结构，以及因此的这些序列，隐含地出现在算法分析中。

OEIS有一个广泛的列表，列出了《具体数学》中出现的几乎所有序列。该列表的简短摘要：

• 哥伦布数列
• 二项式系数
• 会议号码
• 斯特林数
• 欧拉数
• 超阶乘
• 吉诺基数

您可以浏览各个序列的 OEIS 页面，以获取有关这些序列“属性”的详细信息（尽管不完全是应用程序，如果这是您最感兴趣的内容）。

另外，如果您想了解这些序列在算法分析中的实际用途，请翻阅 Knuth 的《计算机编程艺术》索引，您会发现许多对这些序列“应用”的参考。John D. Cook 已经提到过斐波那契数和调和数的应用；这里还有一些例子：

斯特林循环数出现在对查找数组最大元素的标准算法（TAOCP Sec. 1.2.10）的分析中：查找最大值时当前最大值必须更新多少次？事实证明，在元素k数组中找到最大值时，最大值需要更新次的概率为。由此我们可以得出，平均而言，大约需要更新。np[n][k] = StirlingCycle[n, k+1]/n!Log(n)

Genocchi 数与计算“薄” BDD的数量有关（TAOCP 7.1.4 练习 174）。