第8章特殊计数序列讲稿.ppt

第8章 特殊计数序列 主要内容•8.3 分拆数•8.4一个几何问题•8.5格路径和Schroder数8.3 分拆数•分拆数：整数分拆——正整数n分解成若干正整数的和 •实质：划分•举例：• 1： 1；• 2： 2；1+1；• 3： 3；2+1；1+1+1；• 4： 4；3+1；2+2；2+1+1；1+1+1+1• 5： 5；4+1；3+2；3+1+1； 2+2+1； 2+1+1+1；1+1+1+1+1•这里主要讨论无序拆分默认顺序：按从大到小写可以看做可以看做 1+08.3 分拆数•假设一个整数n，其中λ是n的一个分拆•则有 –即： •令pn表示正整数n的分拆数（n的分拆个数）：–可得分拆序列： p0 、p1 、p2 、……pn （n=1,2,3……）•初值：p0 =1、p1 =1、p2 =2、 p3 =3 、p4 =5……•pn等于方程 非负整数解an、an-1、…a2、a1个数。

书上用的是书上用的是“=”8.3 分拆数•回顾：一般生成函数•有无穷数列：•生成函数定义为：•正整数分拆：可以看成下面这样一个序列的划分：•得生成函数：8.3 分拆数•回顾：一般生成函数8.3 分拆数•分拆数的一般表达式： pn•n=an*n+an-1*(n-1)+…+a2*2+a1*1 •设 x1= a1*1 ；x2= a2*2；…；xn=an*n；•目前，没有比较好的一般表达式定理定理8.3.1：：Ferrers图•例：•10=4+2+2+1+1 （无序，按从小到大写）•Ferrers图（横着画） 共轭图（行列转置）•关于对角线对称行数=原图的列数=分拆数的第一项Ferrers图•自共轭分拆（自身的Ferrers图关于对角线对称）优超（控制）• 被u优超 （或 u优超 ） 取=号时，也可以叫 u 控制 自反、反对称、传递自反、反对称、传递优超优超•定理8.3.2：字典序是正整数n的分拆集Pn上优超偏序的线性扩展•a

•1维被0维划分：一条直线被n个点划分• 直线被划分成 n+1个部分：•2维被1维划分：一个平面被n个直线划分（一般位置，两 • 两相交） 直线被划分成 个部分：点分线点分线线分面线分面8.4 一个几何问题有n条直线，再放入第n+1条直线与其他n条直线两两相交，产生了n个交点把直线分成了n+1个部分这 n+1部分，将原来的区域一分为2.即新增加了 n+1个部分递推关系：hn+1-hn=n+1又有初值相等：h0=1所以平面被分成了 部分8.4 一个几何问题•3维被2维划分：n个平面两两相交（一般位置）• 空间被划分成 个部分：面分空间面分空间第n+1个平面，与原来n个平面两两相交可以推知新加进去的平面被分成了 个区域，即新增了这么多的空间区域h2=4h3=8前面的第n+1条线分平面数8.4 一个几何问题•推知……n个（k-1）维超平面将k维空间分成的区域数等于•关于超维平面的想象：（莫比乌斯环，低纬空间的扭曲）8.4 一个几何问题•当k=n时；•n=1：数轴21=2•n=2：平面坐标系22=4•n=3：平面坐标系23=8•当n=n：向量（x1，x2…xn）每一项都有+ -两种选择2n8.5 格路径和Schroeder数•格路径：平面用坐标标识的点。

从A点走到B点的路径•举例：从（r,s）点走到（p,q）点这条路径就是格路径•走法：•H：水平走一格；•V：垂直走一格；•D：斜着走一格对角线•图中红色路径：•H,V,H,H,H,V,V,H,V,H,V,H,V,V8.5 格路径和Schroeder数•回顾：多重集的排列•定理3.4.2 令S是一个多重集，有K个不同类型的元素，各元素的重数分别为n1，n2，…nk设S的大小为n=n1+n2+…nk则S的排列数等于S={n1·a1,n2·a2,…,nk·ak}•证明：多重集S，k种类型元素：a1，a2，…ak，元素的总个数：n=n1+n2+…nk；•占位+乘法原理：•从n个位置中选n1个给a1；•从n-n1个位置中选n2个给a2；•……•从n-n1-…-nk-1个位置中选nk个给ak；•排列数=8.5 格路径和Schroeder数8.5 格路径和Schroeder数•暂时只考虑 H，V两种走法•证明：多重集排列•水平走法：n1=p-r步；•垂直走法：n2=q-s步；•共有n=n1+n2步•则，根据多重集组合定理：8.5 格路径和Schroeder数•当（r,s）=（0,0）•原式可以化简为：8.5 格路径和Schroeder数•下对角线矩形格路径：•如图：从（0，0）走到（9，9）•根据Catalan数：•从（0，0）走到（n，n）问题：如果从（问题：如果从（0,0））走到（走到（p，，q）。

