【作者】 尹志凌；

【导师】 张升；

【作者基本信息】 内蒙古师范大学 ， 计算机应用技术， 2010， 硕士

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

【Abstract】 Bernoulli numbers, Stirling numbers and Euler numbers have a wide range of applications in many fields such as combinatorics, function theory, theoretical physics, approximate calculation, and so on. And the summation of powers of integers, as an old topic, has attracted many scholars. In digital images, Euler numbers can be used to describe the structure of the objects remaining characteristics of them unchanged. In discrete mathematics, these special numbers have the combinatorial meanings. They can also be used to count in meteorology, combinatorial optimization, random graph, Ramsey theory, etc., Donald E. Knuth, renowned computer scientist, from Stanford University, in his famous book The Art of Computer Programming, specifically designed programs for calculating Euler numbers and Bernoulli numbers. Research about power sum has experienced more than 2000 years. Famous Chinese mathematicians, Chen Jingrun, Li Jianyu and others, made a great number of researcher, which results in many advanced achievements far ahead. The power summation of natural numbers can be expressed respectively by Euler numbers, Bernoulli numbers, and Stirling numbers. But these three expressions have not been proved to be identical to each other. Moreover, the analysis for the algorithm complexity also has not been given yet so far. Mr. Xu Lizhi, famous Chinese mathematician, suggests that solving the two problems could be a thesis for master degree in his letter to Professor Luo Jianjin from Inner Mongolia Normal University. This implies that this kind of work is so important and the central work of my thesis is about it.This thesis discusses the origin and development of power summation, introduces the main achievements in the last 2000 years about it, based on which, the author recalls the researches related to the two kinds of Stirling numbers, Euler numbers, and Bernoulli numbers, proves some main results about the identity between the expressions of power summation with Euler numbers, Stirling numbers, and Bernoulli numbers, and finally gives the discussion about the complexity of the algorithm.更多还原