非线性递推关系举例.ppt

2.4 非线性常系数递推关系举例,错排问题 Stirling数 Catalan数,1.错排问题,定义：n个不同的元素进行排列，使得每个元素都不在原来的位置上，这样的排列称为错排。,从比较小的n开始讨论，试图找出规律。,1 2的错排是唯一的，即2 1。,1 2 3的错排有3 1 2，2 3 1。,可以看作是1 2错排，3分别与1，2换位而得的。,1 2 3 4的错排有：,第二列可以看成是4与3 1 2中每一个互换位置得到。,第三列则是4与2 3 1(1 2 3的另一个错排)中的每一个互换位置得到。,4 3 2 1，4 1 2 3，4 3 1 2，3 4 1 2，3 4 2 1，2 4 1 3，2 1 4 3，3 1 4 2，2 3 4 1。,这些错排中，第一列的可以看成是4与1，2，3互换位置，剩下的两个数字错排。,注意3 1 2是1 2 3的一个错排。,似乎可以看出得到n个元素错排有两种途径：,(1)n与某个元素互换，剩下的n-2个元素错排；,(2)前n-1个元素错排，然后对每一个错排，n与某个元素互换。,问题在于这两种途径是否无重复、无遗漏的给出了所有n个元素的错排？,答案是肯定的。,若设n个元素的错排数为Dn，则第一种途径得到的错排数为(n-1)Dn-2；第二种途径的错排数为(n-1)Dn-1。因此我们可以得到递推关系：,Dn=(n-1)(Dn-1+Dn-2)，D1=0,D2=1。,然后说明无遗漏：,对于某一个给定的错排，n一定不会落在最后一个位置，不妨假设n在第一个位置，即1原来所在的位置，接下来看1所在的位置：,(1)若1在第n个位置，则这个错排是通过第一种途径得到的。,首先说明无重复：,(2)若1不在第n个位置，不妨假设在第n个位置的数字是2，交换2和n，则前n-1个数字仍是错排。这表明这个错排是通过第二种途径得到的。,第一种途径得到的错排的特点是若n在位置k，则k必在位置n，而第二种途径的错排必没有这个性质。,因此对于错排问题，我们有如下的递推关系：,这是一个线性非常系数递推关系。,令En=Dn/n!，则,Dn=(n-1)(Dn-1+Dn-2)，D1=0,D2=1。,即,注意到E1=D1/1!=0，E0=D0/0!=1，因此有,D0=1,因此有,所以,例1 数1,2,9的全排列中，求偶数在原来位置上，其余都不在原来位置上的错排数目。,这相当于1,3,5,7,9这5个元素的错排问题，因此,例2 求8个字母ABCDEFGH的全排列中，只有4个元素不在原位置上的排列数。,4个元素的错排数为,因此答案为 C(8,4)D4=630。,2.Stirling数,定义：n个有区别的球放到k个相同的盒子中，要求无一空盒，其不同的方案数用S(n,k)表示，称为第二类Stirling数。,例如红、黄、蓝、白四种颜色的球,放到两个无区别的盒子里，不允许有空盒，其方案有：,其中rybw分别表示红、黄、蓝、白球，因此有,S(4,2)=7。,定理1：第二类Stirling数有如下性质：,性质(a)(b)(e)显然，只证(c)(d)。,(c)n个球中球1放在某个盒子中，那么对于其他n-1个球，每个球都有2种选择：与球1同盒或不同盒。,但要排除掉所有球都与球1同盒的情形(出现空盒)。,因此有：S(n,2)=2n-1-1。,(d)n个不同的球放到n-1个相同的盒子里，必定是某个盒子里有2个球，其他盒子各1个球。,由于盒子都相同，因此问题等价于从n个球中选出2个即可。所以有：S(n,n-1)=C(n,2)。,定理2：第二类Stirling数满足如下递推关系式：,选定球1，则无一空盒的方案可分为两类：,(1)球1独占一个盒子，这样的方案数为S(n-1,k-1)；,(2)球1不独占一个盒子，这相当于把其他n-1个球放到k个盒子里，要求无一空盒，然后再把球1放到每个盒子中。这样的方案数为kS(n-1,k)。,因此有定理2的结论成立。,上面定理的证明过程实际上也给出了一种构造所有方案的方法。,例如考虑把红、黄、蓝、白、绿五个球放到无区别的两个盒子里。,根据递推关系：S(5,2)=2S(4,2)+S(4,1)=27+1=15。,这15种方案可分为2类，如下表所示：,考虑n个球放入m个盒子中的问题。按照球是否有区别、盒子是否有区别、是否允许空盒分为8种情形：,(1)n个球有区别，m个盒子有区别，允许空盒时方案数为：mn。,(2)n个球有区别，m个盒子有区别，不允许空盒时方案数为：m!S(m,n)。,(3)n个球有区别，m个盒子无区别，允许空盒时方案数为：,(4)n个球有区别，m个盒子无区别，不允许空盒时方案数为：S(m,n)。,(5)n个球无区别，m个盒子有区别，允许空盒时方案数为：C(n+m-1,n)。,(6)n个球无区别，m个盒子有区别，不允许空盒时方案数为：C(n-m)+m-1,n-m)=C(n-1,m-1)。,(7)n个球无区别，m个盒子无区别，允许空盒。,中xn的系数。,这相当于把整数n拆分成最多m个整数的和。,根据Ferrers图像，这等价于把整数n拆分成一些最大数为m的整数的和。因此不同的方案数为母函数,(8)n个球无区别，m个盒子无区别，不允许空盒。,中xn的系数。,这相当于把整数n拆分成刚好m个整数的和。,根据Ferrers图像，这等价于把整数n拆分成一些最大数为m的整数的和，且m至少出现1次。,因此不同的方案数为母函数,下面简单介绍一下第一类Stirling数和第二类Stirling数的另一种定义。,则系数s(n,k)称为第一类Stirling数。,注意到：,定义：若,比较两边系数，容易得到第一类Stirling数满足的递推关系式：,则系数S(n,k)称为第二类Stirling数。,这与前面的第二类Stirling数的定义是等价的。,定义：若,可以得到第二类Stirling数满足的递推关系式：,注意到：,第一类Stirling数的显式表达式：,第二类Stirling数的显式表达式：,3.Catalan数,定义：一个凸n边形，通过不相交于n边形内部的对角线，把n边形拆分成若干三角形，不同拆分的数目记为hn，称为Catalan数。,例如当n=5时：,这表明：h5=5。,定理：Catalan数满足如下两个递推关系式：,(a)以 v1vn+1作为一个边的三角形v1vkvn+1，将凸n+1边形分割成两部分：,一部分是k边形,一部分是n-k+2边形，k=2,3,n。这里vk可以是v2,v3,vn 点中任意一点。,根据加法原则即有。,这里注意 h2=1。,如右图所示，从v1点向其它n-3个顶点v3,v4,vn-1可引出n-3 条对角线。对角线v1vk把n边形分割成两个部分。,把k从3到n-1求和即得方案数为：,把上面的v1点换成其他的v2,vn点，也有相同的结果，即方案数为,但是注意到：1.每条对角线有2个顶点；2.每个剖分都通过n-3条对角线，因此真正不同的方案数为：,Catalan数满足的这两个递推关系式,都不是线性的，因此求解方法也比较特殊。,注意到h2=1，因此第一个递推关系式可以写成,与第二个递推关系式比较，很容易得到,令En+1=nhn+1，则E2=h2=1，且nhn+1=(4n-6)hn变为,因此有,还可以利用母函数或者微分方程的方法得到这个表达式。具体过程详见课本。,例3 由表达式有h6=C(8,4)/5=14。具体如下：,例4 a1a2an表示n个不同的数的乘积。不改变这些数的顺序，只用括号表示成对的乘积，问有多少种不同的乘法方案？,设n个数的不同乘法方案为pn，则有,这里p1=1，p2=1。,令pn=hn+1，则上面的递推关系式可以写成,且h2=p1=1，h3=p2=1。,这表明，pn刚好就是Catalan数hn+1，即,以n=4为例，p4=h5=C(6,3)/4=5，即有5种乘法方案：,下面我们来建立4个数的不同乘法顺序方案与5边形的不同拆分之间的一一对应关系。,ab运算用二分树表示，两片叶子分别表示a，b，分支点为运算符，如右图：,例5 n个1和n个0组成一个2n位的2进制数，要求从左到右扫描，1的累计数不小于0的累计数，试求满足这条件的数有多少？,在2n 位上填入n个1的方案数为C(2n,n)。,从C(2n,n)中减去不符合要求的方案数即为所求。不合要求的数指的是从左而右扫描，出现0的累计数超过1的累计数的数。,不合要求的数的特征是从左而右扫描时，必然在某一奇数2m+1位上首先出现m+1个0，和m个1。,把后面的数中1，0互换，得到一个由n+1个0和n-1个1组成的2n位数。这表明一个不合要求的数对应于一个由n+1个0和n-1个1组成的2n位数。,反过来，对于一个由n+1个0和n-1个1组成的2n位数，由于0比1多两个，必定会在某个奇数位第一次出现0比1多的情形。类似的，把后面的0，1互换，即对应于一个不合要求的数。,因此，不合要求的数个数为C(2n,n+1)。,所以若设满足要求的数的个数为p2n，则,当然，这个问题本质上就是第一章介绍非降路径模型时给出的音乐会门票的例题。,即问题等价于求从(0,0)点到(n,n)点的非降路径中，不允许穿越(可以接触)对角线的路径数目。,若问题修改为要求1的累计数始终大于0的累计数(到最后一位时除外)，则问题等价于求从(0,0)点到(n,n)点的非降路径中，不允许接触对角线的路径数目。,详细过程可以参见1-3的PPT。,