组合数学加特兰数课件.pptVIP

§1 加特兰( Catalan )数 一、加特兰数的定义 第八章 特殊计数序列 n+1条边组成的凸多边形,被n-2条不相交的对角线分成 n-1个三角形区域。 二、加特兰数的背景1 n=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，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.50元/张。 若售票处没有准备零钱，问总有零钱找的排队方法有多少种？ 四、应用问题 用零钱买票的人1，用整币买票的人为-1 满足前k项和大于等于0的排队方法即为所求。 所以，能顺利找零的排队数就是加特兰数 如果认为人有区别，则还应考虑1和-1的排列。 例2 （上班路径问题） 解： 我家与办公室南北相隔n个街区，东西也相隔n个街区。若不穿过对角线，有多少种走法？ 向右为1，向上走-1， 当1的个数大于等于-1的个数时，路径在对角线下方。 由对称性，对角线上方的路径数与之相同。所以 怎样加括号？ 例3 乘法结合律 例3 乘法结合律 用二分树表示： 例3 结合率与三角形划分的对应关系 例3 加括号与三角形划分一一对应！ 习题8（第4版）221 1，2，4