论文部分内容阅读
Bernoulli数、Stirling数、Euler数在组合数学、函数论、理论物理及近似计算等方面均有广泛的应用。在数字图像中,可以利用欧拉数来描述物体结构,保持图像特征不变;在离散数学中,这些特殊数具有组合含义;在气象学、组合优化、随机图、Ramsey理论等方面的也可用这些特殊数来计数。著名计算机科学家、美国斯坦福大学教授克努特(Donald E.Knuth)在他的名著The Art of Computer Programming(1998,《计算机程序设计艺术》)中专门设计了计算Euler数及Bernoulli数的程序。而幂和的发展经历了两千多年,一直是人们研究的热点。自然数幂和可以分别用Euler数、Bernoulli数、Stirling数相关的表达式表示,使幂和的计算趋于简便快捷。但这三种表达式的互推多年来无人研究,同时这三种表达式的算法的复杂性也无人分析。我国著名数学家徐利治先生在给内蒙古师范大学教授罗见今先生的信中,曾经建议把这个研究作为硕士研究生的论文题目来开展工作,可见这方面的研究的确有重要意义。本文就此问题进行深入研究,给出了这三种表达式的互推,分析了这三种表达式算法的复杂度,得出了它们具有相同的(O)(k2)的复杂度的结论,力求使此方向的研究向前推进一步,以填补此研究领域的空白,并使之具有实践操作性。
本文讨论了幂和的起源与发展,给出了幂和在两千年间取得的主要成果,在这一工作的基础上介绍了两种Stirling数、Euler数及Bernoulli数的发展,对其主要成果给出了说明。通过证明Stirling数、Euler数及Bernoulli数的关于幂和的表达式,最终设计出一整套的算法,给出了关于幂和分别用Stirling数、Euler数及Bernoulli数这几种特殊计数表示的结果。最后对算法进行复杂性的讨论,给出了幂和在这三种表达式的计算量上是等价的结论。