卡特兰数

定义

C n = ( 2 n n ) n + 1 = ( 2 n ) ! ( n + 1 ) ! n ! = ∏ k = 2 n n + k k = ∑ i = 0 n − 1 C i C n − i = 2 ( 2 n − 1 ) n + 1 C n − 1 = ( 2 n n ) − ( 2 n n − 1 ) C_n=\frac{

}{n+1}=\frac{(2n)!}{(n+1)!n!}=\prod_{k=2}^{n}\frac{n+k}{k}=\sum_{i=0}^{n-1}C_iC_{n-i}=\frac{2(2n-1)}{n+1}C_{n-1}=- Cn​=n+1(2nn​)​=(n+1)!n!(2n)!​=k=2∏n​kn+k​=i=0∑n−1​Ci​Cn−i​=n+12(2n−1)​Cn−1​=(2nn​)−(2nn−1​)

推导

考虑$n\times n$的网格，只能向上或者向右走，且不能超过$y=x$这条对角线
问：从$(0,0)$走到$(n,n)$有多少种走法

解：从$(0,0)$走到$(n,n)$的方案数需要向右走$n$次和向上走$n$次
其实就是说每一步，向右次数必须要大于等于向上走的次数

如果不考虑对角线这个限制，总共有 ( 2 n n )

(2nn​)总走法

接着考虑不合法的走法
不合法也就意味着经过了$y=x+1$这一条直线
设第一次在$P$点接触到$y=x+1$
此时向上走的次数比向右走的次数多1
也就是说从$P$点到$(n,n)$,向右走的次数会比向左走的次数多1
将$P$点到$(n,n)$的路径中，向右和向上对调（即沿着$y=x$翻转）
那么最后将会到达$(n-1,n)$

也就是说所有的不合法的路径，经过这个操作都会到达$(n-1,n)$
因为这个翻转操作是可逆的，所以不合法路径和到达$(n-1,n)$的路径构成一个双射

那么合法的数量就是 ( 2 n n ) − ( 2 n n − 1 )

- (2nn​)−(2nn−1​)

(图来自wiki，红色虚的折线是不合法路径，红色实的折线是翻转后)

还有一种推导方法
因为向右次数必须要大于等于向上走的次数
所以设向右走为$(x^{\prime },y^{\prime })=(x+1,y+1)$
所以设向上走为$(x^{\prime },y^{\prime })=(x+1,y-1)$
最终目标是走到$(2n,0)$
限制就是不能走到$y=-1$,然后推导思路和上面一样

这种推导方法的有点是，假设不是到达$(n,n)$，而是$(n,m)$也可以类似地分析出来

例子

括号匹配

给定n对括号，求括号正确配对的字符串数
例如：
n=0：空串，1种
n=1：()，1种
n=2: (()) ()()，2种
n=3：((())) ()(()) ()()() (())() (()())，5种
解：
观察最后一对括号，可以分为最后一对括号中括号匹配数和最后一对括号前的匹配数，然后相乘
设$f(n)$为给定n对括号，括号正确配对的字符串数
则$f(n)={\sum }_{i=0}^{n-1}f(i)f(n-i)$

也可以像推导种那样，向右次数必须要大于等于向上走的次数，这里每一个位置的左括号数必须大于右括号数
进而 f ( n ) = ( 2 n n ) − ( 2 n n − 1 ) f(n)=

- f(n)=(2nn​)−(2nn−1​)

出栈序列

$1,2,\cdots ,n$按顺序入栈（栈无限大），问出栈序列有多少种
解：
考虑$k$最后一个出栈，

• 那么$1,2,\cdots ,k-1$需要先出栈
• 然后$k+1,\cdots ,n$出栈
• 最后$k$出栈

设$f(n)$为出栈序列数量
则$f(n)={\sum }_{i=0}^{n-1}f(i)f(n-i)$

二叉搜索树

n个数组成一棵二叉搜索树，问方案数
解：
设k为根，则$1,2,\cdots ,k-1$为左子树，$k+1,\cdots ,n$为右子树
设$f(n)$为n个数组成一棵二叉搜索树的方案数
则$f(n)={\sum }_{i=0}^{n-1}f(i)f(n-i)$