资源描述：
《liweiguo_10加特兰数》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、§1加特兰(Catalan)数一、加特兰数的定义第八章特殊计数序列n+1条边组成的凸多边形,被n-2条不相交的对角线分成n-1个三角形区域。二、加特兰数的背景1n=4时K是由n+1条边组成的凸多边形,n-2条不相交的对角线把K分成n-1个三角形。问有多少种不同的分法？加两条辅助线：n+2条边组成的凸多边形,被分成n个三角形区域的分法总数。加特兰数三、加特兰数的背景2由n个1和n个-1组成排列：证明：不允许：１,1,-1,1,-1,-1,-1,1,-1,1变换：-１,-1,1,-1,1,1,1,1,-1,1前7个元素变号，后三个元素不动。此时1增加1个，-1减少一个：有n+1个1
2、，n-1个-1第7个位置首先不满足！前6个元素之和=0，第7个元素必为-1。每个不允许排列可对应有n+1个1和n-1个-1的一个排列。变为不允许排列：１,1,-1,1,-1,-1,-1,1,-1,1给定排列：-１,-1,1,-1,1,1,1,1,-1,1前7个元素变号，后三个元素不动。此时-1增加1个，1减少一个：有n个1，n个-1而且一定是不允许排列。前7项和首先大于0。前6个元素之和=0，第7个元素必为1。反之，每个有n+1个1和n-1个-1的排列也可对应一个不允许排列。所有n+1个1和n-1个-1的排列与所有不允许排列一一对应。例1（零钱问题）解有2n个人排队买电影票，0
3、.50元/张。若售票处没有准备零钱，问总有零钱找的排队方法有多少种？四、应用问题用零钱买票的人1，用整币买票的人为-1满足前k项和大于等于0的排队方法即为所求。所以，能顺利找零的排队数就是加特兰数如果认为人有区别，则还应考虑1和-1的排列。例2（上班路径问题）解：我家与办公室南北相隔n个街区，东西也相隔n个街区。若不穿过对角线，有多少种走法？向右为1，向上走-1，当1的个数大于等于-1的个数时，路径在对角线下方。由对称性，对角线上方的路径数与之相同。所以怎样加括号？例3乘法结合律例3乘法结合律用二分树表示：例3结合率与三角形划分的对应关系例3加括号与三角形划分一一对应！习题8（
4、第4版）2211，2，4
