一種新穎的第二類Stirling數(shù)公式證明

李新社， 姚俊萍

（西安高新技術(shù)研究所，陜西西安 710025）

0 引 言

Stirling數(shù)在資源分配、微積分應(yīng)用、有限集合劃分等方面都有著廣泛的應(yīng)用，所以諸多學(xué)者在論文或編著中都研究和討論Stirling數(shù)，但由于Stirling數(shù)復(fù)雜，計算公式難以推導(dǎo)，所以證明過程難以掌握接受。文獻［1］通過7個引理和數(shù)學(xué)歸納法完成了第二類Stirling數(shù)公式的證明，篇幅長達兩個版面，推導(dǎo)變化異常復(fù)雜；文獻［2］通過不完全歸納法進行猜想Stirling數(shù)公式，然后，通過大量的組合計算變換完成了第二類Stirling數(shù)公式的證明，關(guān)鍵是猜想的邏輯難以論述，不易閱讀、理解和掌握；文獻［3］給出了一些特殊情況下的Stirling數(shù)計算公式，缺乏普遍性，難以推廣使用；文獻［4］通過數(shù)學(xué)歸納法完成了第二類Stirling數(shù)公式的證明，但證明過程長，而且只回答了公式的正確性，未回答公式的模型構(gòu)造過程。文中根據(jù)函數(shù)定義、滿射函數(shù)特性、容斥原理、逐步淘汰原理、排列組合理論等，討論分析了滿射函數(shù)與有限集合劃分的關(guān)系，基于逐步淘汰原理給出了有限集合間滿射函數(shù)個數(shù)的計算公式，最后由滿射函數(shù)個數(shù)計算公式推導(dǎo)出含有m個元素的有限集合劃分成n個非空子集的種類數(shù)計算公式，從而完成了第二類Stirling數(shù)公式的一個既簡單又易接受的證明過程。

1 基本概念與基本原理

定理1 設(shè)π是非空集合A上的劃分，R是A上的等價關(guān)系，那么π誘導(dǎo)出R當且僅當R誘導(dǎo)出π。

定理2（容斥原理） 設(shè)A1，A2，…，An為有限集合，則

定理3（逐步淘汰原理） 設(shè)A1，A2，…，An為有限集合S的子集，則

定義2 設(shè)A，B是兩個集合，如果按照某種對應(yīng)法則f，對于集合A中的任何一個元素，在集合B中都有唯一的元素和它對應(yīng)，這樣的對應(yīng)叫作從集合A到集合B的映射。記作：f：A→B。

定義3 設(shè)f是A到B的一個映射，若對B中的每一個元素y，都存在x∈A使得y＝f（x），則稱f是A到B的一個滿射。

根據(jù)文獻［6-7］，Stirling數(shù)的本質(zhì)在于求解有多少種方法可將一個含有m個元素的有限集合劃分成n個非空的子集，記為S（m，n）。根據(jù)這一含義顯然有

S（m，n）數(shù)列通項計算公式為

現(xiàn)在的問題是上面這個通項計算公式是否正確？如何得來？正如引言所論述，文獻［1-4］的作者和其他一些國內(nèi)外學(xué)者都給出了一些研究成果，但推導(dǎo)過程復(fù)雜，難以理解和掌握。下面基于定義1、定義2、定義3、定理1、定理2、定理3等展開研究。

2 有限集合劃分與有限集合間滿射函數(shù)的關(guān)系

設(shè)f：A→B為A到B的任意一個滿射函數(shù)，其中，｜A｜＝m，｜B｜＝n，m＞n，規(guī)定A上的二元關(guān)系R為

不難證明R具有自反性、對稱性和傳遞性，是A上的一個等價關(guān)系。這樣由一個滿射函數(shù)就確定了一個等價關(guān)系，而基于這個等價關(guān)系正好將A可劃分成n個非空子集。又根據(jù)有限集合上的等價關(guān)系與有限集合的劃分是一一對應(yīng)的（定理1），所以滿射函數(shù)與劃分之間有對應(yīng)關(guān)系，但注意到等價關(guān)系定義中強調(diào)的是函數(shù)值相同，未強調(diào)對應(yīng)的具體值，也就是說函數(shù)值之間可以互換并不改變劃分結(jié)果，因此，根據(jù)函數(shù)定義和排列組合原理可以得出n！個函數(shù)對應(yīng)一個劃分。換句話說，如果求得A到B的滿射函數(shù)個數(shù)，就可求得將一個含有m個元素的有限集合劃分成n個非空子集的方法數(shù)。

3 有限集合間滿射函數(shù)個數(shù)的計算公式

同上，仍然設(shè)f：A→B為A到B的任意一個滿射函數(shù)，｜A｜＝m，｜B｜＝n，m＞n。

根據(jù)滿射函數(shù)定義，B中每個元素都要被映射到，直接求出所有滿射函數(shù)個數(shù)有困難。但從A到B的所有函數(shù)中除去B中至少有一個元素未被映射到的函數(shù)，就可得到A到B的所有滿射函數(shù)。而這正是容斥原理（定理2）和逐步淘汰原理（定理3）解決問題的思路和方法。

首先根據(jù)定義2易知，A與B之間可構(gòu)造的函數(shù)有nm個，其次B中有一個元素未被映射到的函數(shù)個數(shù)為（n－1）m個；B中有2個元素未被映射到的函數(shù)個數(shù)為（n－2）m個；…；B中有i個元素未被映射到的函數(shù)個數(shù)為（n－i）m個；B中元素都未被映射到的函數(shù)個數(shù)顯然為0，即（n－n）m。由定理3得可構(gòu)造的滿射函數(shù)個數(shù)為

即

4 第二類Stirling數(shù)公式與驗證

根據(jù)“2”和“3”的討論，立即可以得出

對于得出的公式，顯然S（m，0）＝0，S（m，1）＝1，S（m，m）＝1，S（m，m－1）＝是成立的，符合Stirling數(shù)的含義。

至于S（m，n）＝nS（m－1，n）＋S（m－1，n－ 1），結(jié)合

也可驗證是成立的。

5 結(jié) 語

通過滿射函數(shù)、等價關(guān)系、劃分、逐步淘汰原理等的相互聯(lián)系，給出了第二類Stirling數(shù)公式證明過程。該證明過程不僅揭示了第二類Stirling數(shù)公式的來源，而且從另一個方面回答了其正確性，有助于對第二類Stirling數(shù)本質(zhì)含義的理解和大力推廣使用。

［1］ 任逸.第二類Stirling數(shù)的一個計算公式及其證明［J］.數(shù)學(xué)通報，2008，47（3）：59-60.

［2］ 楊雅琴.第二類Stirling數(shù)計算公式的一種證明［J］.青島科技大學(xué)學(xué)報：自然科學(xué)版，2009，30（4）：91-93.

［3］ 王紅，楊雅琴，王艷輝.第一類Stirling數(shù)和第二類Stirling數(shù)的關(guān)系式［J］.高師理科學(xué)刊，2008，28（6）：37-39.

［4］ 吳學(xué)澄.計算第二類Stirling數(shù)的公式的證明［J］.東南大學(xué)學(xué)報：自然科學(xué)版，1987，17（3）：159-161.

［5］ 方世昌.離散數(shù)學(xué)［M］.西安：西安電子科技大學(xué)出版社，2005.

［6］ 盧開澄.組合數(shù)學(xué)［M］.北京：清華大學(xué)出版社，1999.

［7］ Danie I A Cohen.Basic techniques of combinatorial theory［M］.［S.l.］：John Wiley ＆Sons Inc，1979：107-119.