カタラン数の漸化式
さて、カタラン数のイメージがつかめたところで、今度はカタラン数のそれぞれの項の間にどんな関係があるかを考えます。
たとえば、最大の数値が8の9個のねんど玉があったとします。
これを隣り合う2個ずつをくっつけていって、最終的に1個のねんど玉にするわけですが、最後に1個にまとまる直前に、2つのねんど玉ができているはずです。たとえば、青のねんど玉にする一歩手前で、0〜4の黄色のねんど玉と5〜8の緑のねんど玉ができていたとします。
上の図では、黄色のねんど玉がどのようなプロセスでできたかはわからないけれど、そのプロセスは0〜4の5個のねんど玉を1つにまとめるプロセスの中に含まれています。なので、黄色のねんど玉ができるまでのくっつけ方はC4通りあるはずです。同様に、5〜8の緑のねんど玉ができるまでのプロセスはC3通り。なので、最後で（5個）と（4個）のねんどをくっつけるようなくっつけ方は、全部で（C4×C3）通りとなります。
これとは別のくっつけ方を考えてみます。
今度は、最終的に（3個）と（6個）になるようなくっつけ方です。黄色の（3個）になるまでC2通り、緑の（6個）になるまでC5通りなので、全部で（C2×C5）通りとなります。Cnのnの値がねんど玉の個数より1小さくなっていることに注意しながら考えていきます。
すべての場合の数をまとめると
（1個）と（8個）になる場合 → C0×C7 通り
（2個）と（7個）になる場合 → C1×C6 通り
（3個）と（6個）になる場合 → C2×C5 通り
（4個）と（5個）になる場合 → C3×C4 通り
（5個）と（4個）になる場合 → C4×C3 通り
（6個）と（3個）になる場合 → C5×C2 通り
（7個）と（2個）になる場合 → C6×C1 通り
（8個）と（1個）になる場合 → C7×C0 通り
よって、
が成り立ちます。右辺をみてみると、すべてのC○C●において、○＋●＝7＝8−1 が成り立っています。
なお、「隣り合うねんど玉2個をくっつけて最終的に1個にする」という考え方だと、C0…つまり最初からねんど玉1個の場合をどう考えればよいのか？という疑問が残りますが、上の式ではC0＝1と考えることになるので、C0＝1と考えていいことにします（なぜこう考えてよいのか、考えてよいのかどうか厳密な意味はわかりませんが、とりあえずここではそういうことにします）。
というわけで、カタラン数の漸化式が求まりました。
いきなりシグマですみません。例のごとく何かと雑なことになっていますが、結城浩『数学ガール』では丁寧かつきちんと記述されています。
（つづく）
たとえば、最大の数値が8の9個のねんど玉があったとします。
これを隣り合う2個ずつをくっつけていって、最終的に1個のねんど玉にするわけですが、最後に1個にまとまる直前に、2つのねんど玉ができているはずです。たとえば、青のねんど玉にする一歩手前で、0〜4の黄色のねんど玉と5〜8の緑のねんど玉ができていたとします。
上の図では、黄色のねんど玉がどのようなプロセスでできたかはわからないけれど、そのプロセスは0〜4の5個のねんど玉を1つにまとめるプロセスの中に含まれています。なので、黄色のねんど玉ができるまでのくっつけ方はC4通りあるはずです。同様に、5〜8の緑のねんど玉ができるまでのプロセスはC3通り。なので、最後で（5個）と（4個）のねんどをくっつけるようなくっつけ方は、全部で（C4×C3）通りとなります。
これとは別のくっつけ方を考えてみます。
今度は、最終的に（3個）と（6個）になるようなくっつけ方です。黄色の（3個）になるまでC2通り、緑の（6個）になるまでC5通りなので、全部で（C2×C5）通りとなります。Cnのnの値がねんど玉の個数より1小さくなっていることに注意しながら考えていきます。
すべての場合の数をまとめると
（1個）と（8個）になる場合 → C0×C7 通り
（2個）と（7個）になる場合 → C1×C6 通り
（3個）と（6個）になる場合 → C2×C5 通り
（4個）と（5個）になる場合 → C3×C4 通り
（5個）と（4個）になる場合 → C4×C3 通り
（6個）と（3個）になる場合 → C5×C2 通り
（7個）と（2個）になる場合 → C6×C1 通り
（8個）と（1個）になる場合 → C7×C0 通り
よって、
が成り立ちます。右辺をみてみると、すべてのC○C●において、○＋●＝7＝8−1 が成り立っています。
なお、「隣り合うねんど玉2個をくっつけて最終的に1個にする」という考え方だと、C0…つまり最初からねんど玉1個の場合をどう考えればよいのか？という疑問が残りますが、上の式ではC0＝1と考えることになるので、C0＝1と考えていいことにします（なぜこう考えてよいのか、考えてよいのかどうか厳密な意味はわかりませんが、とりあえずここではそういうことにします）。
というわけで、カタラン数の漸化式が求まりました。
いきなりシグマですみません。例のごとく何かと雑なことになっていますが、結城浩『数学ガール』では丁寧かつきちんと記述されています。
（つづく）
