円周上の2n個の点を交差しない線分で結ぶ方法を数え上げる問題（４）の解答例を示します。
問題（４）の解
2n個の点に1から2nまでの番号をつける。求める方法の数をf(2n)とする。
番号1と番号2k(1≦k≦n)を結ぶ線分により分類すると、n通りの場合がある。
(1) 番号1と2を結ぶ場合。 該当する方法は、f(2n-2) 通りある。
(2) 番号1と4を結ぶ場合。 該当する方法は、f(2)×f(2n-4) 通りある。
・・・
(k) 番号1と2kを結ぶ場合。 該当する方法は、f(2k-2)×f(2n-2k) 通りある。
・・・
(n-1) 番号1と2n-2を結ぶ場合。 該当する方法は、f(2n-4)×f(2) 通りある。
(n) 番号1と2nを結ぶ場合。 該当する方法は、f(2n-2) 通りある。
したがって、つぎの漸化式を得る。
f(2n) = f(2n-2)＋f(2)×f(2n-4)＋･･･＋f(2k-2)×f(2n-2k)＋･･･
＋f(2n-4)×f(2)＋f(2n-2)
f(0)=1と定義すると、つぎのようになる。
f(2n)はカタラン数と呼ばれている。
