かっこの対応のつけ方の数と、対角線で多角形を三角形に分ける方法の数は、一見まったく関係がなさそうです。ところが驚いたことに、どちらもまったく同じ数列(1, 1, 2, 5, 14, 42...)になります。この不思議な数を、カタラン数といいます。
カタラン数は Cn = (2n)! / ((n+1)! × n!) という式で表されます。n=0から順に 1, 1, 2, 5, 14, 42, 132... と続きます。下でnを変えて値を見たり、自分で並べてみたりして、かっこの対応と多角形の三角形分割がなぜまったく同じ数になるのかを確かめましょう。
nを選んで、カタラン数がどのように計算されるかをくわしく見てみましょう。
開きかっこと閉じかっこをn組使って、かっこが正しく対応する並べ方(どの時点でも閉じかっこが開きかっこより多くならない)をすべて書き出します。
(n+2)角形を対角線で分けて、すべての部分を三角形にする方法が何通りあるか、1つずつめくりながら見てみましょう。
n個の節点をもつ二分木(各節点が多くても左と右の2つの子をもつ木構造)の形の種類の数も、ちょうどカタラン数Cnになります。かっこを節点、かっこの入れ子構造を木の枝だと考えると、3つの問題(かっこ、多角形、二分木)は、実は同じ構造が違う服を着ているだけだとわかります。
このように、見た目はまったく違うのに数がぴったり同じ問題どうしについて、数学者は「全単射がある」といいます。カタラン数は、知られているだけでも200以上の組合せ論の問題に登場します。