毛俊超,趙熙強(qiáng),王 鵬

(1.海軍潛艇學(xué)院作戰(zhàn)指揮系,山東青島266071;2.中國(guó)海洋大學(xué)數(shù)學(xué)科學(xué)學(xué)院,山東青島266100)

錯(cuò)排數(shù)的概率表示的新應(yīng)用*

毛俊超1,趙熙強(qiáng)2,王 鵬1

(1.海軍潛艇學(xué)院作戰(zhàn)指揮系,山東青島266071;2.中國(guó)海洋大學(xué)數(shù)學(xué)科學(xué)學(xué)院,山東青島266100)

利用孫平和王天明給出的錯(cuò)排數(shù)的概率表示,得到有關(guān)錯(cuò)排數(shù)的遞推公式新的證明方法,并得到有關(guān)錯(cuò)排數(shù)的一些新結(jié)果。

錯(cuò)排數(shù);概率方法;遞推公式

0 引 言

錯(cuò)排數(shù)[1]是組合數(shù)學(xué)中1個(gè)比較重要的組合數(shù),但有關(guān)它的新的研究結(jié)果并不多。文獻(xiàn)[2]利用指數(shù)發(fā)生函數(shù)證明了錯(cuò)排問(wèn)題,并利用錯(cuò)排數(shù)的指數(shù)發(fā)生函數(shù)得出1組有關(guān)錯(cuò)排數(shù)的新恒等式;文獻(xiàn)[3]利用反演技巧與生成函數(shù),把Vinh關(guān)于錯(cuò)排數(shù)的2個(gè)恒等式推廣到更一般的情況;文獻(xiàn)[4]用概率的語(yǔ)言重新描述一些組合數(shù)與多項(xiàng)式,把它們表示成一些常見(jiàn)的隨機(jī)變量的矩的和,其中把錯(cuò)排數(shù)表示成了服從指數(shù)分布[5]的隨機(jī)變量的矩的形式,這是1種構(gòu)造性的概率表示方法,從而更加廣泛與深刻的概率論中的方法與技巧就可以直接應(yīng)用到組合數(shù)的研究中。本文中利用這種概率表示,采用概率論中的方法與技巧,重新研究錯(cuò)排數(shù),得到了有關(guān)錯(cuò)排數(shù)的遞推公式新的證明方法,并得到有關(guān)錯(cuò)排數(shù)的1個(gè)遞推公式和組合和式。文中用到下面的2個(gè)基本概念和1個(gè)引理,所用到的符號(hào)r.v是“隨機(jī)變量”的簡(jiǎn)寫。

定義1[1]設(shè)集合N由n個(gè)不同元素構(gòu)成的,稱集合N到它本身的1個(gè)雙射為N的1個(gè)置換σ;若σ沒(méi)有不動(dòng)點(diǎn),即對(duì)Πx∈N,都有σ(x)≠x,則稱該σ為N的一個(gè)錯(cuò)排,記N的所有的錯(cuò)排數(shù)為d(n)。

定義2[5]r.vΓ服從參數(shù)為λ的指數(shù)分布簡(jiǎn)記為r.v?！?λ),其密度函數(shù)為且有其數(shù)學(xué)期望

引理[4]假設(shè)r.v?！?1),則錯(cuò)排數(shù)d(n)=滿足d(n)=E(Γ-1)n,n≥0。

1 主要結(jié)果及證明

由錯(cuò)排數(shù)的概率表示可以得到下面有關(guān)錯(cuò)排數(shù)的遞推公式新的證明方法。

定理1[1]d(n+1)=(n+1)d(n)+(-1)n+1,d(0)=1。(注:定理1是文獻(xiàn)[1]中的結(jié)論,在這里是使用一種新的方法證明該定理。)

采用同樣的證明方法還可以得到下面的結(jié)果。

定理2 錯(cuò)排數(shù)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)。

利用該結(jié)果聯(lián)立公式d(n+1)=(n+1)d(n)+(-1)n+1,很容易就推出錯(cuò)排數(shù)的另一個(gè)遞推公式:d(n+1)=n{d(n)+d(n-1)}[1]。

從概率論的角度看,常數(shù)變量是隨機(jī)變量的特例,它可以被認(rèn)為是一個(gè)取該常數(shù)的概率為1的隨機(jī)變量,因此可以把組合和式或恒等式中的參量不再看成常數(shù)變量,而是看成服從某分布的隨機(jī)變量,于是原有的組合和式或恒等式就被賦予了更豐富的內(nèi)涵[4]。根據(jù)這種觀點(diǎn),錯(cuò)排數(shù)的概率表示實(shí)際上是二項(xiàng)式定理的1個(gè)特例。這是因?yàn)?對(duì)二項(xiàng)式定理:若取x=Γ,r.vΓ～Γ(1),y=-1,并且2邊取數(shù)學(xué)期望得,即(-1)k,即E(Γ-1)n=

此外,根據(jù)這種觀點(diǎn),利用錯(cuò)排數(shù)的概率表示還可以得到下面有關(guān)錯(cuò)排數(shù)的1個(gè)組合和式。

證明 在Abel恒等式(x+y)nkt)n-k,n≥0(x,y,t是任意參數(shù))中,取x=Γ,r.v?！?1),y=-1,并在恒等式的2邊同時(shí)取數(shù)學(xué)期望,可得

2 結(jié)語(yǔ)

把概率論和組合數(shù)學(xué)結(jié)合起來(lái),從概率論的角度研究組合問(wèn)題,的確具有一定的有效性與實(shí)用性。只要掌握充分的概率論和組合學(xué)的相關(guān)知識(shí),并把二者很好的結(jié)合起來(lái),相信會(huì)出現(xiàn)更多的研究成果。

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

[2] 李志榮.錯(cuò)排問(wèn)題的指數(shù)發(fā)生函數(shù)函數(shù)證明及其新的恒等式[J].四川師范大學(xué)學(xué)報(bào),2004,27(4):650-652.

[3] 陳曉靜,劉其群.關(guān)于錯(cuò)排數(shù)的兩個(gè)等式的注記[J].江蘇大學(xué)學(xué)報(bào),2007,23(1):1-5.

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

[5] 魏宗舒.概率論與數(shù)理統(tǒng)計(jì)教程[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

國(guó)家自然科學(xué)基金項(xiàng)目(10771199)資助

2009-06-09;

2010-03-22

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

AMS Subject Classifications: 05A 15;05A 19

責(zé)任編輯 朱寶象