组合数学幻灯片56Stirling数课件.ppt

1、5.65.6StirlingStirling数数 多项式多项式x xn n与与x(x-1)(x-2)x(x-1)(x-2)(x-n+1)(x-n+1)都都是首项系数为是首项系数为1 1的多项式，因而它们必的多项式，因而它们必能相互表示出来。但是，这种相互表示能相互表示出来。但是，这种相互表示出来是通过什么样的桥梁来联系呢出来是通过什么样的桥梁来联系呢?我我们说，这个桥梁就是本节将要讨论的们说，这个桥梁就是本节将要讨论的StirlingStirling数。数。Stirling Stirling数分为两类：第一类数分为两类：第一类StirlingStirling数与第二类数与第二类Stirling

2、Stirling数。数。一、第一类一、第一类StirlingStirling数数令令x xn n=x(x-1)(x-2)=x(x-1)(x-2)(x-n+1)(5.31)(x-n+1)(5.31)定义定义5.8 5.8 若若xxn n=(5.32)(5.32)则称则称S S1 1(n,k)(n,k)为第一类为第一类StirlingStirling数。也就数。也就是说，是说，S S1 1(n,k)(n,k)就是多项式就是多项式x xn n中的中的 x xk k的系数。显然，当的系数。显然，当nknk时，时，S S1 1(n,k)=0(n,k)=0。nkkxknS01),(定理定理5.7 5.7

3、第一类第一类StirlingStirling数满足递归关系：数满足递归关系：(5.33)(5.33)由式由式(5.33)(5.33)易得第一类易得第一类StirlingStirling数数S S1 1(n,k)(n,k)的数值表如表的数值表如表5.15.1。0)(n 0)0,(,1)0,0(0)k0,(n ),()1,(),1(11111nSSknnSknSknSkS1(n,k)n123456712345671-12-624-1207201-311-50274-17641-635-25516241-1085-7351-151751-211表表5.15.1 二、第二类二、第二类StirlingS

4、tirling数数定义定义5.95.9 若若 x xn n=(5.34)(5.34)则称则称S S2 2(n,k)(n,k)为第二类为第二类StirlingStirling数。显然，数。显然，当当nknk时，时，S S2 2(n,k)=0(n,k)=0。nkkxknS02),(定理定理5.8 5.8 第二类第二类StirlingStirling数满足递归关系：数满足递归关系：(5.35)(5.35)由式由式(5.35)(5.35)易得第二类易得第二类StirlingStirling数数S S2 2(n,k)(n,k)的数值表如表的数值表如表5.25.2。0)(n 0)0,(,1)0,0(0)k

5、0,(n ),()1,(),1(22222nSSknkSknSknS表表5.25.2kS2(n,k)n123456712345671111111137153163162590301110653501151401211定理定理5.9 5.9 第二类第二类StirlingStirling数就是数就是n n个元个元素的集合划分成素的集合划分成k k个不相交的非空个不相交的非空子集的方式数目。子集的方式数目。定理定理5.10 5.10 第二类第二类StirlingStirling数具有下列性质：数具有下列性质：1.1.S S2 2(n,n)=1(n,n)=1 S S2 2(n,k)=0 (nk(n,k

6、)=0 (nk或或k=0n)k=0n)2.S2.S2 2(n,2)=2(n,2)=2n-1n-1-1-13.S3.S2 2(n,n-1)=(n,n-1)=2n例例1 1 求把求把n n只不同的球放入只不同的球放入m m个不同个不同编号的盒子中，使得没有一个盒编号的盒子中，使得没有一个盒子为空的方式数。子为空的方式数。20!(,)(1)()minimm S n mmii例例2 2 设设m,nm,n都是正整数，都是正整数，mnmn。证明：证明：!),(21kknSkmmmkn 第二类第二类StirlingStirling数与下面定数与下面定BellBell数有着密切的关系。数有着密切的关系。定义定

7、义5.105.10 若若则称则称B Bn n为为BellBell数。显然，数。显然，B B0 0=1=1。nknknSB02),(由定理由定理5.95.9知，知，S S2 2(n,k)(n,k)就是就是n n个元素的集合划分为个元素的集合划分为k k个不相交的非个不相交的非空子集合的方式数空子集合的方式数 。于是。于是BellBell数数B Bn n就是就是n n个元素的集合划分为不相交的个元素的集合划分为不相交的非空子集的方式数。非空子集的方式数。对于对于BellBell数数B Bn n，有下面的定理。有下面的定理。定理定理5.11 5.11 BellBell数数B Bn n满足如下的递归关系：满足如下的递归关系：nkknBknB01