カトラン数(Catalan Number)とその応用

定義＃テイギ＃
カトラン数は様々なカウント問題によく現れる数列であり,その満たす繰返し方程式は以下の通りである:$$C(n)=sum_{k=0}^{n-1}C(k)times C(n-1-k),ngt 0$$は初期値$C(0)=1$,その前の項は:1,1,2,5,14,42...その一般式には複数の書き方があり,生成関数法で直接以上の繰返し方程式から求めることができるが,ここではひとまず表に出さず,$$C(n)=frac{1}{n+1}binom{2 n}{n}$$
適用
カトラン数は多くの興味深い組合せ数学問題とCSにおけるカウント問題に応用でき、その中の部分を列挙する.

n個の数には、いくつの異なるスタック・シーケンスがありますか.--C(n).

nは括弧に対して何種類の合法的なペアリングの形式がありますか?e.g., n = 2,()(), (()) -- C(n).

n+1個の乗算数にかっこ、e.g.、n=2、(ab)c)、(a(bc))を付ける.いくつの方法がありますか?---C(n).

にはn個のノードの二叉木(二叉探索木(BST)も同様)がありますが、どのような異なる構成形式がありますか.--C(n).

n+1個の葉の結点がある満二叉樹は、何種類ありますか.--C(n).

凸n+2の辺形を交差しない対角線でn個の三角形に分割するには、いくつの方法がありますか.--C(n).

n個−1とn個1からなるシーケンスのうち,任意の接頭辞和が0より大きいものは何種類あるか.--C(n). この問題は,−1を入スタック,1を出スタックと見なすことができ,接頭辞と0より大きいシーケンスは出スタックシーケンスに等価である.

これにより多くの問題が派生し,通常定義中の繰返し方程式を書くことができる.笔记试题:図书馆には全部で6人が并んでいて、3人は「面接宝典」という本を返して、3人は「面接宝典」という本を借りています.図书馆には面接宝典がありません.例題7のように、C(3)=5ですが、組み合わせに注意する問題はすべて品物が同じだと考えられています.ここでは3つの異なる人の配列を考慮しなければなりません.そのため、総数:5*3!*3! = 180.
計算＃ケイサン＃
次にcodeを用いてn番目の組合せ数$C(n)$を計算する.繰返し式と一般式の2つの方法があります.
ダイナミックプランニング
繰返し式によって書きやすく、通項式を忘れたときに使えるので、タイムアウトしないことが多いです.

int catalan(int n) {
    vector dp(n+1, 0);
    for (int i = 1; i <= n; ++i)
        for (int j = 0; j <= i - 1; ++j)
            dp[i] += dp[j] * dp[i-1-j];
    return dp[n];
}

時間複雑度:$O(n^2)$

空間複雑度:$O(n)$

コンビネーション数の計算
一般式を覚えていれば、直接計算する組合せ数はもっと速く、私が別の文章で述べた方法compute_binomialを利用してO(n)時間で完成することができる.

int catalan(int n) {
    return compute_binomial(2*n, n) / (n+1);
}

時間複雑度:$O(n)$

空間複雑度:$O(1)$