カタラン数の定義と，満たすべき漸化式を紹介します．カタラン数の豊富な例は別記事で紹介することにします．
カタラン数は組合せに関するいろいろな場面で登場し，重要であるためいろいろな性質が調べられています．大学入試等でもたびたび題材になることがあります．
カタラン数の定義： $n=0,1,2,…$ に対し，$n$ 番目のカタラン数 $C_n$ を次のように定義する． $$\large C_n=\frac{{}_{2n} \mathrm{C} _n}{n+1}$$
これがカタラン数の定義です．${}_{2n} \mathrm{C} _n=\frac{(2n)!}{(n!)^2}$ なので， $$ C_n=\frac{{}_{2n} \mathrm{C} _n}{n+1}=\frac{(2n)!}{(n+1)!n!}$$ という風に階乗記号を用いて表すことができます．
定義式は分数の形をしていますが，カタラン数は必ず自然数になります．実際，定義式から正であることは明らかで，つぎの式変形により， $$C_n=\frac{(2n)!}{(n+1)!n!}=(2n)!\left(\frac{(n+1)-n}{(n+1)!n!}\right)=(2n)!\left(\frac{1}{(n!)^2}-\frac{1}{(n+1)!(n-1)!}\right)$$ $$=\frac{(2n)!}{(n!)^2}-\frac{(2n)!}{(n+1)!(n-1)!}={}_{2n} \mathrm{C} _n-{}_{2n} \mathrm{C} _{n+1}$$ となり，二項係数はつねに自然数なので，カタラン数も自然数です．
カタラン数のはじめの数項はつぎのようになります． \begin{array}{|c||c|c|c|c|c|c|c|c|c|c|c|}\hline n&0&1&2&3&4&5&6&7&8&9&10&\cdots \\ \hline C_n&1&1&2&5&14&42&132&429&1430&4862&16796&\cdots \\ \hline \end{array} つづきが見たい方はこちらへどうぞ→カタラン数
カタラン数はつぎの漸化式を満たします．このことの証明は少し長くなるので，別の記事で紹介することにして，ここでは結果だけ述べます．
カタラン数の漸化式： カタラン数 $C_n$ は次の漸化式を満たす． $$・\large C_0 =1$$ $$・\large C_{n+1}=\sum_{i=0}^{n} C_iC_{n-i}$$
たとえば， $$C_4=C_0C_3+C_1C_2+C_2C_1+C_3C_0$$ $$=1\times 5+1\times 2+2\times 1+5\times 1=14$$ $$C_5=C_0C_4+C_1C_3+C_2C_2+C_3C_1+C_4C_0$$ $$=1\times 14+1\times 5+2\times 2+5\times 1+14\times 1=42$$ などとなります．このように，$n+1$ 番目カタラン数は $0$ から $n$ 番目のカタラン数たちで書き表わすことができます． 逆に，上の漸化式を満たす数列はカタラン数になります．明らかに上の漸化式はただひとつの数列を定義していますので，片方 (『カタラン数は漸化式を満たす』または『漸化式を満たす数列はカタラン数である』)が示されればもう片方も成り立ちます．したがって，この漸化式を満たす数列をカタラン数と定義しても問題ありません．同じことです．
カタラン数が関わっている組合せの問題を考えている場合，定義式を直接見つけるよりは，この漸化式を先に発見する場合が多いと思います．この特徴的な漸化式を見つけることで，カタラン数が関連しているとわかるのです．
別記事 →パスカルの三角形と最短経路 でパスカルの三角形を手続き的に作成する方法を紹介しました．カタラン数も似たような方法で手続き的に作成することができます．カタラン数の最初の数項をただちに知りたい場合は，定義式や前で紹介した漸化式を使うより，いまから紹介する手続き的作成法を使ったほうが早いと思います．さっそく下図をご覧ください．
$0$ 段目に $1$ という数が書かれており，$1$ 段目に $1 1$，$2$ 段目に $1 2 2$，$3$ 段目に $1 3 5 5$ という風に $n$ 段目に $n+1$ 個の数が書かれています．ここでは，$n$ 段目の $n+1$ 個の数を左から第 $0$ 項，第 $1$ 項，．．．，第 $n$ 項と呼ぶことにします．
実は，$n$ 段目の右端の数がカタラン数 $C_n$ になります．(図で，赤で囲んだ数)
これはつぎのようにしてつくることができます． $Step\ 0$ : 各段の左端に $1$ を書く．
$Step\ 1$ : $n$ 段目 ($n\ge 1$)の $k$ 項目 ($1\le k \le n$) に $n$ 段目の $k-1$ 項と $n-1$ 段目の $k$ 項の和を書く．
$Step\ 2$ : $n$ 段目の $n+1$ 項目に $n$ 段目の $n$ 項目の数を書く． つくりかたの $Step\ 1$ により，どの数も，その左隣の数と真上の数の和になります．
さて，なぜこの方法でカタラン数が導けるのでしょうか．この疑問に答えるために，つぎのような問題を考えてみましょう．
問 下図のような $n-1$ 段の階段状の街路がある．地点 $A$ から 地点 $B$ まで街路をたどって最短で行く方法は何通りあるか．
図は実際には $5$ 段ですが，$n-1$ 段だと思ってください．実は，この問いの答えはカタラン数 $C_n$ になります．これは別記事で説明します．これを認めると，先の疑問に答えられます．→パスカルの三角形と最短経路 で紹介した方法で，地点 $A$ から各地点までの最短経路の数を割り当てていくと，これは上で考えたカタラン数の手続き的作成法と全く同じことをしています．つまり，上で考えたカタラン数の手続き的作成法は，地点 $A$ から各地点までの最短経路の数を数えているとみなせます．したがって，この問の答えが $C_n$ とわかれば，手続き的作成法の正当性が証明されたことになります．
