沈阳理工大学学士学位论文
定理3.4.6 第二类Stirling数满足S(n,k)??(i?1)S(n?k?i,i?1)
i?0?7?k?1定理3.4.7 1?k?n,k??S(n,i)k(k?1)?(k?i?1),即
ni?1?7?kknS(n,1)S(n,2)S(n,k?1)??????S(n,k) k!(k?1)!(k?2)!1!3.5 Stirling数的组合意义及应用
3.5.1 引言
利用概率论的方法系统地研究组合问题,最早由Erdls和Spencer提出。但是,这一方向的研究成果不是很多,而且主要集中在概率论方法在Ramsey理论、随机图、组合优化等方面的应用,以及在经典组合问题中,用Monte Carlo方法处理组合计数的数值解.我们发现,许多组合数及组合多项式,以后称为组合变量,包括Stirling数,Bell数,Bernouli数,分拆数以及Bernouli多项式,Hermite多项式,Bessel多项式,Gegenbauer多项式等都和随机变量的矩有关。同时,符号运算中的伞变量(umbral operator)也与概率论有密切的联系。因此,概率的方法和技巧可以在一些经典组合问题中得到广泛应用。本文只讨论Stirling数,证明两类Stirling数是随机变量和的矩,对于?an,kS(n,k),?an,ks(n,k)类型的组合建立了
nn一个统一的处理方法,我们或者能求出这种和式,或者至少也能得到一个恒等式。组合恒等式中的参数不应当仅仅看成一个常数,而应被视为一个随机变量(常数是随机变量的特例),这样我们就可以从一个简单的恒等式中推导出许多(甚至无穷多个)新的、有趣的恒等式.最后,利用中心极限定理,我们得到了k固定时,S(n,n-k)的渐进形式,它在k?3时与精确公式完全吻合。 3.5.2 预备知识
本文所涉及的概率论知识,其中主要是矩和条件期望的概念。 如果X是一个连续随机变量(下文简记为r.v),它有密度函数f(x),满足
P?a?X?b???f?x?dx,f?x??0,?f?x?dx?1.
a-?b?那么,对任何一个Borel可测函数p(x),r.vp?X?的矩定义为
Ep?X???p?x?f?x? (3.4)
-??特别地,
1)f(x)?xn时,(3.4)称为r.vX的n阶矩; 2)f(x)?x时,(3.4)称为r.vX的期望; 3)如果X,Y是两个r.v,那么
21
沈阳理工大学学士学位论文
E(XY?y)??xf?x??xY?y?dx,f?x??xY?y?
?-?是X关于事件{Y=y}的条件概率密度。
称为r.vX关于事件{Y=y}的条件期望,它是y的函数,记作μ(y),那么μ(Y)?E(XY)是一个r.v,称为X关于Y的条件期望.我们将使用如下的全数学期望公式:
E?Eg(X)Y??Eg(X)
来推导Stirling数的递推关系。
本文中,只涉及到两种常见的的连续r.v 1)均匀分布
r.vX~U[a,b],称为X服从[a,b]上的均匀分布,密度函数为
?1a?x?b,?,f(x)??b-a
其它.??0,bn?1-an?1. 所以EX?(n?1)(b-a)n2)指数分布
r.vX~e(?),??0,称为X服从参数为?的指数分布,密度函数为
?λe-?x,x?0 f(x)???0其它所以EXn?n!/λn.
当r.vX与Y独立时,它们乘积的矩等于矩的乘积:
E(f(X)g(Y))?E(f(X))E(g(Y)). (3.5) 这个性质在本文中起着重要的作用,此外,我们沿用概率论常用的符号,当一列
r.vX1,X2,?不仅是独立的,而且分布还相同,则记为X1,X2,?,i.i.d. 3.5.3 Stirling数的概率表示
定理3.5.1 如果随机变量V服从二项分布B?n,p?，则它的任意m阶原点矩为
??S?m,k??n?kpk,m?0
k?0mEVm22
沈阳理工大学学士学位论文
这里S?m,k?是第二类Stirling数,?n?k为降阶乘。
证明 我们定义降阶乘为?x?k?x?x-1???x-k?1?，则第二类Stirling数又常常被定义为：
x?n?S?n,k??x?k?0nk (3.6)
注意到降阶乘的定义以及
?i?k?0,i?k-1;?i?k?i!,i?k, ?i-k?!因此V的降阶乘的数学期望为：
E?V?k???i?kCpqinii?0nn-i??i?kni!n!?piqn-i ?i-k?!i!??n-i?!n-k?n-k?!pi-qn!kkn-ip???n?kpk ， ??n-k?!i-?k0?i-k?!?n-?i!把x??S(n,k)(x)k式中的x换为随机变量V再取数学期望，则得证。
nk?0n定理3.5.2 假设r.v序列u1,u2,?,i.i.d~U[0,1],Γ1,Γ2,?,i.i.d~Γ(1),并且r.vui 与Γj独立,则n,k?1时,
1)第一类Stirling数s(n,k)
?kn?n-k? s(n,) (3.7) k?(-1)n-?E(uΓ???uΓ)11kk?k????n-1?n-k s(n,k)?(-1)??k-1??E(u1Γ1???uk-1Γk-1) (3.8)
??n-k规定s(n,0)?s(0,k)?0,s(0,0)?1。
2)第二类Stirling数S(n,k)满足
?n?n-k? S(n,) (3.9) k??E(u???u)1k?k???23
沈阳理工大学学士学位论文
S(n,k)?1E(Γ1?2Γ2???kΓk)n-k (3.10) (n-k)!?n-1?n-k? (3.11) S(n,k)??E(u???u?1)1k-1?k-1???规定S(n,0)?S(0,n)?0,S(0,0)?1.
证明 这里仅证明2)式(3.9) S?n,k???n??n??n-k??1??1?1???????????? ??'''??????????k!i1'???ik'?n?i1i2?ik?i1???ik?n-k?k??i1i2?ik??i1?1??ik?1?诸ij'?0??n??n-k??n???n-k?i1ikikik?????????Eu?Eu?Eu?ukk? ?k???ii?i?k?k????i?i?1???12k?????1k???????n?n-k??. ??Eu???u1k?k???证毕。
式(3.7)、(3.9)和(3.10)是把两类Stirling数分别表示成某些随机变量和的矩,这种概率表示是对Stirling数的一种构造性描述,从而为研究Stirling提供了新的工具。主要结论如下:
定理3.5.3 第二类Stirling数S(n,k)和第一类Stirling数s(n,k)有以下性质:
?n?(i)S(n,1)?1, S(n,2)?2-1,S(n,n-1)???2??,S(n,n)?1.
??n-1?n?(ii)s(n,1)?(-1)n-1(n-1)!,s(n,2)?(-1)n-2(n-1)!Hn-1,s(n,n-1)?-??2??,
??s(n,n)?1,其中Hn为调和数。
?n?n-11? 证明 由(3.9)式S?n,1???Eu?n?1,显然S?n,n??1, ?1?1n???n?n-2???S?n,2???Eu?u12?2????n?n-2?n-2?n-2-ii??Eu2 ?2?????i??Eu1??i?1??????1n-2?n??????2n-1-1??2i?0?i?1?24