卡特兰数

Catalan Number
C(2n, n) - C(2n, n + 1) = C(2n, n) / (n + 1)

f[1] = 1
f[2] = 2
f[3] = 5
f[4] = 14
f[5] = 42

f[n] / f[n-1]
(C(2n, n) / (n + 1)) / (C(2n - 2, n - 1) / (n))
((2n)! / n! / (n+1)!) / ((2n-2)! / (n-1)! / n!)
2n * (2n-1) / n / (n+1)
(4n - 2) / (n + 1)

f[n] / f[n-1] = (4n - 2) / (n + 1)
f[n] = f[n-1] * (4n - 2) / (n + 1)

1. n个左括号，n个右括号，有多少种合法的括号序列
2. 等价于有多少种进出栈序列
3. n个节点有多少个二叉树
4. 正n+2边形，连接对角线（不能相交）可以把n+2边形分成n个三角形，问方案数
5. 2n个元素排成一个环，两两配对，不能相交，问有多少种方法
6. 一行n个元素，分成若干组，组和组不能相交 比如5个元素，分成 1 2 1 3 1 是可以的，但 1 2 1 2 3 是不允许的

( 入栈
) 出栈

入栈顺序 1 2 3

((())) 3 2 1
()()() 1 2 3
(()()) 2 3 1
()(()) 1 3 2
(())() 2 1 3

不可能出现 3 1 2

折线法

从(0, 0)到(n, n)每一步可以向上或向右

不能经过(x, y)如果x+1==y，比如(0,1) (1,2) (2,3) ... (n-1,n)

问方案数？

从(0, 0)到(n, n)的方案数是C(2n, n)

从(-1, 1)到(n, n)的方案数是C(2n, n-1)

从(-1, 1)到(n, n)任意一个方案
对应
从(0, 0)到(n, n)任意一个不合法的方案

从(0, 0)到(n, n)方案数C(2n, n)
从(-1, )到(n, n)方案数C(2n, n-1)
总方案数C(2n, n) - C(2n, n-1) = C(2n, n) / (n+1)

f[n] = f[n-1] * (2n-1) * (2n) / (n) / (n+1)
f[n] = f[n-1] * (4n-2) / (n+1)

https://www.luogu.com.cn/problem/P1044
https://www.luogu.com.cn/problem/P1375
https://www.luogu.com.cn/problem/P1754