为什么要学卡特兰数？
为了解决一类计数问题 NOIp能考吗：能
以此记录我模拟赛中被强行卡特兰数卡爆的贪心神题
什么是卡特兰数？
卡特兰数又称卡塔兰数，卡特兰数是组合数学中一个常出现在各种计数问题中的数列。以比利时的数学家欧仁·查理·卡塔兰 (1814–1894)的名字来命名。–百度百科
用人话来说，就是开头为1，2，5，14，42，132，429，1430，4862…的数列
卡特兰数的公式
卡特兰数的一般公式
(只有下标的是卡特兰数，右边那个是组合数)
卡特兰数的递推式
卡特兰数有什么用
此处内容借鉴了:https://blog.csdn.net/wu_tongtong/article/details/78161211
1.括号匹配类计数问题：
给你n个左括号,n个右括号,问有多少种合法的括号放置方案
eg. ()()()是合法的方案，)( 是不合法的方案
能抽象为这类问题的题目，其方案数就是卡特兰数
例题：luogu P3200 有趣的数列
2.出栈次序问题
有1-n个元素，依次进栈，问你有多少种合法的出栈方案
能抽象为这类问题的题目，其方案数也是卡特兰数。
例子：
有2n个人去餐厅吃饭，有n个人有10块钱纸币，n个人有5块钱纸币，餐厅的饭卖5块钱一份，问有多少种可行的买饭顺序
我们可以抽象为：用5块钱买饭就入栈一次，用10块钱买饭就出栈一次
3.二叉树形态数问题
有n个叶子，问你有多少个形态不同的二叉树
这种类型的题目方案数就是卡特兰数
暂无例子( ･´ω`･ )
