斯特林数综述

1斯特林数综述作者杨允东指导教师马铃（湛江师范学院数学与计算科学学院，湛江524048）摘要：假设已经得到一个含参数的恒等式。若不再把参数仅仅限制为常数，而是看作随机变量，对其两端取数学期望就产生了新的恒等式.这个随机变量取不同的分布将导致这些新恒等式的组合意义也完全不同。关键词：斯特林数;递推公式;组合意义;概率表示SummaryOfTheStirlingNumberYangYunDondSchoolofMathematicsandComputationScience,ZhanjiangNormalUniversity,Zhanjiang,524048ChinaAbstract：Supposethatwegetanidentitywithparameter.Ifwetaketheparameterasrandomvariables,insteadofconstant.Differentdistributedofrandomvariablesmakeallsenseofnewidentitycompletelydifferent.Keywords：Stirlingnumber;Recurrenceformula;Combinationofsignificance;Probabilisticrepresentations1斯特林数的定义以及递推公式在组合数学中，斯特林数（Stirlingnumber）指两类数，分别是第一类斯特林数和第二类斯特林数。1.1第一类斯特林数第一类斯特林数是有正负的，其绝对值是包含N个元素的集合分作K个环排列的方法数目。设x为实变元,令0()1,x则()(1)(2)(1)nxxxxxn…(1,2,n…）(1)把()nx叫做实变元x的n次降阶乘，把上式()nx的展开式中kx的系数记做1(,)Snk，称为第一类斯特林(Stirling)数。第一类斯特林数具有递推公式2111(1,)(,1)(,),1snksnknsnknk(2)特别地1(,)1snn0n；1(,0)0sn1n。由第一类斯特林数的递推公式以及边值条件，我们可以得到一个由第一类斯特林数组成的无限下三角矩阵，整理如下1010110231(,)0611610245035101012027422585151snk第二图1图21.2第二类斯特林数第二类斯特林数是把包含N个元素的集合划分为非空的K个子集的方法的数目，记为2(,)Snk。Ex将四个相同的球分别标志为1、2、3、4号，放置在两个不同的盒子，不允许空盒。其方案有如下几种表1方案一二三四五六七盒112341、21、31、4盒22、3、41、3、41、2、41、2、33、42、42、3则有2(4,2)7s第二类斯特林数递推公式222(1,)(,1)(,)snksnkksnk11nk(3)特别地322(,)1;(,0)0,(0,1,2,3)snnsnn为方便记，令2(,)0,()snkkn。由第二类斯特林数递推公式及初值条件，可以构造利用第二类斯特林数组成的无限下三角矩阵，如下21111311761(,)115251011319065151163301350140211snk图3图4上述图1和图3给出了两类斯特林数的矩阵,若记1S左上角的n+1阶主子方阵1S=ijx(,0,1,2,)ijn,则可证由相应的第二类斯特林数2(,)Snk组成的矩阵2S互逆.即121nSSI2斯特林数的组合意义定理1K个互不相交的轮换乘积的N元置换共有1(,)nkSnk（-1）个。证明设恰可表成K个互不相交的轮换乘积的N元置换共有g(n,k)个。当1nk时,这g(n,k)个N元置换可分成下述两类:（1）n所在的轮换是1-轮换的n元置换。属于此类的置换共有g(n-1,k-1)个。（2）n所在的轮换不是1-轮换的n元置换。不妨先做恰可标称k个互不相交的轮换乘积的n-1元置换,有g(n-1,k)种方法,然后把n放到这n-1元置换的一个轮换中,使得最小元仍然排在轮换的首位,有n-1种方法。于是由乘法原则,属于此类的n元置换有(1)(1,)ngnk个。再由加法原则,得4(,)(1,1)(1)(1,),(1gnkgnkngnknk）(4)于是n+k111(,)(1,1)(1)(1,)nknkgnkgnkngnk（-1）（-1）（-1）(5)不妨令n+k(,)(,)hnkgnk（-1）则有(,)(1,1)(1)(1,),(1hnkhnkngnknk）(6)即(1,)(,1)(,),(1hnkhnknhnknk）(7)易知1+1(1,1)(1,1)1hg（-1）,0(,0)(,0)0,(1)nhngnn（-1）综上所述,得h(n,k)与1(,)Snk递推关系及初始条件都相同。故而1(,)(,)(,)nkgnkhnkSnk（-1）(8)即(,)(1,1)(1)(1,)gnkgnkngnk定理2:把n元集分为k个非空子集的方法数1201(1)()()!kjknjjSkjk（n,k）=3斯特林数的一些应用3.1斯特林数的概率表示首先,我们引入两种经典分布——均匀分布和标准指数分布。53.1.1均匀分布随机变量-U(a,b)称服从[a,b]上的均匀分布，的概率密度函数为1()Pxba()axb。的n阶矩阵，即的数学期望11111nnbnnabaExdxbanba(9)特别地(0,1)的n阶矩阵为11n3.1.2标准指数分布随机变量~(1)，称服从标准指数分布，密度函数()xPxe，而n阶矩阵为!n。定理假设两组独立分布随机变量序列12,,~(0,1)U和12,,(1)，且,ij也相互独立，则对任意1k1n和有212(,)()()nnkkkSnkE（10）121121(,)()(1)nnkkkSnkE（11）2121(,)(2)()!nkkSnkEknk（12）特别地,有22(,0)(0,)0SnSk;2(0,0)1S11122(,)(1)()()nknnkkkkSnkE（13）111112211(,)(1)()()nknnkkkkkSnkE（14）此外,特别地有1(0,0)1S11(,0)(0,)0SnSk上述10到14式子给出了斯特林数的概率表示,那么是否可以用其概率表示来推导出斯特林数的递归关系呢?对于第二类斯特林数,当固定1kS时,随机111~(,1)kkkkkSSUSS6根据212(,)()()nnkkkSnkE得到1121(1,)()()nnkkkkSnkES1111()()/nnkkkkkESS111(1)=nknkKkSSnk（）E（15）所以有12221111(,)(1,1)1(1,)()()()()nknnkkSnkSnkSnknk（16）即得第二类斯特林数的递归关系222(1,)(,1)(,)snksnkksnk一般来说,若我们能将一些组合数或多项式表成定理10、11的形式,利用简单的概率性质就可以得到一些新的结果.Ex当~(0,1)U时有(1)~(0,1)U所以112(,)()[(1)(1)(1)]nknkkSnkEk10()(1)(,)nknnkiiiikSnik（17）下面我们假设已经得到一个含参数的恒等式,若不再把参数仅仅限制为常数,而是看做随机变量,对其两端取数学期望就产生了新的恒等式.这个随机变量取不同的分布将导致这些新恒等式的组合意义也完全不同.给出一个关于第二类斯特林数的恒等式.2200!(,)(1)!(1,1)(1)nnknkkkkkSnkkSnk（18）一般情况下将参数取实数值,,若把它看做一个随机变量,该恒等式仍成立①若令,对恒等式两端取数学期望.则2200!!(1)(,)(1)(1,1)11nnknkkkkkSnkSnkkk（19）7即2120(1)!(2,1)0nkkkSnk(20)②若令12,考虑调和数nH的概率表示112(1),1nnHnEn则等式(19)式蕴含了22200!!(1)(,)(1)(,)1(1)nnnkkkkkkSnkSnkkk（21）③若令()0.5iXYx。其中21i，X,Y独立分布于211,2kxiXYk综合()()0.5,0nnBxEiXYxn。（贝努力多项式的概率表示）（22）则等式（1）还蕴含了2200!(,)()(1)!(1,1)(1)nnnkkkkkkSnkBxkSnkBx（23）3.2斯特林数和自然数前m项n次方的求和公式引理1当1knm时,1222221(,)(,1)(,2)(,)nnknmmmmkmpSnkpSnpSnpSnn（24）引理2.对任何正整数1m,1k有1111kmkmjjppk（25）对任何整数1m和1n,有1123mnnnnnjmj111(,)1knmkpSnkk111110[(1)()]nkiinkkmkiCkiC(26)8由引理1可知21(,)nnkjkjSnkp,由引理2知1111kmkmjjppk,所以1123mnnnnnjmj11211(,)1knnmkjpSnkk211(,)nnkjkjSnkp1121(,)1knmkpSnkk111101[(1)()]!1knkiinmkkipCkikk111110[(1)()]nkiinkkmkiCkiC（27）例如,有211(1);2mmjmmjC（28）223111(1)(21)2;6mmmjmmmjCC（29）3232341111(1)(691)6630mmmmjmmmmmjCCC（30）……3.3斯特林数与n元集合m覆盖记n元集合1,2,,nNn.设A为集合,以A表示集合A中元素的个数。定义如果n元集合nN的k个子集12,,,kAAA满足下述条件:1),1iAik,92),1ijAAijk3):,1,1iiAlAlnmlm称nN的无序子集族12,,,kAAA是n元集合nN的一个k组n覆盖。当m=1时，n元集合的k组2覆盖(即双覆盖)的个数就是第二类斯特林数2(,)Snk。因此，n元集合的k组m覆盖的个数可看做是第二类斯特林数的推广。以c(n,k)记n元集合nN的k组2覆盖(即双覆盖)的个数,以d(n,k)记n元集合nN的k组3覆盖的个数.这里给出c(n,3)和c(n,4)的公式。11(,3)(31)2nCn,121(,4)(31)(21)2nnCn(31)至此,我们试验证关于5组3覆盖,有递推关系1122(1,5)10(,5)(4322)3(1,4)3(1,3)nndndnSnSn(32)及计数公式214223512(,5)10432)310[(,4)(,3)]3669nnnnnrrdnSrSr(33)证设12345,,,,AAAAA是n+1元集合1nN