数え上げにおいてときどき現れる．括弧列の数・多角形の分割・グリッドの経路数などがカタラン数で表される．

参考資料
wikipedia 括弧列・二分木・最短経路・三角形分割・平面グラフ・非交差分割
 高校数学の美しい物語トーナメント・最短経路・三角形分割
 カタラン数括弧列・最短経路・整数を2段に並べる
 講義スライド凸多角形・二分木

定義

$C_n = \frac{1}{n+1} \binom{2n}{n}$

$i$	$C_i$
0	1
1	1
2	2
3	5
4	14
5	42

競プロ的にはcombinationの部分の前計算を $O(n)$ でしておけばあとは $O(1)$

応用例

グリッドで対角線をまたがない最短経路数

$n \times n$ の二次元グリッドで対角線をまたがないような最短経路が何通りあるか？制約なしの最短経路数は $\binom{2n}{n}$ 対角線をまたぐような最短経路数は $\binom{2n}{n-1}$ グリッドで対角線をまたがない最短経路数は $\binom{2n}{n}-\binom{2n}{n-1}=\frac{1}{n+1} \binom{2n}{n}=C_n$

(追記 2019/12/23)
対角線上の点以外へ最短で到達する方法も同様に求めることができる
二次元グリッドで $y\gt x$ の領域を通らずに $(x,y)=(p,q) p\geq q$ へ最短で行く方法が何通りあるか？
制約なしの最短経路数は $\binom{p+q}{q}$ 通り
「 $y\gt x$ の領域を通る」と「直線 $y=x+1$ について対称な点に行く」は1対1対応させることができる $y\gt x$ の領域を通るような最短経路数は $\binom{p+q}{q-1}$ 通り
条件を満たす最短経路数は $\binom{p+q}{q} - \binom{p+q}{q-1}$ 通り
類題
 類題の解説

括弧列

開括弧と閉括弧が対応するような長さ $2n$ の括弧列は $C_n$ 通り開括弧を上への移動，閉括弧を右への移動とすると対角線をまたがないことが括弧列の対応が取れていることに相当する

二分木

葉が $n+1$ 個の二分木は $C_n$ 通り葉が $n+1$ 個の二分木と長さ $2n$ の括弧列を対応づけられる

凸多角形の三角形分割

$n+2$ 頂点の凸多角形を $n$ 個の三角形に分割する方法は $C_n$ 通り

トーナメント

$n+1$ 人によるトーナメント表は $C_n$ 通りただしチームは区別しない

平面グラフの交差

円上の $2n$ 個の点を交差させずに結ぶ方法は $C_n$ 通り

カタラン数がでてくるわけではまったくないけど ARC076 E - Connected? とかはこれが括弧列と同一視できることをつかってる気がする

非交差分割

非交差分割とは、集合の分割の内、「集合の要素を円状に並べ、同じ部分集合に属する要素を頂点とした多角形同士が交差しない」分割を指す。非交差分割 - Wikipedia

$n$ 要素の集合の非交差分割は $C_n$ 通り

2段の表に並べる

$2$ 行 $n$ 列の表に $1$ ～ $2n$ までの整数を以下の制約にしたがいつつ並べる方法は $C_n$ 通り

各行で左から右へ数が増加
各列で上から下へ数が増加

この問題はそのままこれを使っている KUPC2019 D - Maximin Game

ヤング盤

ヤング図形 wikipedia
フック長 wikipedia

「ヤング盤が何通りあるか？」はフック長の公式から計算できる
分割 $\lambda=(\lambda_1,\ldots,\lambda_m)$ のヤング図形のあるマス $(i,j)$ について

同じ行で $(i,j)$ より右にあるマス
同じ列で $(i,j)$ より下にあるマス

の個数を $h_{\lambda}(i,j)$ とする

$h_{\lambda}(i,j)$ の例

フック長の公式の定義 $d_{\lambda} = \frac{n!}{\prod h_{\lambda}(i,j)}$
2段の表に並べる方法が何通りか $\iff 2$ 行 $n$ 列のヤング盤が何通りか
フック長の公式に当てはめると $d_{\lambda}=\frac{(2n)!}{n!(n+1)!}=C_n$