カタラン数（Catalan Number）

2.1 Worst-Case EntropyにnノードのGeneral Ordinal Trees（一般順序木？）（一般じゃない順序木とは）の種類はn-1番目のカタラン数になるということが書いてあります。

Wikipediaの「（）を正しく並べる方法」というのがそれに相当するもの（のはず）。

その下に二分木について書いてあるので、順序木無理ではと一瞬あせりますが、順序木は括弧で表現することができるのでkotonakiですね（のはず）（記憶がヤバイ）。

Rustのコードだと以下のような感じ。素朴な実装なのでnが大きくなると死にます。

fn catalan(n: u64) -> u64 {
    factorial(2 * n) / factorial(n).pow(2) / (n + 1)
}

fn factorial(n: u64) -> u64 {
    if n <= 1 {
        1
    } else {
        n * factorial(n - 1)
    }
}

fn main() {
    for i in 0..10 {
        println!("catalan({}) = {}", i, catalan(i));
    }
}

catalan(0) = 1
catalan(1) = 1
catalan(2) = 2
catalan(3) = 5
catalan(4) = 14
catalan(5) = 42
catalan(6) = 132
catalan(7) = 429
catalan(8) = 1430
catalan(9) = 4862