（计算机应用技术专业论文）自然数幂和三种典型公式的等价证明及算法分析.pdf

内蒙古师范大学硕士学位论文 中文摘要 b e r n o u l l i 数、s t i r l i n g 数、e u l e r 数在组合数学、函数论、理论物 理及近似计算等方面均有广泛的应用。在数字图像中，可以利用欧拉数来 描述物体结构，保持图像特征不变；在离散数学中，这些特殊数具有组 合含义；在气象学、组合优化、随机图、r a m s e y 理论等方面的也可用这 些特殊数来计数。著名计算机科学家、美国斯坦福大学教授克努特 ( d o n a l de k n u t h ) 在他的名著t h ea r to fc o m p u t e rp r o g r a m m i n g ( 1 9 9 8 ， 计算机程序设计艺术) 中专门设计了计算e u l e r 数及b e r n o u l l i 数的 程序。而幂和的发展经历了两千多年，一直是人们研究的热点。自然数 幂和可以分别用e u l e r 数、b e r n o u l l i 数、s t i f l i n g 数相关的表达式表 示。使幂和的计算趋于简便快捷。但这三种表达式的互推多年来无人研 究，同时这三种表达式的算法的复杂性也无人分析。我国著名数学家徐 利治先生在给内蒙古师范大学教授罗见今先生的信中，曾经建议把这个 研究作为硕士研究生的论文题目来开展工作，可见这方面的研究的确有 重要意义。本文就此问题进行深入研究，给出了这三种表达式的互推， 分析了这三种表达式算法的复杂度，得出了它们具有相同的o ( k 2 ) 的复杂 度的结论，力求使此方向的研究向前推进一步，以填补此研究领域的空 白，并使之具有实践操作性。 本文讨论了幂和的起源与发展，给出了幂和在两千年问取得的主要 成果，在这一工作的基础上介绍了两种s t i r l i n g 数、e u l e r 数及 b e r n o u l l i 数的发展，对其主要成果给出了说明。通过证明s t i r l i n g 数、 e u l e r 数及b e r n o u l l i 数的关于幂和的表达式，最终设计出一整套的算法， 给出了关于幂和分别用s t i r l i n g 数、e u l e r 数及b e r n o u l l i 数这几种特 殊计数表示的结果。最后对算法进行复杂性的讨论，给出了幂和在这三 种表达式的计算量上是等价的结论。 关键词：b e r n o u l l i 数，s t i r l i n g 数，e u l e r 数，算法复杂性 内蒙古师范大学硕士学位论文 ab s t r a c t b e r n o u l l i n u m b e r s ，s t i r l i n gn u m b e r sa n de u l e rn u m b e r sh a v eaw i d e r a n g eo fa p p l i c a t i o n si nm a n yf i e l d ss u c ha sc o m b i n a t o r i c s ，f u n c t i o nt h e o r y , t h e o r e t i c a lp h y s i c s ，a p p r o x i m a t ec a l c u l a t i o n ，a n ds oo n a n dt h es u m m a t i o no f p o w e r so fi n t e g e r s ，a sa no l dt o p i c ，h a sa t t r a c t e dm a n ys c h o l a r s i nd i g i t a l i m a g e s ，e u l e rn u m b e r sc a l lb eu s e dt od e s c r i b et h es t r u c t u r eo ft h eo b je c t s r e m a i n i n gc h a r a c t e r i s t i c so ft h e mu n c h a n g e d i nd i s c r e t em a t h e m a t i c s ，t h e s e s p e c i a ln u m b e r s h a v et h ec o m b i n a t o r i a lm e a n i n g s 。t h e yc a na l s ob eu s e dt o c o u n ti n m e t e o r o l o g y , c o m b i n a t o r i a lo p t i m i z a t i o n ，r a n d o mg r a p h ，r a m s e y t h e o r y , e t c ，d o n a l de k n u t h ，r e n o w n e dc o m p u t e rs c i e n t i s t ，f r o ms t a n f o r d u n i v e r s i t y , i n h i sf a m o u sb o o kt h ear t o fc o m p u t e rp r o g r a m m i n g , s p e c i f i c a l l yd e s i g n e dp r o g r a m sf o rc a l c u l a t i n ge u l e rn u m b e r sa n db e r n o u l l i n u m b e r s r e s e a r c ha b o u tp o w e rs u mh a se x p e r i e n c e dm o r et h a n2 0 0 0y e a r s f a m o u sc h i n e s em a t h e m a t i c i a n s ，c h e nj i n g r u n ，l ij i a n y ua n do t h e r s ，m a d ea g r e a tn u m b e ro fr e s e a r c h e r , w h i c hr e s u l t si nm a n ya d v a n c e da c h i e v e m e n t sf a r a h e a d t h e p o w e rs u m m a t i o n o fn a t u r a ln u m b e r sc a nb e e x p r e s s e d r e s p e c t i v e l yb ye u l e rn u m b e r s ，b e r n o u l l in u m b e r s ，a n ds t i r l i n gn u m b e r s b u t t h e s et h r e ee x p r e s s i o n sh a v en o tb e e np r o v e dt ob ei d e n t i c a lt oe a c ho t h e r m o r e o v e r , t h ea n a l y s i sf o rt h ea l g o r i t h mc o m p l e x i t ya l s oh a sn o tb e e ng i v e n y e ts of a r m r x ul i z h i ，f a m o u sc h i n e s em a t h e m a t i c i a n ，s u g g e s t st h a ts o l v i n g t h et w op r o b l e m sc o u l db eat h e s i sf o rm a s t e rd e g r e ei nh i sl e t t e rt op r o f e s s o r l u oj i a n ji nf r o mi n n e rm o n g o l i an o r m a lu n i v e r s i t y t h i si m p l i e st h a tt h i s k i n do fw o r ki ss oi m p o r t a n ta n dt h ec e n t r a lw o r ko f m yt h e s i si sa b o u ti t t h i st h e s i sd i s c u s s e st h eo r i g i na n dd e v e l o p m e n to fp o w e rs u m m a t i o n ， i n t r o d u c e st h em a i na c h i e v e m e n t si nt h el a s t2 0 0 0y e a r sa b o u ti t ，b a s e do n w h i c h ，t h ea u t h o rr e c a l l st h er e s e a r c h e sr e l a t e dt ot h et w ok i n d so fs t i r l i n g n u m b e r s ，e u l e rn u m b e r s ，a n db e r n o u l l in u m b e r s ，p r o v e ss o m em a i nr e s u l t s 内蒙古师范大学硕士学位论文 a b o u tt h ei d e n t i t yb e t w e e nt h ee x p r e s s i o n so fp o w e rs u m m a t i o nw i t he u l e r n u m b e r s ，s t i f l i n gn u m b e r s ，a n db e r n o u l l in u m b e r s ，a n df i n a l l yg i v e st h e d i s c u s s i o na b o u tt h ec o m p l e x i t yo ft h ea l g o r i t h m k e y w o r d s ：b e m o u l l in u m b e r s ，s t i r l i n gn u m b e r s ，e u l e rn u m b e r s ， a l g o r i t h mc o m p l e x i t y 内蒙古师范大学硕士学位论文 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成果，尽我所知，除了文中特别加以标注和致谢的 地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不 包含本人为获得内蒙古师范大学或其它教育机构的学位或证书而使 用过的材料。本人保证所呈交的论文不侵犯国家机密、商业秘密及 其他合法权益。与我一同工作的同志对本研究所做的任何贡献均已 在论文中作了明确的说明并表示感谢。 功f q 年j 月谚日 关于论文使用授权的说明 本学位论文作者完全了解内蒙古师范大学有关保留、使用学位 论文的规定：内蒙古师范大学有权保留并向国家有关部门或机构送 交论文的复印件和磁盘，允许论文被查阅和借阅，可以将学位论文 的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印 或扫描等复制手段保存、汇编学位论文，并且本人电子文档的内容 和纸质论文的内容相一致。 保密的学位论文在解密后也遵守此规定。 签名： 罗专良 鬻孝烈堵日 f 刖舂 i l l _ 刚吾 从公元前6 世纪，古希腊毕达哥拉斯开始研究自然数方幂和以来，两千多年来幂 和问题一直是人们研究的热点。在数论、特殊函数论及组合计数等领域内，两种 s t i r l i n g 数、两类e u l e r 数及b e r n o u l l i 数等特殊数更是引起了人们的极大的兴趣， 它们具有深刻的意义并取得了广泛的应用，历来受到数学家们的重视。直到今天 e u l e r 数、b e r n o u l l i 数、s t i r l i n g 数等仍然是研究的热点。自从j a m e sb e r n o u l l i 在求正整数次幂的幂和时给出了b e r n o u l l i 数，就注定了b e r n o u l l i 数与幂和之间不 可割断的联系，而作为与之相关的s t i r l i n g 数、e u l e r 数也不可避免的和幂和发生 了联系。几千年来，人们一直在寻找他们之间的关系，得到了许多有趣的结论，对幂 和的发展起到了推动的作用。随着对这些特殊计数的发展，e u l e r 数和b e r n o u l l i 数， 还衍生出诸如e u l e r 多项式、b e r n o u l l i 多项式及其高阶e u l e r 数和高阶b e r n o u l l i 数等相应的定义及其定理，这些公式的出现反过来又推动了这些特殊数数的进一步发 展。 本文致力于研究自然数的方幂和与三种计数之间的关系表达式。幂和自从我国著 名数学家陈景润与黎鉴愚成功计算出前三十个等幂和以来，王云葵、李朝星等人又对 幂和进行了大量的研究，给出了关于幂和与b e r n o u l l i 数之间的表达式，为我们利用 计算机求幂和提供了理论基础。随着计算机的发展，原来因用笔算而需要大量时间的 计算，现在可以由计算机来操作，为我们计算幂和提供了方便。但是e u l e r 数随着n 的增加，会变得很大，而b e r n o u l l i 数是一个分数，如果直接用它的递推公式来进行 程序设计，由于系统的误差将直接导致结果的不确定性，得到的只是b e r n o u l l i 数的 近似数。虽然理论上我们可以做到直接递推，实际中操作却是不可行的，如何计算这 些特殊数，选择何种算法成为一个难题。在本文中，我们先介绍幂和从毕达哥拉斯发 现一次幂和直到王云葵等人给出的1 0 7 个幂和的中问两千多年的主要理论和具有重 要意义的结果，然后利用已知的结果，给出了幂和用e u l e r 数、b e r n o u lli 数、s t i r li n g 数表达的形式，并设计了算法来实现幂和的结果，最后通过分析算法，给出了这三种 公式是在算法上等价的结论。他们具有相同的o ( k 2 ) 的复杂度。 内蒙古师范大学硕士学位论文 1 绪论 1 i 研究背景 1 i 1 幂和的发展 幂和& ( 门) = i 是一个历史悠久的古老问题，公元前6 世纪，古希腊毕达哥拉斯 ( p y t h a g o r a s ) ( 约公元前5 8 0 年一5 0 0 年) 发现任意多个连续自然数之和构成三角形 数，由此利用补充倒立的三角形可得 1 + 2 + 3 + 玎= ! 玎( 玎+ l 、= 一1 玎2 + 三玎 ( 1 ) 222 公元前3 世纪，希腊数学家阿基米德( a r c h i m e d e s ，公元前2 8 7 - 2 1 2 ) 又利用几。 何的方法证明了( 玎+ 1 ) ( 玎口) 2 + a ( a + 2 a + n a ) = 3 ( a 2 + ( 2 a ) 2 + + ( 凇) 2 ) ，利用( 1 ) 则 取a = 1 ，可得公式( 2 ) 【。 1 2 + 2 2 + 3 j + 4 2 + 刀2 = ! 玎( 聆+ 1 ) ( 2 刀+ 1 ) = 三n 3 + 吉n 2 + i 66 ( 2 ) 、 一 326 公元1 0 0 年左右，毕达哥拉斯学派数学家尼可麦丘( n i c o m a c h u s ，6 0 7 1 2 0 7 ) 在 其著作算术引论中指出，在奇数l ，3 ，5 ，7 ，中，第一个是立方数，后面两个之和是 立方数，再后面三个之和是立方数。公元5 、6 世纪，印度数学家阿耶波多( a r y a b h a t a ， 约公元4 7 6 5 5 0 年) 及后来的婆罗摩笈多( b r a h m a g u p t a ，约5 9 8 6 6 0 ) 、摩诃毗罗( m a h a v i r a ，约8 5 0 一? ) 和婆什迦罗( b ha s k a r a ，l l1 4 ? ) 的数学著作中都出现公式( 2 ) 及公式( 3 ) 【1 j 1 3 + 2 3 + 3 3 + 4 3 + 聆3 = ( 圭门( 玎+ 1 ) y = 丢n 4 + j 1n 3 + 百1 玎2 ( 3 ) 1 1 世纪，阿拉伯数学家阿尔卡克希( a l - k a r k h i ，9 5 3 - 1 0 2 9 ) 的数学著作中用富有 希腊特色的几何代数法对公式( 3 ) 给出了证明，到了1 5 世纪，阿拉伯数学家阿尔卡希 ( a 1 一k a s h i ，? 一1 4 3 6 ) 又在算术之钥中给出四次幂和公式2 1 1 4 + 2 4 + 3 4 + 4 4 + 刀4 = ( ( r 1 ) + ，) ( r 2 ) ( 4 ) 1 7 世纪，德国数学教师法尔哈伯( j f a u l h a b e r ，1 5 8 0 1 6 3 5 ) 在其算术之秘 ( 1 6 1 5 ) 中建立了( 1 ) 的从1 到1 7 的幂和公式法国数学家帕斯卡 ( b p a s c a l ，1 6 2 3 1 6 6 2 ) ，利用不完全归纳法获得公式乜1 2 绪论 ( 七：- 1 ) 喜z + ( 七三1 ) 喜产1 + ( 七：1 ) 喜，= c n + 1 ) t m - c ，z + t ， c 5 ， b e r n o u l l i 多项式的起源也是b e r n o u l l i 在计算自然数幂和时引进的。j a m e s b e r n o u l l i ( 1 6 5 4 - - 1 7 0 5 ) 在求正整数次的幂次之和时给出了下面的公式口1 ： 夕f 。：! ，z t + l + ! 玎t + 生及玎i i + k ( k - 1 ) ( k - 2 ) 曰。n t 一3 十k ( k - 1 ) ( k - 2 ) ( k - 3 ) ( k - 4 ) b 6 胛t 智 k + 122 2 2 3 4 2 3 4 5 6 ( 6 ) 直到珂的最后一个正次幂为止， 冥中吹，反，最是b e r n o u l l i 数，且 岛= 否1 ，反= 一菊1 ，玩= 石1 ，坟= 一嘉，蜀。= 去 其递推式为： 鼠= 一去芸( 甩：- 1 p ，z = 。，2 ，玩= t ， c 7 ， 苏格兰数学家斯特灵( j s t i r l i n g ，1 6 9 2 - - 1 7 7 0 ) 在他的著作微分法中给出h 1 崦如i 件- 1 2 l o g n - n + l o g2 瓜+ 鲁 面b 2 丽k 万1 + 以他的名字命名的第二种s t i r l i n g 数以及上式都同幂和有一定关系。 日本的和算家关孝和( s e k i ，t a k a k a z u ，1 6 4 2 1 7 0 ) 也在其括要算法厶垛积术 解方垛部分首先给出了由圭垛积到的十乘方垛积的十一个幂和公式，。得出了自然 数次幂的前，2 项和是n + l 的k + 1 次多项式( 无常数项) 的结论。 在我国也有许多这方面的研究，并取得了一定的成果。公元3 世纪，著名数学家 刘徽( 公元2 5 0 - 9 ) 在注释九章算术时给出了公式( 1 ) ，1 3 世纪，数学家杨辉( 约1 2 3 8 年约1 2 9 8 年) 在详解九章算法中明确给出公式( 2 ) ，特别到了1 9 世纪，著名数学 家李善业- - - ( l ej e ns h o o ，l iz s e ns t l ，1 8 1 1 1 8 8 2 ) 在垛积比类中指出i k ( f = 1 ，2 ，) 可以用k 个k 乘三角垛来表示，即： r ，| 、 忙 姒 内蒙古师范大学硕士学位论文 r 3 = ( 三 + 4 ( r ；1 ) + ( r 三2 ) ， 广t = 三。( r + 主一1 ) + 三。：( r + 妻一2 ) + + 三船( ：) 其中 厶l = 三珏= 1 ( j = l ，2 ) ；乞= ( 七一f + 1 ) 厶t l x ，一1 ) + 以k - 1 ) ( 0 ( 1 ， 七) ， 从而可以得到 喜r = 喜厶，( 聆+ ：+ 1 c 8 ， 清代数学家夏鸾翔( 1 8 2 3 - - 1 8 6 4 ) 在洞方术图解喳3 中研究有限差分理论，建立 了一种计数函数原著称为“单一起根诸乘方诸较图”，记作祥称为夏氏数，横行序数 n ( n = l ，2 ) 表示x 8 中的幂指数，纵列序数七( 岔= 0 ，1 ，2 ) 表示a ，中的差分阶数，据 原著，递归定义可以表示成 霹= l ，研= o ( k ，z ) ( 9 ) 墨= 娥j + ( 七+ 1 ) 霹。 夏氏利用数得到乘方公式= 圭t = o 群( x 7 1 ) 当x 为整数时可得幂和公式 喜f n， 在上世纪八十年代，我国著名数学家陈景润与黎鉴愚对等幂和进行了大量的研 究，得到了如下的递推公式阱： 设，z ，k 为自然数，m = 2 n + l ，n = n ( n + 1 ) 则 c 缸2 r1 是，( 门) = 妻( ( ，z + 1 ) 2 + 力砧- 2 k n - 1 ) ( 1 1 ) 嚷。是，( 刀) = 妻( ( 刀+ 1 ) 2 “1 + 刀2 “1 - m ) ( 1 2 ) 从而一举获得了前3 0 个等幂和公式，远远领先于西方国家。此后我国研究幂和的科 学家们又获得了大量的关于幂和的公式，尤其是王云葵等人利用微积分方法来研究等 幂和问题，改进了陈景润与黎鉴愚的算法，得到了当k 4 时n 1 ， q 1 是川( 甩) = 去( ( 刀+ 1 ) 。+ ( 一疗) 一2 n - 1 ) ( 1 3 ) 4 绪论 l 字i， q 7 是，( 玎) = 去( o + 1 ) + ( 一万) 一m ) ( 1 4 ) 髦g $ 2 , _ l ( n ) 2 r - i = k 馨去二l ， ct 5 ， l t i ii t l i 。t j 口( 妒等。丢1 ， ( 1 6 ) 利用这些公式，从而求出了前1 0 7 个等幂和。遥遥领先于世界，同时也为等幂和 的研究指引了方向。 陈瑞卿通过对幂和的研究，在前人的基础上又获得了关于幂和的新的结果。在其 论文幂和问题的新结果中得到了关于幂和系数的递推公式哺1 。 设门，k 为自然数，n = 刀( 玎+ 1 )m = 2 n + l ，n = n ( n + 1 ) 记 是川( 玎) = ea r n 扛“2 ；。( 疗) = 彰“”1 ( 2 ，z + 1 ) ； 群= 瞄= 0 ：型丛彤 ( 1 7 ) k i + 2 群= 【2 群一一一均+ 1 ) + 2 从而使这个典型的古老问题的求和方法得以简化，为进一步利用b e r n o u l l i 数求 幂和提供了依据。 1 1 2 现阶段研究状况 自然数幂和求解问题发展迅速。我国现阶段已经得到了很多关于幂和的结果，而 作为e u l e r 数、b e r n o u l l i 数、s t i r l i n g 数这三个组合数学中的重要计数，也取得了 很大的进展。 李朝星，韩宇健在其论著自然数方幂和的包含b e r n o u l1i 数的精确表示式中， 给出了自然数方幂和可以用多项式表示，并用西种方法给出其系数的包含b e r n o u l l i 数的几种精确表示凹3 。 吃= 丽m - 1 一薯击阶+ ， 内蒙古9 币范大学硕士学位论文 则 吃七扩 丽m - 1 + m 驴- 2 ，者阶+ ， 跏，= 雨1 1 + 筹击咖 跏) = 雨1 玎_ i 雨1 备k - ii t 七岁1 b 玎 ( 1 8 ) 李志荣在广义m 阶b e r n o u l l i 数和广义m 阶e u l e r 数的计算公式中给出当m 为实数时，广义m 阶b e r n o u l l i 数磁帕和广义m 阶e u l e r 数磷m 的定义，并且利用第 一类无符号s t i r l i n g 数和第二类s t i r l i n g 数的发生函数得到广义m 阶b e r n o u l l i 数磁哪和广义聊阶e u l e r 数耳州分别用第一类s t i r l i n g 数及第二类s t i r l i n g 数表 示的几组计算公式n 引 设朋r ，广义垅阶b e r n o u l l i 数磁引和的定义，z 阶e u l e r 数霹州由下式给出： 薹等九( 去) ”，( i 水印， ) 卅 ，( h 2 1 0 广义m 阶b e r n o u l l i 数噬”的计算公式，设s 2 ( ，z ，五) 为第二类s t i r l i n g 数 设m r ，玎n ，贝4 磁“= 1 且 磁驯l = ( 一) ”竹：。+ ：。+ 莓，峨：。( 了 搞赤一薹s ：c 甩，七，磁”) 。i + i 2 + b + 2 ， ( 1 9 ) 砂! 酣c o 广h 丑一点0 了) ，! i 。! 之! 31 一厶 即) _ 赫k = 0 毗) ( _ 矿七! i l + 2 2 + 3 b + 叫j 七t = 七 t i + t + 1 3 + t = 设聊r ，n n ，则鹾州= 1 且 ，! i 。! i 21 f 31 一一 1 2 1 3 。z + 1 ) 一1 n - i n ) 磁“) l 一 2 t 1 3 j 2 0 + 1 ) 岛 s 2 ( n ，七) 为第二类s t i r l i n g 数 6 ( 2 0 ) ( 2 1 ) 筹 ，1 坐m 。脚 绪论 掣= ( 孙z i t + 2 i 2 + 3 t 3 + 巩北) 器( c o s 锁c o s 带( c o s 学) 。 一最( 胛，七) 砭” ( 2 2 ) 刊”：磊北) 躺( c o s 锁c o s 才( c o s 学 k 一酗即 ( 2 3 ) = 鼢( 孙一i i + 2 1 2 + 3 ；3 + 皑旧躺( c o s 才( c o s 半y ( 2 4 ) 杨奎林与刘国栋在一些包含第二类中心阶乘数的求和公式中利用实数或复数 意义下广义e u l e r 数吃和广义b e r n o u l l i 数群1 丽2 ) 。= 丢两t 2 n ! ( s 叫。= 薹( 一j _ t 2 2 州t 磁n = 0 、厶，： c 去卜薹南研 及其递推公式并在第二类中心阶乘数是( 门，七) 是由下列生成函数给出时 = s ：( 玎，k ) x ( x - 1 2 ) ( x - 2 2 ) ( x 一3 2 ) o 一( 七一1 ) 2 ) k = 0 得到当门n 时以下定理成立： 内蒙古师范大学硕士学位论文 羔螋s ( 疗，七) = 巨。(25)ok 2 厶 一v ，一，一2 n 7 k = o 二 薹掣蛐- 2 2 州( 2 2 n + 2 _ 1 ) 丽b 2 n + 2 易。( 2 6 ) 砉掣趣帆驴2 。：一2 2 2 n + 2 ( 2 2 n + 2 _ 1 ) 磊n 2 n + 2 ( 2 7 ) 李朝星在自然数方幂和中的s t i r l i n g 数研究又给出了自然数方幂和关 于( ；：1 或( 行岁1 ) 的表达式n 2 】 ，= 驴k ：化，) ， = 蔷k s a n ) z s ：( 七+ 1 ，j + t ) ( 歹：。) c 2 9 ) = 弘2 ( 七+ ，+ 1 ) k1 i ( 2 9 ) 其中s 2 ( ，) 表示第二类s t i r l i n g 数。 直接计算式为 卅漕叫0 m ， i s 。c ，z ，= = 妻 妻c _ t ，一7 ( 二) c r ， ( n 。) c 3 - ， 并给出了当 ，k + l 时b e r n o u l l i 数与s t i r l i n g 数之间的关系 势”u h u 少由f 卜= 势限川h u 洲3 2 ， 2 0 0 5 年朱伟义在自然数幂和公式系数的递推公式和有关b e r n o u lli 数的计算 公式给出n 3 3 设( 川= a k ，。，z 川+ ，z 。+ 1 一。+ 一以，t ，2 s k + l ( 甩) 为自然数的k + 1 次幂和则递推公式为 吼“。：；銎l 吼 j ，o f 七；鼠+ i ：竺乌竽，1 ， ( 3 3 ) 、7七+，+lf、一七+f 8 绪论 或者利用 口k + i d ：黑a k , i 轧2 而u s s 七； 一t a k + i ，t + l = 1 - 口+ i ， b o 并且同时可得到 = 等胚，其中色为b e r n o u l l i 数。 利用这一递推公式，我们可以用利用计算机实现求幂和值，同时也可得到 b e r n o u l l i 数的值。 2 利用生成函数法去求自然数幂和 孙哲，殷喜荣用三个关系式与m a t h e m a t i c a 软件求第二类自然数幂和公式 中提到若第二类自然数幂和定义式n 铂 s k ( n ) = ( i - 1 ) 跏船幽+ ( n 小幽) ，z ( 3 4 ) 则生成函数与其的关系是为 鲁= 薹跏，鼢 由此可以利用自然数幂和积分递推关系式去求和。 3 利用m a t h e m a t i c a 软件系统和高阶等差数列求自然数幂和 在龚飞兵的自然数幂和公式的另一种计算机实现方法一文中，作者利用 m a t h e m a t i c a 系统和高阶等差数列的一个结果，利用类p a s c a l 矩阵实现了求幂和的结 田【1 5 1 7 ko 1 2 研究的目的和意义 b e r n o u l l i 数、e u l e r 数、高阶b e r n o u l l i 数、高阶e u l e r 数及s t i r l i n g 数在组 合数学、函数论、理论物理及近似计算等方面均有广泛的应用，它们之间的关系研究 直受到学者的关注。 在数字图像中，能表现其拓扑性质的量是指当图像像橡皮薄膜那样伸缩变化时， 保持图像特征不变的量。欧拉数恰好就是可以描述物体结构，而与其特定几何形状无 9 内蒙古师范大学硕士学位论文 关的拓扑参数。对于二维图像，欧拉数就被定义为连接体数与其中的孔洞数之差n 引。 离散数学的兴起，使得这些特殊数也经历了相当的发展，一些特殊数还具有组合含义。 很多组合数与随机变量的矩有关n ，s t i r l i n g 数和b e r n o u l l i 数都有错位排列数的概 率解释n 引。著名计算机科学家、美国斯坦福大学教授克努特( d o n a l de k n u t h ) 也在 他的名著t h ea r to fc o m p u t e rp r o g r a m m i n g ( 1 9 9 8 ，计算机程序设计艺术) 中专 门设计了计算e u l e r 数及b e r n o u l l i 数的程序n 9 1 。 但是这些特殊的计数在计算时并不是很容易的，b e r n o u l l i 数是有理数且除一两 个以外均为分数，这些分数的分子随着n 的增大而迅速增大，而且要求是最简分数， 笔算难度陡然上升，人们至多计算到6 0 多位，就不能计算了。e u l e r 数、s t i r l i n g 数由于全是整数要好一些。但是当n 很大时，值会变得很大，计算问题也成为了一个 难题。当计算机出现之后，使用任何一种计算机程序设计语言就可以计算出较小的 e u l e r 数、s t i r l i n g 数，但计算机系统会有临界值，当数值超过这一临界值以后，必 须设计相应结构来存储计算，否则计算机就会自动将结果表示为近似的实数值，这时 结果就没有意义。同时对伯努利数来说，如果企图直接用它的递推公式来进行程序设 计，几乎是不可能成功的。这是因为，第一，计算机直接输出的只是伯努利数的一些 近似值，而近似值对于我们的目的来说是无用的；第二，即使想办法控制表达形式， 也很难有效地输出所需要的最简分数。而这两种数趋向无穷的速度都很快，所以在算 法的选择上也是一个很大的难题。著名计算机科学家克努特( d o n a l de k n u t h ) 于 1 9 6 7 年将这两种数计算到了第2 0 0 个，这是目前比较好的结果但1 。 自然数幂和可以分别用e u l e r 数、b e r n o u l l i 数、s t i r l i n g 数相关的表达式表示， 但这三种表达式的互推尚没有给出，固时对这三种表达式所给出的算法的复杂性也没 有给出过分析。我国著名数学家、组合分析专家徐利治先生曾经建议把这个研究作为 硕士研究生的论文题目来开展工作，可见这方面的研究的确有重要意义。 1 0 幂和三种表达式的证明 2 幂和三种表达式的证明 2 1 方幂和与b e r n o u i li 数及e uie r 数及s tiriin g 数的定义 2 1 1 伯努利数及伯努利多项式 数学家e u l e r ( l e o n h a r de u l e r ，1 7 0 7 - - 1 7 8 3 ，瑞士人) 给出b e r n o u l l i 数e 的 指数型生成函数为1 二：争堡， e 一1 篇n ! 由其确定的系数最称为b e r n o u l l i 数，现在一般用此式来定义它。其中 鼠= 1 曩= 一j i ，由于函数厂( x ) 2 孑一玩二日二是偶函数，则通过七匕较厂( x ) - - 与- f ( 一x ) 的两个恒等级数的各个不同次幂的系数不难得到 b 2 。+ l = 0 ，n = 1 ，2 ， 利用扯k ：o t = o 、1 还可以得到递推公式啪1 耻 杰芸( 2 ：1 p 乩2 ， 也可以写成 鼠乩e = 丽n - 1 一备n - 2 鬲1 ( n ，户+ ，z 吃3 ， 其与正切数有如下关系1 ： b 2 nm 2 两n d 设聊r ，广义m 阶b e r n o u l li 数b 的指数型生成函数可由下面的公式给出n 们 ( 去) ”= 砉等 内蒙古师范大学硕士学位论文 由此确定的系数磁州称为广义珑阶b e r n o u l l i 数。当m = 1 时，碰们即为b e r n o u l l i 数峨。 广义m 阶b e r n o u l l i 数磁州与b e r n o u l l i 数尾关系如一p 。： 砌、fe b 吃吃 2 帆量：。黹 b e r n o u l l i 多项式的定义是b e r n o u l l i 计算自然数幂和时引进的口，即存在唯一的一 个首项系数为l 的n 次多项式鼠 ) 使得下式成立 l ”+ 2 no o ( k - 1 ) ”= r 吃( x ) 出 b e r n o u l l i 多项式色( x ) 的严格分析定义是由下面指数生成函数给出 m 力= 蓦= 薹等矿 其中f 为参数，当t = o m t 域( 0 ) = 吃。 2 1 2 欧拉数及欧拉多项式 e u l e r 在研究级数的过程中给出了欧拉数酶指数型生成函数为2 i 】 罢：争墨矿 e 2 j + 1 台门! “ 由其确定的系数e 称为e u l e r 数，也称为第一类e u l e r 数。 由于函数0 x ) = 若是偶函数，则通过比较厂( x ) 与厂( 一x ) 的两个恒等级数的各 个不同次幂的系数可以得到与b e r n o u l l i 数类似的结果岛剃= 0 ，玎= l ，2 ，。 利用欧拉数的指数型生成函数，取x = o ，可知= 1 ，并且还有递推公式： 窆( 蛩) 易，：o ，( 纠) i = o l 罗见今教授指出可以用本弧求割线术的递归法来求s e c ( x ) 展开式的系数陋2 1 即欧 拉数，利用这一方法可以得到欧拉数的递推公式如下 初值：e ( o ，0 ) ：1 ，e ( m ，刀) = o ( m 门) e = e ( n ，疗) = ( - 0 “1 e ( n ，n - k ) 同时他还提到的是戴煦数即为正切数，其具有如下的递推公式心纠： 初值：d ( m ，0 ) = 1 ，d ( m ，船) = 0 ( 聆 m ) 递推式：。( 坍，刀) = 西万( 2 j m 两- 1 砭) ( i 2 m j - 五2 ) 面。( m - 1 , n ) ， 所) d ( n ，疗) = ( 一1 ) 1 d ( n ，n - k ) 设m r ，r 。y m 阶e u l e r 数磁”的指数型生成函数可由下面的公式给出口1 ( 笔心挚 由此确定的系数e 帕称为广义垅阶e u l e r 数。当聊= 1 时，e 州即为e u l e r 数色。 e u l e r 多项式e ) 是由指数生成函数口3 竺：争型x 一 e 。+ 1 鲁玎! 中的e ( ，) 来确定的。若令f = 乏1 z = 2 甜 可得 筹三薹拿2 砸，一 根据e u l e r 数的定义则 艺n = o 掣2 v ：势” - ，l ! 怠以! 比较对应项系数，从而可得 乜( 三) 2 ”= e 这一欧拉数与多项式之间的关系。 2 1 3 方幂和的定义与8 t iri in g 数的定义 内蒙古师范大学硕士学位论文 设疗，k 均为正整数，我们称由 吼= x ( x - 1 ) ( x 一2 ) ( x - n + 1 ) = s ( 门，k ) x 所确定的s ( ，z ，k ) 为第一类s t i r l i n g 数乜3 l 。 设以，k 均为正整数，我们称由 n p = & ( p ，0 ) 【玎】o + + 曼( p ，p ) ，z 】口 所确定的s 2 ( n ，七) 为第二类s t i r l i n g 数。其表示的含义为门个有区别的球放到m 个相 同的盒子中，没有一个空盒的方案数盥钔。 设亿k 均为正整数，我们定义& ( 玎) = i 为自然数方幂和。显然 i = 1 瓯( 门) = s k ( 门一1 ) + n 2 2 1 4b e r n o ul ii 数及e uie r 数及s tiri n g 数之间的转换关系 e = 南势广川e m ) , n = 2 , 3 , 4 , - p 1 色= t + 耋吃+ 。警( ：) ，= 。，2 ，3 ，4 ，3 1 玩= 耋( _ 1 ) ”黑( n + l , m + 1 ) 吃= 妻( - 1 ) 熹s ：m ) 最= 掣一薹n - i 跏川吃，纠m 1 2 2 方幂和与b e r n o u i 数及e ule l - 数及s tiriin g 数的关系表达式 定理l ：设以，庀均为正整数，则幂和瓯( 刀) = i 与b e r n o u l l i 数之间存在如下关系式： 跏，= 击1 + 击甜批九 1 4 幂和三种表达式的证明 定理2 ：设k 均为正整数，自然数方幂和瓯o ) = i 与e u l e r 数之间关系表达式为 s k ( n ) 庀1 i t n + i + i 2 玎t + 荟k - ict，一7(：)ij斋薹c一，”(七：r)上z。玎7 c 2 ， 定理3 ：自然数方幂和s 。( 门) = i 2 与第二类s t i r l i n g 数之间的关系可表示为 跏，= 抵i = 1 限文r1 定理4 ：幂和瓯( ，2 ) 可由第一类s t i r l i n g 数与第二类s t i r l i n g 数共同表出 七+ lk + i 1 & ( 聍) = 墨( 后，歹) s ( ，r ) ( ，z + 1 ) 7 r = l = rj 2 。3 定理的证时 为了给出上述几个定理的证明，我们先给以下几个关于b e r n o u l l i 数及e u l e r 数及s t i r li n g 数的结论如下： 鼠= 南势广”一已m n 。= 2 , 3 , 4 , - - - 吲 域= 薹) ”篙( n + l , - m + 1 ) 色= 驴k ) ”熹跏川 ( 6 ) 1 2 1 ( 7 ) 引理1 ：b e r n o u l l i 数满足如下关系式： ，” 丽m - 1 曲i = 1 ，川 证明： 取刀= m + l ，贝u 有 由反= 划e 玩+ ( 小f 1 届+ 姜( 聊；1 ) e = 。 内蒙古师范大学硕士学位论文 由鼠= 1 ，蜀= 一丢，代入可得 知上式可写为 则知 故 由 即 兰1 = 2 一卜字，峨“= 啦， 扣竹1 p = 丁m - 1 九m 邶吃= 丁m - 1 一驴m - i ，。一p 。七矿fm - 1 万一而1 m - in 1 ) 一磊刍m - | 竹1 卜 = 荟m - i ( - 1 ) i + 1 禹 = 驴m - i 广啦m 。p = m 驴- 2 ，击 纠叫m - 1 石+ m 驴- 2 ，击盼+ 1 定理1 ：设”，k 均为正整数，则