《组合数学3.6差分表和Stirling数》由会员分享，可在线阅读，更多相关《组合数学3.6差分表和Stirling数（26页珍藏版）》请在金锄头文库上搜索。
1、3.6 差分序列和Stirling数 n3.6.1 差分3.6.1.1 差分算子3.6.1.2 差分表3.6.1.3 移位算子3.6.1.4 算子运算3.6.1.5 牛顿公式3.6 差分序列和Stirling数n3.6.2 Stirling数3.6.2.1 第二类Stirling数的定义3.6.2.2 第二类Stirling数递归3.6.2.3 第二类Stirling数3.6.2.4 第一类Stirling数3.6.1.1 差分算子n差分算子 设序列hn(n0,1,2,)，递归定义0阶差分序列0hnhn(n0,1,2,) 1阶差分序列1hnhn+1hn(n0,1,2,) k阶差分序列 khn(
2、k-1hn) k-1hn+1k-1hn (n0,1,2,) 3.6.1.2 差分表n数列的差分表设序列hn(n0,1,2,)h0 h1 h2 h3 h4 1h0 1h1 1h2 1h32h0 2h1 2h23h0 3h1 0条对角线 3.6.1.2 差分表n序列hnn3n(n0,1,2,)的差分表0 2 10 30 68 130 2 8 20 38 626 12 18 24 6 6 60 03.6.1.2 差分表n定理3.6.1令序列hn(n0,1,2,)的一般项是n的t次多项式，即hnatntat-1nt-1a1na0则对任意n(n0,1,2,),t+1hn0 3.6.1.3 移位算子n移位
3、算子E设序列hn(n0,1,2,)，定义Ekhnhn+k(n0,1,2,)n恒等算子I设序列hn(n0,1,2,)，定义Ikhnhn(n0,1,2,)3.6.1.4 算子运算n算子运算设序列hn(n0,1,2,)，,为任意算子。定义() hnhn hn()hn(hn)3.6.1.4 算子运算n定理3.6.2 设是任意算子，则(1) II(2) EI， EI3.6.1.5 牛顿公式n定理3.6.3(牛顿公式)(约定0E0I0I)n(1) Ek(I)k (k0,1,2,)n(2) k(EI)k (k0,1,2,) 3.6.1.5 牛顿公式n牛顿公式的一个应用hn+kEkhn (k0,1,2,)在上
4、式取n0得hk (k0,1,2,) 3.6.1.5 牛顿公式nh0 nh1 nh2 nh3 nhk 3.6.1.5 牛顿公式n h0h1 h2hk 3.6.1.5 牛顿公式n例3.6.3 求n解 令数列hnn(n1)(n2)(n0,1,2,)， 其差分表为0 0 8 30 720 8 22 428 14 206 603.6.1.5 牛顿公式n故3.6.2.1 第二类Stirling数的定义n引入符号nk ，则n序列hnnp(n0,1,2,)np 0h0 1h0 ph0 3.6.2.1 第二类Stirling数的定义n第二类Stirling数S2(p,k) (k0,1,2,p)S2(p,p)1S
5、2(p,0)3.6.2.2 第二类Stirling数递归n第二类stirling数满足类pascal型递归3.6.2.2 第二类Stirling数递归n第二类Stirling数类Pascal三角形k p0 1 2 3 4 5 6 01234561 0 1 0 1 1 0 1 3 1 0 1 7 6 1 0 1 15 25 10 1 0 1 31 90 65 15 1 S2(p,k)3.6.2.3 第二类Stirling数n问 题将p个不同球放入k个相同盒中，要求各盒非空，求其不同方案数目T(p,k)。3.6.2.3 第二类Stirling数n将球1,2,p放入k个相同盒中，要求各盒非 空，建立
6、其不同方法数目T(p,k)的递归。一类 球p单独放一盒中，有T(p1,k1) 种放法。二类 球p不单独放一盒中。分两步：先把 球1,2,p1放入k个相同盒中，要求各盒 非空，有T(p1,k)种放法；再将球p加入这 k个盒中任一个，有k中加入法。乘法原则， 共有kT(p1,k)种放法。 3.6.2.3 第二类Stirling数n于是因此 S2(p,k) T(p,k)3.6.2.3 第二类Stirling数np个不同球放入k个不同盒中，要求各盒非空p个不同球放入k个相同盒中，要求各盒非空T(p,k)k个相同盒排排队 k!n因此 S2(p,k)T(p,k)3.6.2.3 第二类Stirling数n定理3.6.4 第二类Stirling数S2(p,k)满足S2(p,k)3.6.2.4 第一类Stirling数n np n(n1)(n2)(np1) S1(p,p)npS1(p,p1)np-1S1(p,pk)np-kS1(p,0)n0第一类Stirling数S1(p,k) (k0,1,2,p)显然 S1(p,p)1，S1(p,0)03.6.2.4 第一类Stirling数n定理3.6.7 第一类Stirling数S1(p,k) (k1,2,p1)满足S1(p,k)(p1)S1(p1,k)S1(p1,k1)
