カタラン数

$C_n=\frac{1}{n+1}\left(\genfrac{}{}{0ex}{}{2n}{n}\right)=\frac{(2n)!}{(n+1)!n!}(n\ge 0)$ $C_n=\left(\genfrac{}{}{0ex}{}{2n}{n}\right)-\left(\genfrac{}{}{0ex}{}{2n}{n-1}\right)(n\ge 1)$ 1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845, …

• x 座標か y 座標の増加する方向に 1 だけ進む操作を繰り返し、x < y なる領域を通らずに (0, 0) から(N, N) まで移動する場合の数
  • 
    • カタラン数 - Wikipedia
• 長さ 2N の、バランスされた括弧列の個数
• 凸 N 角形の三角形分割の個数
  • n + 2 個の辺からなる凸多角形を、頂点どうしを結ぶ線を互いに交差しないように引いて、n 個の三角形に切り分けることを考える。この分け方の場合の数は、カタラン数 Cn である。
• n 個の分岐を持つ（n + 1 枚の葉を持つ）二分木の個数