概率方法在組合數(shù)學(xué)中的某些應(yīng)用

戈海畔,趙熙強

(中國海洋大學(xué)數(shù)學(xué)科學(xué)院,山東青島266100)

概率方法在組合數(shù)學(xué)中的某些應(yīng)用

戈海畔,趙熙強＊＊

(中國海洋大學(xué)數(shù)學(xué)科學(xué)院,山東青島266100)

運用概率論的方法得到有關(guān)Bernoulli數(shù)、第二類Stirling數(shù)、Bell數(shù)、調(diào)和數(shù)、錯排數(shù)等新的關(guān)系式以及遞推公式。

第二類Stirling數(shù);Bell數(shù);錯排數(shù);Bernoulli數(shù)

采用概率論的方法能夠有效地簡化組合問題,這種方法最早是由Erdos[1]提出的,他把這種理論運用到圖論[2]中,之后這種研究問題的方式被運用到Ramsey理論、隨機圖論等組合問題當(dāng)中。本文正是沿用這種概率方法得到一些組合數(shù)學(xué)中新的遞推公式以及新的關(guān)系式,它們涉及到了第二類Stirling數(shù)[3-4],Bell數(shù)bn,調(diào)和數(shù)Hn,錯排數(shù)d(n)等。

1 基礎(chǔ)知識與基本思路

本文涉及到的一些基礎(chǔ)知識[4-6],約定如果一系列隨機變量X1,X2,…是獨立的,且它們的分布相同,

則記為r.v X1,X2,…i.i.d。

(Ⅰ)r.v u1,u2,…i.i.d～U[0,1],則第二類Stirling數(shù)

可以表示為

本文所運用的方法大體思路如下:

找到一個基礎(chǔ)恒等式,把恒等式中的參數(shù)替換成隨機變量,通過整理可以得到一個全新的恒等式,之后通過給恒等式兩邊同時取數(shù)學(xué)期望,再把可以還原成組合數(shù)的部分還原,就得到了一個新的恒等式,顯然若把基礎(chǔ)恒等式中的參數(shù)換成不同的隨機變量得到新的恒等式也會不一樣的。

2 主要結(jié)果

定理1 關(guān)于第二類Stirling數(shù)的遞推公式

綜上,完成了(6)式的證明.

(4)(7)是關(guān)于Bell數(shù)bn與Bernoulli數(shù)Bn的一個關(guān)系式,相應(yīng)的證明過程中則涉及基礎(chǔ)知識(Ⅱ)

(6)(9)是關(guān)于Fibonacci數(shù)Fn與Bernoulli數(shù)Bn的一個關(guān)系式,相應(yīng)的證明過程中涉及基礎(chǔ)知識(Ⅳ) (Ⅵ)。

由基礎(chǔ)知識(Ⅳ)得

綜上,就完成了對定理5中的6個關(guān)系式的證明。

3 結(jié)語

本文在已有的基礎(chǔ)上運用了概率論的方法得到了有關(guān)Stirling數(shù),Bell數(shù),調(diào)和數(shù)Hn,錯排數(shù)d(n)以及Bernoulli數(shù)的新的結(jié)論,從以上討論中也可以看出這種研究問題方法的有效性以及簡潔性。

[1] Erdos P,Spencer J.Probabilistic methods in combinatorics[M]. New York:Academic Press,1974.

[2] Erdos P.Some remarks on the theory of graphs[J].Bull AMS, 1947,53:292-294.

[3] 孫平,王天明.Strling數(shù)的概率表示和應(yīng)用[J].數(shù)學(xué)學(xué)報, 1998,41(2):281-290.

[4] Sun Ping.Product of uniform distribution and Stirling numbers of the first kind,Acta Mathematica Sinica[J].English Series, 2005,21(6):1435-1442.

[5] 魏宗舒.概率論與數(shù)理統(tǒng)計教程[M].北京:高等教育出版社, 1983.

[6] Comtet L.Advanced Combinatorics[M].Reidel:Dordrecht NL, 1974.

Abstract: We use probabilistic methods to get some new relations and recurrence formulae on the Bernoulli numbers,Strling numbers of the second kind,and the Bell number,etc.

Key words: Stirling numbers of the second kind;Bell numbers;derangement numbers;Bernoulli numbers

AMS Subject Classification: 05A15;05A19

責(zé)任編輯 朱寶象

Some Applications of Probabilistic Methods in Combinatorial Mathematics

GE Hai-Pan,ZHAO Xi-Qiang
(School of Mathematical Sciences,Ocean University of China,Qingdao 266100,China)

O157.1

A

1672-5174(2010)09Ⅱ-230-05

國家自然科學(xué)基金項目(10771199)資助

2009-06-12;

2010-05-30

戈海畔(1986-),男,碩士。E-mail:gehaipan19860207@163.com

zhaodss@yahoo.com.cn