概要

• 一般項: $C_n = \frac{1}{n+1} \binom{2n}{n}$
• 漸化式:
  • $C_0 = 1$
  • $C_n = \sum_{k=0}^{n-1} C_k C_{n-1-k} = (C*C)_{n-1}$ (畳み込み)
• 漸化式から一般項の導出
• 性質
  • $C_n = \binom{2n}{n} - \binom{2n}{n-1}$
    • 証明: 二項係数の定義から計算すると導出できる

例

■ Dyck Path

• $2n$ 回移動する Dyck Path は $C_n$ 通り
• Dyck Path から漸化式の導出

■ 括弧列

• 長さ $2n$ の括弧列は $C_n$ 通り
• 参照: 括弧列
• Dyck Path との対応

■ 二分木

• $n$ 個の分岐を持つ二分木の数は $C_n$ 通り
  • $n+1$ 人によるトーナメント戦の総数だと思っても同じ
• 括弧列との対応
• 漸化式との対応