1 . 卡特兰数是组合数学中一个常在各种计数问题中出现的数列．以比利时的数学家欧仁·查理·卡特兰（1814-1894）命名．历史上，清代数学家明安图（1692年-1763年）在其《割圜密率捷法》最早用到“卡特兰数”，远远早于卡塔兰．有中国学者建议将此数命名为“明安图数”或“明安图-卡特兰数”．卡特兰数是符合以下公式的一个数列：且．如果能把公式化成上面这种形式的数，就是卡特兰数．卡特兰数是一个十分常见的数学规律，于是我们常常用各种例子来理解卡特兰数．比如：在一个无穷网格上，你最开始在上，你每个单位时间可以向上走一格，或者向右走一格，在任意一个时刻，你往右走的次数都不能少于往上走的次数，问走到，0≤n有多少种不同的合法路径．记合法路径的总数为