組合數(shù)學3.6差分表和Stirling數(shù).ppt

3.6 差分序列和Stirling數(shù),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數(shù),3.6.2 Stirling數(shù) 3.6.2.1 第二類Stirling數(shù)的定義 3.6.2.2 第二類Stirling數(shù)遞歸 3.6.2.3 第二類Stirling數(shù) 3.6.2.4 第一類Stirling數(shù),3.6.1.1 差分算子,差分算子 設(shè)序列hn(n0,1,2,)，遞歸定義 0階差分序列0hnhn(n0,1,2,) 1階差分序列1hnhn+1hn(n0,1,2,) k階差分序列 khn(k-1hn) k-1hn+1k-1hn (n0,1,2,),3.6.1.2 差分表,數(shù)列的差分表 設(shè)序列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 差分表,定理3.6.1令序列hn(n0,1,2,)的一般項是n的t次多項式，即 hnatntat-1nt-1a1na0 則對任意n(n0,1,2,),t+1hn0,3.6.1.3 移位算子,移位算子E 設(shè)序列hn(n0,1,2,)，定義 Ekhnhn+k(n0,1,2,) 恒等算子I 設(shè)序列hn(n0,1,2,)，定義 Ikhnhn(n0,1,2,),3.6.1.4 算子運算,算子運算 設(shè)序列hn(n0,1,2,)，,為任意算子。定義 () hnhn hn ()hn(hn),3.6.1.4 算子運算,定理3.6.2 設(shè)是任意算子，則 (1) II (2) EI， EI,3.6.1.5 牛頓公式,定理3.6.3(牛頓公式) (約定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 (k0,1,2,) ,3.6.1.5 牛頓公式,h0 h1 h2 h3 hk ,3.6.1.5 牛頓公式,h0h1 h2hk ,3.6.1.5 牛頓公式,例3.6.3 求 解 令數(shù)列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數(shù)的定義,引入符號nk ，則 序列hnnp(n0,1,2,) np 0h0 1h0 ph0 ,3.6.2.1 第二類Stirling數(shù)的定義,第二類Stirling數(shù) S2(p,k) (k0,1,2,p) S2(p,p)1 S2(p,0),3.6.2.2 第二類Stirling數(shù)遞歸,第二類stirling數(shù)滿足類pascal型遞歸,3.6.2.2 第二類Stirling數(shù)遞歸,第二類Stirling數(shù)類Pascal三角形,S2(p,k),3.6.2.3 第二類Stirling數(shù),問 題 將p個不同球放入k個相同盒中，要求各盒非空，求其不同方案數(shù)目T(p,k)。,3.6.2.3 第二類Stirling數(shù),將球1,2,p放入k個相同盒中，要求各盒非空，建立其不同方法數(shù)目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數(shù),于是 因此 S2(p,k) T(p,k),3.6.2.3 第二類Stirling數(shù),p個不同球放入k個不同盒中，要求各盒非空 p個不同球放入k個相同盒中，要求各盒非空 T(p,k) k個相同盒排排隊 k! 因此 S2(p,k)T(p,k),3.6.2.3 第二類Stirling數(shù),定理3.6.4 第二類Stirling數(shù)S2(p,k)滿足 S2(p,k),3.6.2.4 第一類Stirling數(shù),np n(n1)(n2)(np1) S1(p,p)npS1(p,p1)np-1 S1(p,pk)np-kS1(p,0)n0 第一類Stirling數(shù)S1(p,k) (k0,1,2,p) 顯然 S1(p,p)1