淺談 Catalan 數

引言#

$Catalan$ 的精髓是推遞推式，很多問題的遞推式形式上與 $Catalan$ 的遞推式相同，這說明他們有著共同之處，可以使用 $Catalan$ 數的思考方法，這對我們解決問題來說算是打開了一個新的窗口。

分治：左 + 自己 + 右

我們有如下定義

H_n=\begin{cases} 1, n=0,1\\ \sum_{i=1}^nH_{n-i}\cdot H_{i-1}, n\geq 2 \end{cases}

$n$ 個 $+1$ 和 $n$ 個 $-1$ 構成 $2n$ 項 $a_1,a_2, \cdots ,a_{2n}$ ，其部分和滿足 $a_1+a_2+ \cdots +a_k \geq 0(k=1,2,3, \cdots ,2n)$ 對於 $n$ 該數列為？

乍一看好像很難，但是我們仔細分析一下

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

我們用總量減去不合法量

把 $n$ 個 $+1$ 放在長 $2n$ 數列裡面，其他的都是 $-1$ ，故總量為 $\binom{2n}{n}$

首先我們考慮不合法的情況
而只有一種情況會導致不合法
那就是在某個前綴和的過程中，部分和首次小於零。

設 $A$ 是一組合法解， $B$ 是任意序列 (同時滿足 $B$ 中缺少且僅缺少一個 $-1$ 且有 $|B|=n-1$ )
即 $|A|+|B|=2n-1$

顯然此時有 $H=(A, -1, B)$ ，這是一組不合法解

Warning

此時雖然是不合法解，但是此時 $H$ 中 $+1$ 和 $-1$ 的數量都為 $n$

怎麼區分合法解和不合法解呢？
我們設 (取反 $B$ 序列)

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

那麼現在 $\hat{B}$ 就是一個多了且僅多了一个 $-1$ 的序列 (從少一個到多一個了呢)

那麼現在 $\hat{H}=(A, -1, \hat{B})$ 就是一組有 $n+1$ 個 $-1$ 和 $n-1$ 個 $+1$ 的序列

好像區分開了，來驗證一下可行性
考慮是否能做到不重不漏

仔細思考 $\hat{B}$ 和 $B$ 是一個雙射集合
也就是說所有的不合法解都對應一個如此這般的 $\hat{H}$

那麼如何統計呢？
枚舉 $+1$ 或 $-1$ 的數量都可以

那就是 $\binom{2n}{n-1}$ 或 $\binom{2n}{n+1}$

$H_n=\binom{2n}{n}-\binom{2n}{n-1}$