资源描述：
《(最新)组合数学_第20讲（0604）-经典的递推关系》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、§5.6经典的递推关系（1）§5.6经典的递推关系5.6.1Fibonacci数列性质5.6.1：F1+F2+…+Fn=Fn+2-1性质5.6.2：F1+F3+…+F2n-1=F2n性质5.6.3：F12+F22+…+Fn2=FnFn+1性质5.6.4：Fn-1Fn+1-Fn2=(-1)n§5.6经典的递推关系（1）性质5.6.1：F1+F2+…+Fn=Fn+2-1§5.6经典的递推关系（1）性质5.6.2：F1+F3+…+F2n-1=F2n§5.6经典的递推关系（1）性质5.6.3：F12+F2
2、2+…+Fn2=FnFn+1§5.6经典的递推关系（1）性质5.6.4：Fn-1Fn+1-Fn2=(-1)n§5.6经典的递推关系（2）§5.6经典的递推关系5.6.2第一类Stirling数定义5.5定理5.7第一类Stirling数满足以下递推关系：注：这是依赖于两个参数的递推关系。令[x]n=x(x-1)(x-2)…(x-n+1)，若，则称S1(n,k)为第一类Stirling数。§5.6经典的递推关系（3）§5.6经典的递推关系5.6.3第二类Stirling数定义5.6定理5.8第二类S
3、tirling数满足以下递推关系：令[x]n=x(x-1)(x-2)…(x-n+1)，若，则称S2(n,k)为第二类Stirling数。§5.6经典的递推关系（4）§5.6经典的递推关系5.6.3第二类Stirling数定理5.9定理5.9'第二类Stirling数S2(n,k)就是n个元素的集合划分为k个不相交的非空子集的方式数目。n个有区别的球放入m个相同的盒子中，要求无一空盒的方式数即第二类Stirling数S2(n,m)。证明：设A(n,k)是n个元素的集合划分成k个不相交的非空子集的方式
4、数目。下面证明A(n,k)满足定理5.8中的递推关系式。§5.6经典的递推关系（4）给定一个n元集合{a1,a2,…,an}，将这个n元集合划分成k个不相交的非空子集可以分为互不相容的两种情况：①设{an}是k个子集合中的一个子集，于是把{a1,a2,…,an-1}划分为k-1个子集有A(n-1,k-1)种划分方式。②如果{an}不是k个子集合中的一个，首先把{a1,a2,…,an-1}划分为k个子集，这共有A(n-1,k)种划分方式。然后把an加入到k个子集合中的一个子集中去，这有k种加入方式。
5、对每一个加入方式都使集合划分成k个子集，因此方式数共有kA(n-1,k)种。由①,②并应用加法法则有：{a1,a2,…,an}划分成k个子集的方式数一共有A(n-1,k-1)+kA(n-1,k)种即A(n,k)=A(n-1,k-1)+kA(n-1,k)。§5.6经典的递推关系（4）用n+1代替上式中的n，则上式变为A(n+1,k)=A(n,k-1)+kA(n,k)。又因为将一个元素的集合划分成一个不相交的的非空子集的方式数显然是1，故A(1,1)=1，代入递推关系有A(0,0)=1。另外，我们不可
6、能把n个元素的集合的n个元素不放进任何一个集合中去，故A(n,0)=0。因此A(n,k)是满足定理5.8中的递推关系式的。故A(n,k)=S2(n,k)§5.6经典的递推关系（5）§5.6经典的递推关系5.6.3第二类Stirling数定理5.10第二类Stirling数S2(n,k)具有如下性质：S2(n,0)=0S2(n,1)=1S2(n,n)=1S2(n,k)=0(n＜k或k=0＜n)S2(n,2)=2n-1-1S2(n,n-1)=C(n,2)§5.6经典的递推关系（5）S2(n,2)=2n
7、-1-1证明：S2(n,2)表示n个有区别的球放入2个相同的盒子中，要求无一空盒的方式数。设有n个不相同的球b1,b2,…,bn,从中取出球b1，其余的n-1个球，每个都有两种选择：与b1同盒或不与b1同盒。但必须排除一种情况，即全体与b1同盒，因这时另一盒将是空盒。故实际上只有2n-1-1种方案，即S2(n,2)=2n-1-1。§5.6经典的递推关系（6）S2(n,n-1)=C(n,2)证明：S2(n,n-1)表示n个不相同的球放到n-1个相同的盒子里，不允许有空盒的方式数。故有且只有一个盒子有
8、两个球，从n个有区别的球中取2个共有C(n,2)种组合方案，故S2(n,n-1)=C(n,2)。§5.6经典的递推关系（7）§5.6经典的递推关系5.6.3第二类Stirling数定理5.10第二类Stirling数S2(n,k)具有如下性质：S2(n,0)=0S2(n,1)=1S2(n,n)=1S2(n,k)=0(n＜k或k=0＜n)S2(n,2)=2n-1-1S2(n,n-1)=C(n,2)§5.6经典的递推关系（7）解：S2(n,m)表示把n个不同的球放入m个相同的盒子，而且
