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