Catalan 数についての簡単な考察

引言#

$Catalan$ の本質は再帰的な関係式であり、多くの問題の再帰的な形式は $Catalan$ の再帰的な形式と同じです。これは彼らが共通点を持っていることを示しており、 $Catalan$ 数の考え方を使用することができ、私たちが問題を解決するための新しい視点を開くことになります。

定義#

$|A|: シーケンスの長さ$
$解の集合: 一連の合法的なシーケンス$
$operator\ +: シーケンスの結合$

二分木の種類数問題#

分割統治：左 + 自分 + 右

以下の定義があります

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}$