次の2つの問題を考えてみましょう。1つ目:開きかっこ「(」n個と閉じかっこ「)」n個を、どの時点でも閉じかっこが開きかっこより多くならないように並べる方法は何通りあるでしょうか? 2つ目:凸(n+2)角形を対角線で分けて、すべての部分を三角形にする方法は何通りあるでしょうか? まったく関係のない問題に見えますが、驚いたことに、どちらの答えもまったく同じ数列 1, 1, 2, 5, 14, 42, 132… になります。この数をカタラン数といいます。

カタラン数は Cn = (2n)! / ((n+1)! × n!) という式で表されます。n=0, 1, 2… を代入すると、C0=1, C1=1, C2=2, C3=5, C4=14, C5=42 のようになります。たとえば、3組のかっこでつくれる正しい並べ方は ((())), (()()), (())(), ()(()), ()()() のちょうど5通りです。

ところが、五角形を対角線ですべて三角形に分ける方法を数えても、やはりちょうど5通りになります。これは偶然ではありません。五角形は2本の対角線で3つの三角形に分かれ、n=3の(n+2)角形なので、C3=5とぴったり一致するのです。かっこの問題も多角形の問題も、「何かを再帰的に2つに分ける方法の数」という同じ構造をもっています。

五角形を2本の対角線で3つの三角形に分ける方法は5通り。3組のかっこの対応のつけ方の数とぴったり一致します

偶然に見えるこの一致を、数学者は2つの問題の間に「全単射がある」と表現します。2つの問題の答えを1対1で対応させられる、という意味です。かっこを多角形の対角線に、かっこの入れ子構造を三角形がくっつく順番に対応させて考えると、2つの問題はまったく同じように移り合います。n個の節点をもつ二分木(各節点が多くても左と右の2つの子をもつ木構造)の形の種類の数さえ、同じCnになります。

カタラン数はベルギーの数学者ウジェーヌ・カタランにちなんで名づけられましたが、実はそれより前に、スイスのレオンハルト・オイラーとモンゴルの明安図(ミンガントゥ)がそれぞれ独自に研究していました。この数は、知られているだけでも200以上の組合せ論の問題に登場し、数学のあちこちに隠れています。

アクティビティのページでは、nを変えてそれぞれのカタラン数がどう計算されるかをくわしく見たり、正しいかっこの並べ方をすべて書き出して自分の目で数えたりできます。多角形の三角形分割も1つずつすべてめくって、2つの問題の答えが本当にまったく同じように増えていくことを自分で確かめられます。