沈阳理工大学学士学位论文
?n?n?n-1??n???, ??S?n,n-1???Eu???u???n-1?n-1?1??2???2?由(3.10)式也可以得到相应的值。 由(3.7)式s?n,1???-1?n-1?n?n-1n-1???????n-1?!,显然s?n,n??1, Eu??-1?1?11??n-2?s?n,2???-1???n?n-2???Eu??u?22?11?2?n-1??-1???-1?n-2?n-1?!?1??-1?n-2?n-1?!Hn-1
k?1kn-2?n-1?!Hn-1?n??n?????s?n,n-1???-1??Eu????u??-n-1n-1?n-1?11?2?? ????文献[9]根据引理,运用概率技巧重新得到了有关两类Stirling数的递推公式
S(n,k)?S(n-1,k-1)?kS(n-1,k)
和
s(n,k)?s(n-1,k-1)-(n-1)s(n-1,k).
另外我们还可以重新得到下面的递推公式: 定理3.5.4 S(n,k)??kn-mS(m-1,k-1).
m?kn下面简单给出该递推公式的推导过程: 记Sk-1?Γ1?2Γ2???(k-1)Γk-1,由(3.75)式
S(n,k)?1E(Γ1?2Γ2???kΓk)n-k (n-k)!?n-k?n-k?n-k-j1j???E????Sk-1?k?k??j(n-k)!?j?1??????kjj?0n-kn-k11-j-(k-1)ESkn--1?n-k-j?!
??kjS(n-1-j,k-1)j?0n??kn-mS(m-1,k-1)m?k此外我们还可以发现如下一些新的递推公式。
25
沈阳理工大学学士学位论文
定理?15?3.5.5 第二类Stirling数S(n,k)和第一类Stirling数s(n,k)满足下列递推关系: kS(n,k)??n??1) ??m??S(m,k-m?k-1??n-1n-1?n-k?S?n,k?????m-k?1?S?m,k-1???n-m?kn-mS?m-1,k-1??
m?k ks?n,k??n-1m?k-1?n-m-1?????-1n-m-1!??n-2n??s?m,k-1? ??m?n-m??n??n??-1??s?n,k?????n-m??n-m?!??m-1??s?n-1,k-1?-?m-k?1??n-m-1?!??m??s?m,k-1?? ??kn-km?k??????3.5.4 渐进与估计
这一节我们利用概率论的技巧给出两类Stirling数的估计,首先介绍一个概率不等式. Minkowski 不等式 如果EXpp??,EYp1p??,1?p??,则
p1p{EX?Y}?{EX}?{EY}p1p
定理3.5.5 当n,k?1,
(-1)n-ks(n,k)?(n-1)!S(n,k)
(k-1)!kn-k证明 当?1,?2,?,i.i.d~??1?时,r.v?1??2????k的密度函数为
f?x??1xk-1e-x,x?0. ?k-1?!所以
E??1????k??k?k?1???k?r-1??r?k?r-1?!. ?k-1?!因为r.vui与?j的独立性,由定理(3.5.2),
E?u1???uk??n-k??1???k?n-k?
?n-1?!?n???k???k-1?!??S?n,k?.
????1n-k??n?n-k??????E??1???k????Eu???u??k?1??n????k???????k????????而由Minkowski不等式
26
沈阳理工大学学士学位论文
E?u1???uk??n-k??1???k?n-k?
n-k?E??u1?1???uk?k???u1?2???uk?1???u1?3???uk?2?????u1?k??uk?k-1??
?n-k??E?u1?1???uk?k????1n-k?E?u1?2???uk?1??1n-kn-k???E?u1?k???uk?k-1??1n-kn-k????n-k
?????????1n-k???k-1?s?n,k????n??????k????????????即?-1?n-k1n-k?????????n-kkn-k?-1?n-ks?n,k?, ??n???k????s?n,k???n-1?!S?n,k?. ?k-1?!kn-k利用定理3.5.2和中心极限定理,我们还能得到当k固定时,S?n,n-k?的渐近行式,为方便记,我们把S?n,n-k?化为S?n?k,n?的形式。 定理?9?3.5.6 任给固定的k?1,当n??时,
(n?k)!?n?k1?S(n?k,n)~???2??(k-2nl)!l!(6n)l. n!??l?03.5.5 Stirling数的组合意义
1)由k个轮换构成的n阶置换的个数为s(n,k)。 2)恰可表示成k个互不相交的轮换乘积的n元置换共有(-1)n?1s(n,k)个。 3)把n件相异物分别放到k个相同盒中使得无一盒空的不同放法共有S(n,k)种。
?k?1k?1n?4)把n元集划分成k个非空子集的方法数为S(n,k)??(?1)j?。 (k?j)??k!j?0?j?5)n元集无序拆分为k个非空子集的方法数为S(n,k)。
6) ①n个不同球,放入m个相同的盒中,盒非空,其放法数为S(n,m)。 ②n个不同球,放入m个不同的盒中,盒非空,其放法数为m!S(n,m)。
27
沈阳理工大学学士学位论文
4 其他几种常见的组合数
4.1 Fine数
4.1.1引言
由于Fine数和格路有着紧密的联系,所以在介紹Fine数之前,我们先来简单了解一些格路的相关知识。
在平面直角坐标系中,横坐标和纵坐标都为整数的点称为平面格点,平面格路径是指在所有的平面格点中,从一点到另一点走格点的路,格路径的长度是指其所走的路的步数。我们这里研究的都是平面格路径,下面都简称为路径。一条长度为n的格路径也可以看做一个n维的向量v??v1,v2,?,vn?,这里vi?Z2,vi?1-vi表示这条路径所走的步法之一。
格路径是组合数学中非常重要的一个概念,因而有关格路径的研究在组合数学中一直占据着非常重要的位置,这是由于格路径不仅可以作为重要的模型来描述其他的组合统计量,像树,有禁排列,正交多项式,连分式等,也可以作为证明组合恒等式的重要工具,并且还在其他数学分支比如概率论,统计学,随机过程等有着广泛的应用.另外,格路径与生物信息学也有着很密切的联系。
在计数组合数学的研究中,对格路径所走的步作不同的限制即得到不同类型的格路径。格路计数只要是研究这些不同类型的格路的数目和性质。Dyck格路是其中最典型的一类格路径,它与计数组合数学中的很多经典的序列有着很密切的联系, 下面我们先来介绍以下什么叫Dyck格路。 4.1.2 Dyck格路与Catalan数
定义4.1.1 一条2n长的Dyck格路是指在Z2中,从原点(0,0)出发到(2n,0),由(1,1)方向的上升步和(1,-1)方向的下降步组成的,始终在x轴上方的一条路径.从(0,0)出发到(2n,0)的Dyck格路记做n-Dyck格路。
为了更好地理解定义,我们画出n=2和n=3时所有的Dyck格路
28