概率方法在组合数学中的某些应用

戈海畔,赵熙强

(中国海洋大学数学科学院,山东青岛266100)

概率方法在组合数学中的某些应用

戈海畔,赵熙强＊＊

(中国海洋大学数学科学院,山东青岛266100)

运用概率论的方法得到有关Bernoulli数、第二类Stirling数、Bell数、调和数、错排数等新的关系式以及递推公式。

第二类Stirling数;Bell数;错排数;Bernoulli数

采用概率论的方法能够有效地简化组合问题,这种方法最早是由Erdos[1]提出的,他把这种理论运用到图论[2]中,之后这种研究问题的方式被运用到Ramsey理论、随机图论等组合问题当中。本文正是沿用这种概率方法得到一些组合数学中新的递推公式以及新的关系式,它们涉及到了第二类Stirling数[3-4],Bell数bn,调和数Hn,错排数d(n)等。

1 基础知识与基本思路

本文涉及到的一些基础知识[4-6],约定如果一系列随机变量X1,X2,…是独立的,且它们的分布相同,

则记为r.v X1,X2,…i.i.d。

(Ⅰ)r.v u1,u2,…i.i.d～U[0,1],则第二类Stirling数

可以表示为

本文所运用的方法大体思路如下:

找到一个基础恒等式,把恒等式中的参数替换成随机变量,通过整理可以得到一个全新的恒等式,之后通过给恒等式两边同时取数学期望,再把可以还原成组合数的部分还原,就得到了一个新的恒等式,显然若把基础恒等式中的参数换成不同的随机变量得到新的恒等式也会不一样的。

2 主要结果

定理1 关于第二类Stirling数的递推公式

综上,完成了(6)式的证明.

(4)(7)是关于Bell数bn与Bernoulli数Bn的一个关系式,相应的证明过程中则涉及基础知识(Ⅱ)

(6)(9)是关于Fibonacci数Fn与Bernoulli数Bn的一个关系式,相应的证明过程中涉及基础知识(Ⅳ) (Ⅵ)。

由基础知识(Ⅳ)得

综上,就完成了对定理5中的6个关系式的证明。

3 结语

本文在已有的基础上运用了概率论的方法得到了有关Stirling数,Bell数,调和数Hn,错排数d(n)以及Bernoulli数的新的结论,从以上讨论中也可以看出这种研究问题方法的有效性以及简洁性。

[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数的概率表示和应用[J].数学学报, 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] 魏宗舒.概率论与数理统计教程[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

责任编辑 朱宝象

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

国家自然科学基金项目(10771199)资助

2009-06-12;

2010-05-30

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

zhaodss@yahoo.com.cn