カタラン数

$ C_n ={\frac {1}{n+1}}{2n \choose n}={\frac {(2n)!}{(n+1)!\,n!}}\quad (n\geq 0)

$ C_{n}={2n \choose n}-{2n \choose n-1}\quad (n\geq 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) まで移動する場合の数

https://gyazo.com/091f70ce1d43c2c68dc6fecc9593c68e

n + 2 個の辺からなる凸多角形を、頂点どうしを結ぶ線を互いに交差しないように引いて、n 個の三角形に切り分けることを考える。この分け方の場合の数は、カタラン数 Cn である。