组合数学 第8章

第八章特殊计数序列,8.1Catalan数,8.1Catalan数Catalan序列是其中为第n个Catalan数。,8.1Catalan数,定理8.1.1n个+1和n个1构成的2n项数列a1,a2,a2n若其部分和满足a1a2ak0k1,2,2n则称该数列是可接受的数列，否则是不可接受的数列。这种2n项数列中可接受的数列的个数等于第n个Catalan数，即,8.1Catalan数,证明Sn是由n个+1和n个1构成的2n项数列的全体，An是其中可接受的部分，Un是其中不可接受的部分。于是|Sn|An|Un|而可见，通过计算|Un|进而计算出|An|,8.1Catalan数,设由n个+1和n个1构成的序列a1,a2,a2n是不可接受的，那么必然存在最小的k，使得该序列为:a1,a2,ak-1,-1,ak+1,a2n()而a1,a2,ak-1中+1和-1的个数相等，且k是奇数。在序列()中，前k个项的每一项改变符号，则得:-a1,-a2,-ak-1,1,ak+1,a2n()注意到()是含有n个+1和n个1的不可接受的序列，所以()是一个含有(n+1)个+1和(n-1)个-1的序列(注意)，反之亦然。而具有性质()的序列有所以,8.1Catalan数,3.所以,8.1Catalan数,对于Catalan数的递推关系，由于所以于是有递推关系进一步，通项是的数列称为拟-Catalan数。并且,8.1Catalan数,例设a1,a2,an是n个数。定义这些数的一种乘法格式是指a1,a2,an之间的一种乘法运算的方案。计算n个数的不同乘法格式的个数。分析设hn是n个数的不同乘法格式的个数。则hn=22(n-2)hn-1+2hn-1从而hn=(4n-6)hn-1n2由此可见,8.1Catalan数,由此可见，对凸(n+1)边形区域通过插入在区域内不相交的对角线而分成三角形区域的方法数与给定顺序的n个数的乘法格式数相同。即,8.2差分序列和Stirling数,8.2差分序列和Stirling数,8.2差分序列和Stirling数,定理8.2.1设序列的通项是n的p次多项式：则对于所有的n0，必有证明对多项式的方次p实施数学归纳法。,8.2差分序列和Stirling数,差分表的线性性：设gn和fn分别是两个序列的通项，那么，对于任何常数c,d来说，对于每个整数p0均成立。,8.2差分序列和Stirling数,差分表的第0行上的元素是h0,h1,h2,hn,。它们决定了整个差分表的所有元素的值。另一方面，差分表的第0条对角线上的元素是,它们也同样可以决定整个差分表的所有元素的值。,8.2差分序列和Stirling数,定理8.2.2其差分表的第0条对角线等于c0,c1,c2,cp,0,0,0,(其中cp0)的序列的通项是满足：的关于n的p次多项式。,8.2差分序列和Stirling数,证明,由此可见hn可以表示的某种表达式。即c0，c1,c2,c3,cp的某种表达式。此即,8.2差分序列和Stirling数,例对于通项为的序列。我们有h0=1,h1=3,h2=17,h3=49,h4=105,计算差分表有137491052143256121824660由于hn是n的3次多项式。且其差分表的第0条对角线上的元素是1，2，12，6，0，因此由此我们可以证明,8.2差分序列和Stirling数,定理8.2.3设序列h0,h1,h2,hn,的差分表上第0条对角线上的元素是c0,c1,c2,cp,0,0,(cp0)则该序列的部分和可表示为：,8.2差分序列和Stirling数,8.2差分序列和Stirling数,8.2差分序列和Stirling数,关于第一类Stirling数。我们希望找出n0,n1,n2,np表示np的方法。因为np=(n-0)(n-1)(n-2)(n-(p-1)即np是含有n的幂np,np-1,n1,n0=1的多项式。我们现在的问题变为求这个多项式每项的系数。若令s(p,k)是项nk的系数的绝对值。则我们称s(p,k)(0kp)是第一类Stirling数。显然s(p,0)=0(p1)s(p,p)=1(p0),8.2差分序列和Stirling数,定理8.2.8如果1kp1，则s(p,k)=(p-1)s(p-1,k)+s(p-1,k-1),8.3分拆数,8.3分拆数设n是一个正整数，若存在正整数的集合n1,n2,nk(其中1kn，nin)使得n1n2nkn则称n1,n2,nk是n的一个分拆。如果n的一个分拆含有an个n，an-1个(n-1),a2个2和a1个1。即nnan+(n-1)an-1+2a2+1a1则将该分拆记作,8.3分拆数,例1