課題1

カタラン数を計算する関数 catalan n を定義しなさい。

カタラン数とは

カタラン数cnとは、下図のような格子上の道路を、 左下の角から右上の角まで移動する経路の数のことである。(但し、後戻りはしない。)

格子上の道路

カタラン数cnは、次の漸化式を満たす。

cn = c0cn-1 + c1cn-2 + . . . + cn-1c0
但し、便宜上c0 = 1と定義する。

おわり