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,