并且并且p≥q呢？呢？8.5 格路径和Schroeder数•思路：•总路径数-穿过对角线的路径数现在求 将图整体下移一格原来的（0,0）--（p,q)，路径r；变成（0,-1）--（p,q-1)，路径r'；原来穿越y=x，等效于，r'接触（有可能穿过）y=x；1：从而：从而 r与与r’间有着一一对应的关系间有着一一对应的关系涉及到两次对应关系涉及到两次对应关系-见下一页见下一页8.5 格路径和Schroeder数•两个一一对应关系：•由于（-1,0）与（p，q-1）位于y=x两侧所以，r1*--r2这条路径必穿过对角线——剩下的就是求从（-1,0）到（p，q-1）路径数定理定理8.5.18.5 格路径和Schroeder数•再次，将r'转换将r'分成了r'1+r2.利用了镜像：r1*是r'1的镜像从而 r’1+r2的路径数=r1*+r2的路径数因为 r1*和r'1是一对一的关系从而问题 由（0,0）--（p,q）变成 （0,-1）--（p,q-1）变成（-1,0）--（p,q-1）因为（因为（-1,0））（（p,q-1）位）位于对角线两于对角线两次，所以路次，所以路径肯定会穿径肯定会穿过对角线过对角线8.5 格路径和Schroeder数• 8.5 格路径和Schroeder数•增加对角线步进 D=（1,1）格路径。

即，斜走•实质：D等效于=1*H+1*V表示：直行 p步骤，竖行q步，斜行r步D等效于等效于=1*H+1*V；；r≤min{p，，q}r=r*H+r*V；则r≤p（即H），r≤q（即V）反之，路径不存在8.5 格路径和Schroeder数•证明：8.5 格路径和Schroeder数• 8.5 格路径和Schroeder数•乘法原理•先排：只有H，V的路径（0,0）--（p-r，q-r）•再排：余下的r步D即插入上一步骤中的路径中即可）•在水平、垂直前后之间的 p+q-2r+1处地方插入r个D•等效于方程的非负整数解个数8.5 格路径和Schroeder数8.5 格路径和Schroeder数•大Schroeder数•本质：从（0,0）--（n,n）下对角线格路径数8.5 格路径和Schroeder数•小Schroeder数•本质：给一组元素添加括号的方法数•添加括号方法：•如：• 单个元素 a1 ，实际为：(a1)；简写为a1【去掉单个元素的括号】• （a1a2 )，实际为：((a1)(a2))；简写为a1a2【红色括号为连续括号-去掉；（a1a2 ）（a3a4 ）这个括号不是连续的括号；蓝色括号为所有元素的最外层括号-去掉】•如有一个序列：a1a2 …a1an 所有添加括号的方法数：小Schroeder数。

8.5 格路径和Schroeder数•添加括号举例：8.5 格路径和Schroeder数•小Schroeder数生成函数推导：•大Schroeder数生成函数推导：8.5 格路径和Schroeder数•小Schroeder数生成函数推导：8.5 格路径和Schroeder数8.5 格路径和Schroeder数•小Schroeder数的递推关系：8.5 格路径和Schroeder数8.5 格路径和Schroeder数•大Schroeder数生成函数推导：本质：格路径•分情形：Øn=0•i）空路径；Øn≠0•ii）从一个对角步进D开始；•iii）从一个水平步进H开始；8.5 格路径和Schroeder数Øn≠0 加法原理&乘法原理•ii）从一个对角步进D开始；•iii）从一个水平步进H开始；•关于K点的解释：为了避免与情形 ii）中的路径重复确保 从（0，0）到（k，k-1）不是 ii）中的走法见下一页图片）•因为（n，n）是在对角线上，所以（k，k）这个点一定是存在的•但（k，k）≠（1,1）8.5 格路径和Schroeder数•（k，k）点•的作用•根据乘法原理： • • 根据加法原理：8.5 格路径和Schroeder数8.5 格路径和Schroeder数•大Schroeder数的递推关系：8.5 格路径和Schroeder数•小Schroeder数的几何意义•Catalan数：n凸多边形三角形划分；8.5 格路径和Schroeder数•小Schroeder数：n凸多边形的剖分（实质就是划分，不在限定是三角形）；•加括号和剖分之间建立了一一对应的关系。