错排问题catalan数ppt课件.ppt

《错排问题catalan数ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、2.10错排问题定义:n个有序的元素应有n!个不同的排列,如若一个排列使得所有的元素不在原来的位置上,则称这个排列为错排,有的叫重排。以1，2，3，4四个数的错排为例，分析其结构，找出规律性的东西来。12的错排是唯一的，即21。即123的错排有312，231。这二者可以看作是12错排，3分别与1，2换位而得的.2.10错排问题1234的错排有4321，4123，4312，3412，3421，2413，2143，3142，2341。4321，3412，2143。第一列是4分别与1，2，3互换位置,其余两个元素错排.由此生成的。2.10错排问题第2列

2、是4分别与3，1，2（123的一个错排）的每一个数互换而得到的。即2.10错排问题第三列则是由另一个错排231和4换位而得到,即上面的分析结果，实际上是给出一种产生错排的结果。设n个数1，2，…，n错排的数目为Dn,任取其中一数i,数i分别与其他的n-1个数之一互换，其余n-2个数进行错排，共得(n-1)Dn-2个错排。另一部分为数i以外的n-1个数进行错排，然后i与其中每个数互换，得(n-1)Dn-1个错排。2.10错排问题综合以上分析结果得递推关系Dn=(n-1)(Dn-1+Dn-2)，D1=0,D2=1(2-10-1)它是一非常系数的递推关

3、系.D0=12.10错排问题一种解法:由于D1=0,D0=1故得关于Dn的递推关系2.10错排问题另一种解法:2.10错排问题令2.10错排问题2.10错排问题例1：数1,2,…,9的全排列中，求偶数在原来位置上，其余都不在原来位置上的错排数目。解：这相当于1,3,5,7,9这5个数的错排问题例2：求8个字母ABCDEFGH的全排列中，只有4个元素不在原位置上的排列数。2.11Catalan数Catalan数的递推关系是非线性的,许多有意义的计数问题都导致这样的递推关系.定义：一个凸n边形,通过不相交于n边形内部的对角线,把n边形拆分成若干三角形

4、,不同拆分的数目用hn表之，称为Catalan数.图2-11-1hn=51.递推关系定理1：2.11Catalan数以v1vn+1作为一个边的三角形v1vkvn+1，将凸n+1边形分割成两部分，一部分是k边形,一部分是n-k+2边形，k=2,3,…n.即vk点可以是v2,v3,…,vn点中任意一点图2-11-2证明(a)的证明：如图所示，2.11Catalan数2.11Catalan数依据加法法则有从v1点向其它n-3个顶点{v3,v4,…,vn-1}可引出n-3条对角线。对角线v1vk把n边形分割成两个部分，因此图2-11-3(b)的证明：如图

5、所示2.11Catalan数以v2,v3,…,vn取代v1点也有类似的结果。但考虑到对角线有两个顶点，同一对角线在两个顶点分别计算了一次，以v1vk对角线作为拆分线的方案数为hkhn-k+2,vk可以是{v3,v4,…,vn-1}中任一点，对所有这些点求和得2.11Catalan数(2-11-3)式并不给出剖分数，无疑其中是有重复的。其重复度是由于一个凸n边形的剖分有n-3条对角线，而对其每一条边计数时该剖分都计数了一次，故重复了n-3次，即该式给出的结果是hn的n-3倍。2.11Catalan数(2-11-1)式和(2-11-2)式都是非线性递

6、推关系.2.11Catalan数由(2-11-1)式及h2=1,故得2.Catalan数计算公式2.11Catalan数由整理得令2.11Catalan数即2.11Catalan数2.11Catalan数设3.母函数方法2.11Catalan数2.11Catalan数由二项式定理2.11Catalan数后面将看到只有取才有意义.2.11Catalan数中项的系数为即2.11Catalan数的系数为正xxxG2411)(--=且得2.11Catalan数同样可推出令从递推关系4.微分法2.11Catalan数2.11Catalan数2.11Cat

7、alan数即2.11Catalan数5.举例2.11Catalan数图2-11-42.11Catalan数例2.为n个数，的乘积,依据乘法的结合律,不改变其顺序,只用括号表示成对的乘积.试问有几种不同的乘法方案?例1.,见图2-11-42.11Catalan数令pn表示n个数乘积的n-1对括号插入的不同方案数.令故得而且即为Catalan数故2.11Catalan数以n=4为例P4是Catalan数h5，下面建立(2-11-4)式中不同的乘法顺序和一个5边形不同拆分的一一对应关系，如图(2-11-6)2.11Catalan数ab运算用二分树表示

8、，两片叶子分别表乘数和被乘数，分支点为运算符，如图图2-11-52.11Catalan数2.11Catalan数2.11Catalan