发布时间 : 星期二 文章组合数学中常见的计数方法更新完毕开始阅读
沈阳理工大学学士学位论文
?n?k?n?n-1???n-k?1?若k?1 ??1若k?0?我们注意,?n?k与P?n,k?相同,即n个不同物体的k-排列数(见文献[11]3.2节),但是,现在希望用不太麻烦的记号?n?k.我们还注意到
?n?k?1??n-k??n?k
由于
?n?n?n-1???n-k?1??n?k? ??k???k!k!??得到
?n?k因此,公式(3.1)可以改写为
np?c?p,0?p?n??k!??k??
???n?00!?c?p,1??n?1???c?p,p??n?p1!p!
??c?p,k?k?0p?n?kk!??c?p,k??n?kk!k?0
现在我们引入数
S?p,k??c?p,k? ?0?k?p?
k!则公式(3.1)变为
np?S?p,0??n?0?S?p,1??n?1???S?p,p??n?p
??S?p,k??n?k
k?0p刚刚引入的数S?p,k?叫做第二类Stirling数。 3.2.2 几个计算公式
定理?11?3.2.1 如果1?k?p-1,则
17
沈阳理工大学学士学位论文
S?p,k??kS?p-1,k??S?p-1,k-1?
定理?11?3.2.2 第二类Stirling数S?p,k?是将p个元素的集合划分成k个不可辨别的非空盒的划分的个数。 引理3.23 n?4时,
34 S(n,n?2)?Cn?3Cnn?6时,
456S(n,n?3)?Cn?10Cn?15Cn
n?8时,
5478S(n,n-4)?Cn?25Cn?105Cn?105Cn
3.2.3 性质
性质1 S(n?1,k)??(?1)i[n]iS(i,k?1)
i?01k性质2 S(n,k)??(?1)k!i?0性质3 S(n,2)?2n?1i?k?n??,0?k?n (k?i)?i????n?3n?1?1n?1? ?1,S(n,3)??2,S(n,n?1)????2?2?3.3 第一类Stirling数
3.3.1 定义
第二类Stirling数指出如何利用?n?0,?n?1,?,?n?p写出np.第一类Stirling数的作用则相反.它告诉我们如何用n0,n1,?,np写出?n?p.由定义
?n?p?n?n-1??n-2???n-p?1?
??n-0??n-1??n-2???n-?p-1?? (3.2) 因此
i) ?n?0?1 ii) ?n?1?n
18
沈阳理工大学学士学位论文
ii) ?n?2?n?n-1??n2-n
iv) ?n?3?n?n-1??n-2??n3-3n2?2n
v) ?n?4?n?n-1??n-2??n-3??n4-6n3?11n2-6n
一般地,公式(3.2)右边的乘积有p个因子.如果将其乘开,就得到含有n的幂的多项式,其系数的符号正负相间;就是说,得到形如
?n?p?s?p,p?np-s?p,p-1?np-1????-1?p-1s?p,1?n1??-1?ps?p,0?n0
???-1?k?0pp-ks?p,k?nk (3.3)
的表达式.第一类Stirling数就是出现在公式(3.3)中的系数
s?p,k? ?0?k?p?
和
s?p,p??1 ?p?0?
因此,第一类Stirling数满足与第二类Stirling一样的初始条件。但是,它们满足不同的递推关系。 3.3.2几个计算公式
定理?11?3.3.1 如果1?k?p-1,则
s?p,k???p-1?s?p-1,k??s?p-1,k-1?
定理?11?3.3.2 第一类Stirling数s?n,p?是将p个物体排成k个非空的循环排列的方法数。 定理?7?3.3.3 n?3时,
s(n,n?2)?n(n?1)(n?2)(3n?1),
24n2(n?1)2(n?2)(n?3)s(n,n?3)??
48定理?7?3.3.4 n?8时,
n(n?1)(n?2)(n?3)(n?4)(15n3?30n2?5n?2)s(n,n?4)?
242?1019
沈阳理工大学学士学位论文
3.3.3 性质
性质1 s(n?1,k)??(?1)i[n]is(n?i,k?1)
i?0?n?1性质2 s(n,2)?(?1)(n?1)!?,s(n,n?1)????2?? kk?1??nn?1性质3
?s(n,k)?n!;?s(n,k)?0,n?1;?s(n,k)xk?1k?0k?0nnnk?[x]n
3.4 第一类Stirling和第二类Stirling数的关系式
组合数学中的许多问题是数学中的精华,组合数学的应用也涉及到自然科学的许多领域,本文给出第一类Stirling数和第二类Stirling数的独立计算公式。
定理3.4.1对于任意的正整数n,有s(1,1)?1, s(n,n)?1,k?n时,s(n,n-k)?(-1)kMkn ,其
?0??0(n)中Mk是矩阵????0?时,s(n,k)?0 。
01?0?0???0?n-1s(n,1)?(-1)(n-1)! ,k?n的k阶主子式之和.特别地,?????n-1??2定理3.4.2 对于任意的正整数n,有S(n,n)?1,S(n,n-1)?-s(n,n-1)?Cn ,而当1?t?n?1时,?S(n,n?k)s(n?k,n?t)?0
k?0t引理3.4.3 第一类Stirling数满足递归关系
s(0,0)?1,s(n,0)?0? ,(n?0,k?0) 。 ?s(n?1,k)?s(n,k?1)?nS(n,k)1?引理3.4.4 第二类Stirling数满足递归关系
S(0,0)?1,S(n,0)?0? ? , (n?0,k?0)。 ?S(n?1,k)?S(n,k?1)?kS(n,k)定理3.4.5 第一类Stirling数满足s(n,k)???(n?k?i)s(n?k?i,i?1)
i?o?7?k?120