円周上の2n個の点を交差しない線分で結ぶ方法を数え上げる問題(3)の解答例を示します。
問題(3)の解
42通りある。
10個の点に1から10までの番号をつける。求める方法の数をf(10)とする。
番号1と番号2k(1≦k≦5)を結ぶ線分により分類すると、5通りの場合がある。
(1) 番号1と2を結ぶ場合。 該当する方法は、f(8)=14 通り。
(2) 番号1と4を結ぶ場合。 該当する方法は、f(2)×f(6)=5 通り。
ただし、f(2)=1とする。
(3) 番号1と6を結ぶ場合。 該当する方法は、f(4)×f(4)=4 通り。
(4) 番号1と8を結ぶ場合。 該当する方法は、f(2)×f(6)=5 通り。
(5) 番号1と10を結ぶ場合。 該当する方法は、f(8)=14 通り。
したがって、つぎの等式を得る。
f(10) = f(8)+f(2)×f(6)+f(4)×f(4)+f(6)×f(2)+f(8) = 42