卡特兰数(Catalan Number)
卡特兰数是组合数学中常出现在各种计数问题中的数列。
数列的前几项为1，1，2，5，14，42，132，429，1430，4862。下边几个例子从简单到难得介绍了卡特兰数的各种应用。
经典问题
1. 进出栈的问题
这是个最经典的卡特兰数的问题，n个元素进出栈的序列为1, 2 ,3, ..., n，那么有多少种出栈的顺序。
思路
首先建模，如果将进栈表示为+1，出栈表示为-1，则1 3 2的出栈顺序代表的序列可表示为： +1 -1 +1 +1 -1 -1 。根据栈的特点，每次出栈操作之前必须有入栈操作，即每个-1前都有一个+1与之对应。换言之，出栈序列的任意前n项的和必须大于等于0，并且+1的数量等于-1的数量。下面考虑不合法的出入栈序列： +1 -1 -1 +1 -1 +1，序列的前三项和小于0，如果将第一个和小于0的前缀（即前三项）都取反，得到的是 -1 +1 +1 +1 -1 +1。此时有3 + 1个+1和3 - 1个-1。因为这个小于0的前缀和必然是-1，且-1比+1多一个，取反后，-1比+1少一个，则+1变为n + 1个，且-1变为n - 1个。进一步推广，对于n元素的每种非法出栈序列，都会有一个含有n + 1个+1和n - 1个-1的序列与之一一对应。
上面描述从左到右已经说明，下面说明从右到左：对于每一个含有n + 1个+1和n - 1个-1的序列必然存在第一个和大于0的前缀，将其反转，得到一个非法序列。（证明一一对应还必须说明这两个集合的元素个数相等，如何证明？）
因此非法的序列个数为C(m+1)(2n)，因此合法出栈的个数有C(n)(2n) - C(n+1)(2n)个。
2. 括号序列
有n对括号，则有多少种合法的“括号匹配”的括号序列？
思路：如果将左括号看作+1，右括号看作-1，那么问题就转化为上边的进出栈问题。
如何输出见：(https://starkschroedinger.github.io/2019/12/10/LeetCode-Records/) 22M. 产生括号对
3. 满二叉树
n + 1个叶子节点能够构成多少种形状不同的（国际）满二叉树？所谓（国际）满二叉树是除了叶子节点外每个节点都有两个孩子。
思路：如何将满二叉树的形状转化为进出栈的问题？由叶子节点和非叶子节点的数量关系可知，总扩展的数量为2n个（节点与节点之间的连接成为扩展）。因此从根节点出发，左扩展为+1，向右扩展为-1。因此每有一个右扩展，之前必须有对应的左扩展，否则为非法（证明略）。如此建立联系。
4.零钱找零问题
一张电影票50，一开始售票员没有零钱，顾客会拿50和100的面值来买票。若有m个50的人和n个100个人。有多少种排队方式，可以让每个人都买到电影票？
思路：因为100的钞票对后续找零没有任何作用，因此可以将50看错+1，100看作-1，不同的是，m不一定等于n，如果等于n就是典型的进出栈问题。而且，所有人并不相同，因此最后结果为 (C(m)(m+n) - C(m+1)(m+n))*m!*n!。关于被减去的那一项的解释：对于非法的排列，必然有前缀和小于0的，如果将小于0的前缀翻转，则得到一个有m+1个+1的序列。
递推公式
卡特兰数满足以下递推公式：
` C1 = 1, Cn = Cn-1(4n-2)/(n+1)`
代码计算时按照上式计算第n个卡特兰数。
需要注意的是，卡特兰数增长很快， n = 17时就超过了32位int的上限（2^31 - 1）。记住卡特兰数的前四项1、1、2、5有助于联想到卡特兰数的匹配问题。LeetCode上1259. 不相交的握手也是这种问题。
最后编辑日期：2020-02-18
