自然數(shù)冪和三種典型公式的等價(jià)證明及算法分析.pdf

1、Bernoulli數(shù)、Stirling數(shù)、Euler數(shù)在組合數(shù)學(xué)、函數(shù)論、理論物理及近似計(jì)算等方面均有廣泛的應(yīng)用。在數(shù)字圖像中，可以利用歐拉數(shù)來(lái)描述物體結(jié)構(gòu)，保持圖像特征不變；在離散數(shù)學(xué)中，這些特殊數(shù)具有組合含義；在氣象學(xué)、組合優(yōu)化、隨機(jī)圖、Ramsey理論等方面的也可用這些特殊數(shù)來(lái)計(jì)數(shù)。著名計(jì)算機(jī)科學(xué)家、美國(guó)斯坦福大學(xué)教授克努特(Donald E．Knuth)在他的名著The Art of Computer Programming(1

2、998，《計(jì)算機(jī)程序設(shè)計(jì)藝術(shù)》)中專(zhuān)門(mén)設(shè)計(jì)了計(jì)算Euler數(shù)及Bernoulli數(shù)的程序。而冪和的發(fā)展經(jīng)歷了兩千多年，一直是人們研究的熱點(diǎn)。自然數(shù)冪和可以分別用Euler數(shù)、Bernoulli數(shù)、Stirling數(shù)相關(guān)的表達(dá)式表示，使冪和的計(jì)算趨于簡(jiǎn)便快捷。但這三種表達(dá)式的互推多年來(lái)無(wú)人研究，同時(shí)這三種表達(dá)式的算法的復(fù)雜性也無(wú)人分析。我國(guó)著名數(shù)學(xué)家徐利治先生在給內(nèi)蒙古師范大學(xué)教授羅見(jiàn)今先生的信中，曾經(jīng)建議把這個(gè)研究作為碩士研究生的論文題

3、目來(lái)開(kāi)展工作，可見(jiàn)這方面的研究的確有重要意義。本文就此問(wèn)題進(jìn)行深入研究，給出了這三種表達(dá)式的互推，分析了這三種表達(dá)式算法的復(fù)雜度，得出了它們具有相同的(O)(k2)的復(fù)雜度的結(jié)論，力求使此方向的研究向前推進(jìn)一步，以填補(bǔ)此研究領(lǐng)域的空白，并使之具有實(shí)踐操作性。
　　 本文討論了冪和的起源與發(fā)展，給出了冪和在兩千年間取得的主要成果，在這一工作的基礎(chǔ)上介紹了兩種Stirling數(shù)、Euler數(shù)及Bernoulli數(shù)的發(fā)展，對(duì)其主要成果