组合数学(23)

1、1第八章第八章 特殊计数序列特殊计数序列8.2 差分序列和差分序列和Stirling数数(2) 前面见到的递推关系都是一个参数的。前面见到的递推关系都是一个参数的。Stirling数导出的递推关系式是两个参数的。数导出的递推关系式是两个参数的。我们已经讨论过第二类我们已经讨论过第二类Stirling(司特林司特林)数数, 本次课本次课将继续讨论将继续讨论第二类第二类Stirling数和第一类数和第一类Stirling数。数。 首先证明第二类首先证明第二类Stirling数满足数满足Pascal型递推型递推关系。关系。2定理定理8.2.4 如果如果1kp-1 则则 S(p, k) = kS(p-

2、1,k) + S(p-1, k-1) 证明：在二项式公式中，我们有下式：证明：在二项式公式中，我们有下式：111knknkn我们要证明的等式与上式有些相似。我们要证明的等式与上式有些相似。 1010),1(),(pkkppkkpnnkpSnnkpSnh和31010110101010101), 1(), 1(), 1()(, 1()(, 1(), 1(), 1(pkkpkkpkkpkkpkkpkkpkkppnkpkSnkpSnkkpSnknkpSnkknkpSnnkpSnkpSnnnn4对上式左边的求和中，用对上式左边的求和中，用k-1置换置换k后得到：后得到：11101110110101),

3、1()1, 1()1, 1(), 1()1, 1()1, 1(), 1()1, 1(), 1(), 1(pkkkpkkpkkkpkkpkkpkkpkkpnkpkSkpSnkpSnkpkSnkpSnkpSnkpkSnkpSnkpkSnkpSn5对于对于1kp-1 的每一个的每一个k比较上式与下式中比较上式与下式中nk 的系数可以看出：的系数可以看出：), 1() 1, 1(),(), 1() 1, 1(),(110kpkSkpSkpSnkpkSkpSnkpSpkkpkk与 证毕证毕 递推关系中的初值由下列给出：递推关系中的初值由下列给出： S(p, 0) = 0 (p1) ; S(p, p) =

4、 1 (p0) 根据根据p, k的值得到的值得到第二类第二类Stirling数数S(p, k)的序列的序列 6P k 0 1 2 3 4 5 6 7.01234567. 1 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 0 1 63 301 350 140 21 1 7由上表看出，左上角到右下角对角线的元素是由上表看出，左上角到右下角对角线的元素是 初值初值 S(p, p) = 1 (p0) ；左边第一列的元左边第一列的元素（除第一个外）是初值素（除第一个外）是初值S(p, 0) = 0 (p1) 。其他元素的递推关系

5、是：通过其他元素的递推关系是：通过k乘以该项上方乘以该项上方的元素再加上该项左上方元素的和。的元素再加上该项左上方元素的和。 另外我们还能得到下列结论：另外我们还能得到下列结论： S(p, 1) = 1 (p1) ； S(p, 2) = 2p-1 - 1 (p2) 1(2) 1,(ppppS8例：例： n个有区别的球放到两个有区别的盒子里，个有区别的球放到两个有区别的盒子里， 若要求第若要求第1个盒子放个盒子放k个球，第二个盒子放个球，第二个盒子放n-k个球个球(k=0,1,2.n) 方案数应是方案数应是(x+y)n展开式展开式中中xk yn-k项的系数：项的系数： 依据加法法则有：依据加法法

6、则有：knnknnnn2.210 可把上面的讨论推广到可把上面的讨论推广到n个有区别的球放到个有区别的球放到m个有区别的盒子里，要求个有区别的盒子里，要求m个盒子放的球数个盒子放的球数9 分别是分别是n1, n2, n3, . nm (n1+n2+n3+. +nm= n ) 的情况，其不同方案数用的情况，其不同方案数用 表示表示mnnnnn.321 定理定理8.2.5 第二类第二类Stirling数数S(p, k) 是将是将p个元素个元素的集合划分成的集合划分成 k个不可分辨的非空盒子的划分个不可分辨的非空盒子的划分的个数。的个数。 (不可分辨的盒子是指看起来一样不可分辨的盒子是指看起来一样)

7、证明：令证明：令S*(p, k) 是将是将p个元素的集合划分成个元素的集合划分成 k个个不可分辨的非空盒子的划分的个数。如果把集不可分辨的非空盒子的划分的个数。如果把集合划分成合划分成 p个非空盒子，显然个非空盒子，显然S*(p, p) =1 (p0) 10而且而且S*(p, 0) =0 (p1) 看上去与看上去与S(p, k)的初值一样的初值一样 我们这样划分：将前我们这样划分：将前p个正整数个正整数1,2, p, 的的集合作为要被划分的集合。把集合作为要被划分的集合。把1,2, p满足满足题意的划分有下列两种类型：题意的划分有下列两种类型： i) 使得使得 p单独在一个盒子的划分；或者单独

8、在一个盒子的划分；或者 ii) 使得使得 p不单独在一个盒子的划分。此时该盒不单独在一个盒子的划分。此时该盒子的元素多于子的元素多于1个；个；11 相当于：相当于：设有设有p个有区别的球个有区别的球b1, b2, b3,., bp, 从从 中取一个球设为中取一个球设为bp。把。把p个球放到个球放到k个盒子个盒子无一空盒的方案的全体可分为两类。无一空盒的方案的全体可分为两类。 （a） bp独占一盒，固定了一个，其方案数显独占一盒，固定了一个，其方案数显然为：然为： S*(p-1, k-1) （b） bp不独占一盒，这相当于先将剩下的不独占一盒，这相当于先将剩下的p-1 个球放到个球放到k个盒子，

9、不允许空盒，共有个盒子，不允许空盒，共有S*(p-1, k) 种方案，种方案，然后将然后将bp球放进其中一盒，从乘法球放进其中一盒，从乘法12 原理得原理得bp不独占一盒的方案数应为：不独占一盒的方案数应为： kS*(p-1, k) 再由加法原理：再由加法原理： S*(p-1, k)=S*(p-1, k-1)+ kS*(p-1, k) 证毕证毕 上面证明递推公式的过程，也就是给出构上面证明递推公式的过程，也就是给出构造所有划分方案的办法。造所有划分方案的办法。13例：红例：红, ,黄黄, ,蓝蓝, ,白四种颜色的球白四种颜色的球, ,放到两个无区放到两个无区 别的盒子里别的盒子里, ,不允许有

10、空盒不允许有空盒, ,其方案有如下其方案有如下七种七种: : S (4, 2) = 7 其中其中r表红球表红球,y表黄球表黄球,b表蓝球表蓝球,w表白球表白球, 1234567第一盒子第一盒子rybwryrbrw第二盒子第二盒子ybwrbwrywrybbwywyb14例：将红、黄、蓝、白、绿五个球放到无区别的例：将红、黄、蓝、白、绿五个球放到无区别的 两个盒子里。共有两个盒子里。共有1515种不同的方案。种不同的方案。 由递推关系由递推关系S(p, k) = kS(p-1,k) + S(p-1, k-1)得：得： S(5,2) =2S(4,2)+S(4,1)=27+1=15种。种。先把绿球取走

11、，余下的四个球放到两个盒子的方先把绿球取走，余下的四个球放到两个盒子的方案已见前面的例子。和前面一样用案已见前面的例子。和前面一样用r,y,b,w分别分别表示红，黄，蓝，白球，绿球用表示红，黄，蓝，白球，绿球用g表示，故得表表示，故得表15g不 独 占 一 盒 g独 占 一 盒 第1盒 子 第2盒 子 第1盒 子 第2盒 子 第1盒 子 第2盒 子 rg yg bg wg ryg rbg rwg ybw rbw ryw ryb bw yw yb r y b w ry rb rw ybwg rbwg rywg rybg bwg ywg ybg g rybw 第一类型第一类型 7 种种第二类型第二

12、类型 7 种种第三类型第三类型 1 种种 共计共计7+7+1=15种种16 现在使用我们对现在使用我们对第二类第二类Stirling数的组合解数的组合解 释并且求出它的计算公式释并且求出它的计算公式: 确定将集合确定将集合1,2, p分成个分成个k非空、可辨别非空、可辨别的盒子的盒子的划分数为的划分数为S#(p, k)。注意，前面我们讨。注意，前面我们讨论是论是不可辨别的盒子不可辨别的盒子的划分数为的划分数为S(p, k)。 把盒子看成是涂成红色、兰色、绿色等。把盒子看成是涂成红色、兰色、绿色等。这时不仅有考虑哪些元素一起被放进盒子里，这时不仅有考虑哪些元素一起被放进盒子里，而且要考虑放进哪些

13、盒子里，一旦知道而且要考虑放进哪些盒子里，一旦知道k个个17 盒子的内容，就可以用盒子的内容，就可以用k!种方法给种方法给k个盒子涂色。个盒子涂色。 于是：于是： S#(p, k) = k! S(p, k) 那么：那么： 通过第六章的容斥原理来求通过第六章的容斥原理来求S#(p, k) ；应该注；应该注意到，上式是基于每个盒子都是非空的前提，意到，上式是基于每个盒子都是非空的前提，如果如果k个盒子中有个盒子中有r个是空的，交换这个是空的，交换这r个空盒子个空盒子不会影响我们的划分，公式就改写成：不会影响我们的划分，公式就改写成：),(!1),(#kpSkkpS),(!),(#kpSrkkpS1

14、8 定理定理8.2.6 对每个满足对每个满足0 kp的整数的整数k，都有，都有ppitppittktkkkpStktkkpS)()1(!1),()()1(),(00#从而 证明：令证明：令U是将是将1,2, p分成个分成个k可辨别盒子可辨别盒子B1, B2, ., Bk的所有划分的集合。定义的所有划分的集合。定义k个性质个性质p1, p2, p2,., pk ，其中，其中pi为第为第i个盒子个盒子Bi是空盒的是空盒的性质。再令性质。再令Ai表示表示U的子集，它由盒的子集，它由盒Bi是空盒是空盒的那些划分组成。于是：的那些划分组成。于是：19 我们有：我们有：|U| = kp (p个元素的每个都

15、能放到个元素的每个都能放到k个盒子中去，如同填号码个盒子中去，如同填号码) 令令t是满足是满足: 0 tk的整数。盒子的整数。盒子B1, B2,., Bt是空的而是空的而Bt+1, Bt+2,., Bk可以是空的也可以不是空的。因此可以是空的也可以不是空的。因此|A1A2.At| 对于集合对于集合1,2, p的划分计数的划分计数到到 k-t 个可辨别的盒子。即等于个可辨别的盒子。即等于(k-t)p 。无论假。无论假设哪设哪t 个可盒子为空，相同的结论都成立；个可盒子为空，相同的结论都成立；kAAAAkpS.),(221#20就是说，对于就是说，对于1,2, k的每一个的每一个t-组合组合: i

16、1, i2, i3,., it 都有：都有：成立piiiitkAAAAt)(.321由第六章由第六章P107公式（公式（6-3）pkkpkppkkAAAAkAAAkkUS)(.)1(.)0(321211021证毕pktttkttttktktktktkkkkAAAAkpS)() 1() 1() 1(.321.),(003210221# 注意，上式是注意，上式是第二类第二类Stirling数的组合解数的组合解 释的计算公式，在实际使用中并不方便，求第释的计算公式，在实际使用中并不方便，求第二类二类Stirling数的值我们习惯用它的初值和递推数的值我们习惯用它的初值和递推公式公式S(p, k) =

17、 kS(p-1,k) + S(p-1, k-1)或者查表。或者查表。22 由于第二类由于第二类Stirling数相当于将数相当于将p个球放到个球放到k 个盒子里，依个盒子里，依球球和和盒子盒子是否有区别？是否是否有区别？是否允许允许空盒空盒？共有？共有222=8 种状态的种状态的方案个数方案个数列于下表：列于下表：p个球个球k个盒个盒是否空是否空方方 案案 个个 数数有区别有区别 有区别有区别 有空盒有空盒k p有区别有区别 有区别有区别 无空盒无空盒 k!S(p,k)若不考虑盒子区别时若不考虑盒子区别时得得S(p,k)，再对，再对k个盒子排列个盒子排列有区别有区别 无区别无区别 有空盒有空盒

18、S(p,1)+ S(p,2)+.+ S(p,k) (nm)S(p,1)+ S(p,2)+.+ S(p,p) (nm)23p个球个球k个盒个盒是否空是否空方方 案案 个个 数数有区别有区别 无区别无区别 无空盒无空盒S(p,k)无区别无区别 有区别有区别 有空盒有空盒C(p+k-1,p),相当于相当于p个有区别个有区别的元素取的元素取k个作允许重复排个作允许重复排列列无区别无区别 有区别有区别 无空盒无空盒C(p+(p-k)-1, p-k) = C(p-1, p-k) =C(p-1, p-1),先取先取k个球每盒个球每盒一个，余下的一个，余下的p-k个无区别的个无区别的球放到球放到k个盒子中。个

19、盒子中。无区别无区别 无区别无区别 有空盒有空盒无区别无区别 无区别无区别 无空盒无空盒数讲后再证下次课拆分)1).(1)(1 (1)(2kxxxxG数讲后再证下次课拆分)1).(1)(1 ()(2kkxxxxxG24第一第一类类Stirling数数 第二第二类类Stirling数是指出如何用数是指出如何用n0, n1, n2, np写出写出np。而第一。而第一类类Stirling数的作用刚数的作用刚好相反。它的作用是如何用好相反。它的作用是如何用n0, n1, n2,., np写写出出np。由定义：。由定义： np= n(n-1)(n-2)(n-3).(n-(p+1) =(n-0)(n-1)

20、(n-2)(n-3).(n-(p+1) 因此因此25 n0= 1 n1= n n2= n(n-1)= n2- n n3= n(n-1)(n-2)= n3- 3n2 + 2n n4= n(n-1)(n-2)(n-3) = n4- 6n3 +11n2-6n 一般地，一般地， np展开式有展开式有p个因子。乘开后得到个因子。乘开后得到n的的26 幂多项式，幂多项式， np, np-1 ,.,n1,n0, 其系数的符号正其系数的符号正 负项间；故负项间；故: np=apnnp +ap-1nnp-1+.+ a1nnp-1 + a0nn0定义：下阶乘函数定义：下阶乘函数xn的展开形式为：的展开形式为：其中

21、，其中，xk前的系数前的系数akn称为第一类称为第一类Stirling数。记为：数。记为： S1(p, k) (S的下表的下表1是为了区别第二类是为了区别第二类Stirling数数)nnnnnnkkknnxaxaaxax10027公式的系数值分别是第一类公式的系数值分别是第一类Stirling数。由展开数。由展开 式很容易得到第一类式很容易得到第一类Stirling数的初值数的初值: S1(p, 0) = 0; (p1) 和和 S1(p, 1) =1; (p0) 我我们同样们同样有第一类有第一类Stirling数数的三角形表：的三角形表：P k 0 1 2 3 4 .012345. 1 0 1

22、 0 -1 1 0 2 -3 1 0 -6 11 -6 128 因此因此第一类第一类Stirling数和第二类数和第二类Stirling数数的的 初值是一样的初值是一样的,但它们的递推关系不同。但它们的递推关系不同。定理定理8.2.8如果如果1kp-1则则: S1(p, k) = (p-1)S1(p-1, k) + S1(p-1, k-1) （红色系数部分是与第二类（红色系数部分是与第二类Stirling数的区别）数的区别）证明：由公式证明：由公式kpkkppkpkkppnkpSnnkpSn), 1()1( :),()1(1101110得到29 我们可以观察到这两个关系中有：我们可以观察到这两

23、个关系中有： np= np-1(n- (p-1)kpkkpkpkkppkpkkpkpkkpkpkkpkpkkpkpkkpppnkpSpnkpSnnkpSpnkpSnkpSpnkpSnnkpSpnnpnn), 1() 1() 1() 1, 1() 1(), 1() 1() 1(), 1() 1(), 1() 1() 1(), 1() 1(), 1() 1()1()1(110101101111011101110111011 对上式中的第一项用对上式中的第一项用k-1代替代替k后得到后得到30比较它们的系数可以看出：比较它们的系数可以看出：kpkkpkpkkppkpkkppnkpSpnkpSnnkp

24、Sn), 1() 1() 1() 1, 1() 1(),() 1(1101010 S1(p, k) = (p-1)S1(p-1, k) + S1(p-1, k-1) 对每个满足对每个满足1kp-1 的整数的整数k都成立。都成立。 与与第二类第二类Stirling数一样，第一类数一样，第一类Stirling数也数也是用与对某种事物的计数，如下定理：是用与对某种事物的计数，如下定理：31定理定理8.2.9第一类第一类Stirling数数S1(p, k)是将是将p个物体排个物体排 成成k个非空的循环排列方法数。个非空的循环排列方法数。证明：循环排列在第三章中我们介绍过，因为证明：循环排列在第三章中我

25、们介绍过，因为循环没有首尾区分，可以看成是圆圈排列，它循环没有首尾区分，可以看成是圆圈排列，它的的r-排列数与线性排列数与线性r-排列数的关系是：排列数的关系是：令令S#(p, k)是将是将p个人排成个人排成k个非空圆圈的方法数。个非空圆圈的方法数。 S#(p, p)是有是有p个人有个人有p圆圈，每个人左手牵自己圆圈，每个人左手牵自己右手，每个圆圈包含一人，故右手，每个圆圈包含一人，故:S#(p, p) = 1 (p0) rrnP),(32 还有还有S#(p, 0) = 0 (p1) ;看得出它与第一类看得出它与第一类 Stirling数数S1(p, k)有相同的初值条件。有相同的初值条件。 设排列的人编上号码设排列的人编上号码1,2,3,p。将。将1,2,3,p排成排成k个圆圈有两种类型：个圆圈有两种类型： 第一种是