Preface

Catalan 组合数学 真是一个神奇的东西

Catalan 的精髓是推递推式, 只不过很多问题的递推式会收敛到 Catalan 的递推式(只能说是一种推递推的思想)

Start up

二叉树种类

分治的思想, 左+自己+右, 把问题化小

Hn=∑i=1nHn−i⋅Hi−1H_n=\sum_{i=1}^nH_{n-i}\cdot H_{i-1}

当然, 初始值 H0=H1=1H_0=H_1=1

合法数列

nn 个 +1+1 和 nn 个 −1-1 构成 2n2n 项 a1,a2,⋯ ,a2na_1,a_2, \cdots ,a_{2n}，其部分和满足 a1+a2+⋯+ak≥0(k=1,2,3,⋯ ,2n)a_1+a_2+ \cdots +a_k \geq 0(k=1,2,3, \cdots ,2n) 对与 nn 该数列为？

乍一看好像很难, 但是我们仔细分析一下

好像不方便直接得到结果, 那就容斥原理

我们用总量减去不合法量

总量

这个不难, 我们把 nn 个 +1 放在 长 2n2n 数列里面, 其他的都是 -1
那么这里就是 (2nn)\binom{2n}{n}

不合法量

首先我们考虑不合法的情况
而只有一种情况会导致不合法
那就是

一组解: 一串序列
|A|: 求序列长度

设 AA 是一组合法解, BB 是任意序列(同时满足 BB 中缺少且仅缺少一个 −1-1 且有 ∣B∣=n−1|B|=n-1)
即 ∣A∣|A|+∣B∣|B|=2n-1

此处代表序列拼接(下同)

显然此时有 H=(A,−1,B)H=(A, -1, B) 是一组不合法解
注意, 此时虽然是不合法解, 但是此时 HH 中 +1+1 和 −1-1 的数量都为 nn

有无什么好方法区分合法解和不合法解呢?
我们设(其实就是"取反" BB 序列)

Bi^={+1,Bi=−1−1,Bi=+1\hat{B_i}=\begin{cases} +1, B_i=-1\\ -1, B_i=+1 \end{cases}

那么现在 B^\hat{B} 就是一个多了且仅多了一个 −1-1 的序列(从少一个到多一个了呢)

那么现在 H^=(A,−1,B^)\hat{H}=(A, -1, \hat{B}) 就是一组有 n+1n+1 个 −1-1 和 n−1n-1 个 +1+1 的序列

好像区分开了, 来验证一下可行性
考虑是否能做到不重不漏

仔细思考 B^\hat{B} 和 BB 是一个双射集合
也就是说 所有的不合法解都对应一个如此这般的 H^\hat{H}

那么如何统计呢?
简单, 枚举 +1+1 或 −1-1 的数量都可以

那就是 (2nn−1)\binom{2n}{n-1} 或 (2nn+1)\binom{2n}{n+1}

最终解

Hn=(2nn)−(2nn−1)H_n=\binom{2n}{n}-\binom{2n}{n-1}