错排数的概率表示的新应用*

毛俊超,赵熙强,王 鹏

(1.海军潜艇学院作战指挥系,山东青岛266071;2.中国海洋大学数学科学学院,山东青岛266100)

错排数的概率表示的新应用*

毛俊超1,赵熙强2,王 鹏1

(1.海军潜艇学院作战指挥系,山东青岛266071;2.中国海洋大学数学科学学院,山东青岛266100)

利用孙平和王天明给出的错排数的概率表示,得到有关错排数的递推公式新的证明方法,并得到有关错排数的一些新结果。

错排数;概率方法;递推公式

0 引 言

错排数[1]是组合数学中1个比较重要的组合数,但有关它的新的研究结果并不多。文献[2]利用指数发生函数证明了错排问题,并利用错排数的指数发生函数得出1组有关错排数的新恒等式;文献[3]利用反演技巧与生成函数,把Vinh关于错排数的2个恒等式推广到更一般的情况;文献[4]用概率的语言重新描述一些组合数与多项式,把它们表示成一些常见的随机变量的矩的和,其中把错排数表示成了服从指数分布[5]的随机变量的矩的形式,这是1种构造性的概率表示方法,从而更加广泛与深刻的概率论中的方法与技巧就可以直接应用到组合数的研究中。本文中利用这种概率表示,采用概率论中的方法与技巧,重新研究错排数,得到了有关错排数的递推公式新的证明方法,并得到有关错排数的1个递推公式和组合和式。文中用到下面的2个基本概念和1个引理,所用到的符号r.v是“随机变量”的简写。

定义1[1]设集合N由n个不同元素构成的,称集合N到它本身的1个双射为N的1个置换σ;若σ没有不动点,即对Πx∈N,都有σ(x)≠x,则称该σ为N的一个错排,记N的所有的错排数为d(n)。

定义2[5]r.vΓ服从参数为λ的指数分布简记为r.vΓ～Γ(λ),其密度函数为且有其数学期望

引理[4]假设r.vΓ～Γ(1),则错排数d(n)=满足d(n)=E(Γ-1)n,n≥0。

1 主要结果及证明

由错排数的概率表示可以得到下面有关错排数的递推公式新的证明方法。

定理1[1]d(n+1)=(n+1)d(n)+(-1)n+1,d(0)=1。(注:定理1是文献[1]中的结论,在这里是使用一种新的方法证明该定理。)

采用同样的证明方法还可以得到下面的结果。

定理2 错排数d(n)满足d(n+1)=n(-1)n+n(n+1)d(n-1)。

所以d(n+1)=n(-1)n+n(n+1)d(n-1)。

利用该结果联立公式d(n+1)=(n+1)d(n)+(-1)n+1,很容易就推出错排数的另一个递推公式:d(n+1)=n{d(n)+d(n-1)}[1]。

从概率论的角度看,常数变量是随机变量的特例,它可以被认为是一个取该常数的概率为1的随机变量,因此可以把组合和式或恒等式中的参量不再看成常数变量,而是看成服从某分布的随机变量,于是原有的组合和式或恒等式就被赋予了更丰富的内涵[4]。根据这种观点,错排数的概率表示实际上是二项式定理的1个特例。这是因为,对二项式定理:若取x=Γ,r.vΓ～Γ(1),y=-1,并且2边取数学期望得,即(-1)k,即E(Γ-1)n=

此外,根据这种观点,利用错排数的概率表示还可以得到下面有关错排数的1个组合和式。

证明 在Abel恒等式(x+y)nkt)n-k,n≥0(x,y,t是任意参数)中,取x=Γ,r.vΓ～Γ(1),y=-1,并在恒等式的2边同时取数学期望,可得

2 结语

把概率论和组合数学结合起来,从概率论的角度研究组合问题,的确具有一定的有效性与实用性。只要掌握充分的概率论和组合学的相关知识,并把二者很好的结合起来,相信会出现更多的研究成果。

[1] Com tet L.Advanced Combinatorics[M].Boston:D.Reidel Publishing company,1974:180-183.

[2] 李志荣.错排问题的指数发生函数函数证明及其新的恒等式[J].四川师范大学学报,2004,27(4):650-652.

[3] 陈晓静,刘其群.关于错排数的两个等式的注记[J].江苏大学学报,2007,23(1):1-5.

[4] 孙平,王天明.Stirling数的概率表示和应用[J].数学学报,1998,41(2):281-290.

[5] 魏宗舒.概率论与数理统计教程[M].北京:高等教育出版社,1983.

New Applications on Probabilistic Rep resentations of the Number of Derangements

M AO Jun-Chao1,ZHAO Xi-Qiang2,WANG Peng1
(1.Navy Submarine Academy,Qingdao 266071,China;2.School of Mathematical Science,Ocean University of China,Qingdao 266100,China)

By applying the probabilistic representation of the number of derangements presented by Sun and Wang,a new p roof of the recurrence formulas is given and some new results on the number of derangements are achieved.

the number of derangements;probabilistic method;recurrence formula

O157.1;O211

A

1672-5174(2010)12-159-02

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

2009-06-09;

2010-03-22

毛俊超(1976-),男,讲师。E-mail:maojunchao2727@sina.com.cn

AMS Subject Classifications: 05A 15;05A 19

责任编辑 朱宝象