Catalan

卡塔兰数¶

Catalan数递推公式为

$C(n)=C(0)*C(n-1)+C(1)*C(n-2)+...+C(n-1)*C(0)$

$C(0)=1$

$C(1)=C(0)*C(0)=1$

$C(2)=C(0)*C(1)+C(1)*C(0)=2$

通项公式为

$C(n)=C_{2n}^n-C_{2n}^{n-1}$

96. Unique Binary Search Trees是直接计算catalan数的题，用的是递推公式

很多组合数学问题可以用Catalan数来计算，比如

括号匹配，也就是长度为2n的dyck word，即n个X和n个Y，任何前缀串中X个数大于等于Y个数
正n边形划分三角形方案个数
95. Unique Binary Search Trees II n个节点构成的不同构二分搜索树的方案数，这里可以这样想，跟节点是一个点，然后左右子树分别计算，也就是上面递推式的格式
2n+1个节点构成的不同构满二叉树方案数

递推公式是通过分治直观得到的，考虑一个栈(无穷大)的进栈序列为1，2，3，…，n，有多少个不同的出栈序列

从第一个元素入栈起，把栈第一次为空位置作为分割点，即1的出栈顺序k，然后前k-1个出栈元素和后n-k个元素顺序可以自由排，即是两个子问题，以n=5，k=3为例

说明在1之前，2和3已经出栈，顺序可以是23可以是32，后面的45出栈顺序可以是45可以是54，用乘法法则，k=3的方案数为 $C(2)*C(2)$

因此总方案数 $C(n)=C(0)*C(n-1)+C(1)*C(n-2)+...+C(n-1)*C(0)$

用dyck word例子来想，总word数有 $C_{2n}^n$ 个，然后来计算不满足条件的word数

对不满足条件的word，一定可以找到一个前缀，Y的数量比X多一，此时将前缀中X和Y互换，整个式子变成n-1个X，n+1个Y的式子，可以证明这种式子和不满足条件的word一一对应，共有 $C_{2n}^{n-1}$ 个

故 $C(n)=C_{2n}^n-C_{2n}^{n-1}$

先说明一下格路问题

从(0, 0)到(m, n)，只沿x正方向或y正方向移动，有 $C_{m+n}^n$ 条路线
从(0, 1)到(m, n)，只沿x/y正方向移动且不接触对角线路线数量为 $C_{m+n-1}^m-C_{m+n-1}^{m-1}$

刚好接触对角线的方案再从总数中减去即可，接触对角线等价于从(0, 1)点关于对角线的对称点(1, 0)到(m, n)的路线数量，即 $C_{m+n-1}^{m-1}$ + 从(0, 0)到(m, n)，只沿x/y正方向移动可以接触但不穿过对角线路线数量为 $C_{m+n}^m-C_{m+n}^{m-1}$

把对角线往下移动一个单位，则和不接触问题相同，此时对称点为(1, -1)

而格路问题就是可以接触但不穿过对角线的路线数量，即 $C(n)=C_{2n}^n-C_{2n}^{n-1}$