自然数幂和三种典型公式的等价证明及算法分析

摘要

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数这几种特殊计数表示的结果。最后对算法进行复杂性的讨论，给出了幂和在这三种表达式的计算量上是等价的结论。

目录

文摘

英文文摘

声明

前言

1绪论

1.1研究背景

1.1.1幂和的发展

1.1.2现阶段研究状况

1.2研究的目的和意义

2幂和三种表达式的证明

2.1方幂和与Bernoulli数及Euler数及Stirling数的定义

2.1.1伯努利数及伯努利多项式

2.1.2欧拉数及欧拉多项式

2.1.3方幂和的定义与Stirling数的定义

2.1.4Bertloulli数及Euler数及Stirling数之间的传换关系

2.2方幂和与Bernoulli数及Euler数及Stirling数的关系表达式

2.3定理的证明

3计算机实现幂和三种表达式

3.1程序需要解决的问题

3.2程序设计的难点

3.3程序设计思路

3.3.1高精度计算

3.3.2几个系数的计算方法

3.3.3多项式的计算

3.3.4计算框图

4幂和三种表达式的算法复杂性分析

4.1关于多项式的复杂度

4.2系数的计算复杂度

4.2.1利用Bernoulli数表示多项式系数

4.2.2利用Euler数表示多项式系数

4.2.3利用Stirling数表示多项式系数

5总结

参考文献

致谢

攻读硕士学位期间公开发表的学术论文