カタラン数というものがあるらしい。二分木みたいなプログラミングに関係しているものなのに全然知りませんでした。勉強が足りんなあ…
カタラン数（-すう、英:Catalan number）は自然数で、ベルギーの数学者Eugène Charles Catalanによって名付けられた数である。n番目のカタラン数Cnは以下の式で定義される。
Wikipediaのカタラン数の意味、という項目を見て、しばらく考えて気づいたのだが、この括弧と二分木と経路の例は、同じ事を別の形で表現にしているだけのような気がする。
いずれの例も「aとbという要素が同数ある。これらの要素を取り出して一列に並べる場合の数はいくつか？。ただしbを選べるのは、bを選んだ回数が、aを選んだ回数を超えない場合に限る」という問題に抽象化できる。括弧の問題は(を選ぶのがa、)を選ぶのがb、経路の問題は→を選ぶのがa、↑を選ぶのがb、二分木はちょっとわかりにくいが、上・左からノードを埋めていってノードにデータがある場合がa、ノードがnullの場合がbとする並べ替えの問題。
「２n人が円になって手を交差させないで握手をする場合の数はカタラン数Cnである。」これも同じように抽象化できるだろうか？暇なときに考えてみることにする。
