面白い問題おしえて～な十三問目

面白い問題おしえて～な十三問目 at MATH

155:１３２人目の素数さん
07/09/26 16:47:57
>>153

L種類の棒で作られるL[mm]の長さが何通りあるかを f(L)で表す。

L=1のとき、明らかに1mmの棒が一本の1通りである。

L=n (ただしn>1) の場合について考える。
一番上になる棒の長さが1であるものは f(n-1)の上に長さ1の棒を重ねたものと等しい
一番上になる棒の長さが2であるものは f(n-2)の上に長さ2の棒を重ねたものと等しい
一番上になる棒の長さが3であるものは f(n-3)の上に長さ3の棒を重ねたものと等しい
：
一番上になる棒の長さがL-1であるものは f(n-(L-1))の上に長さ(L-1)の棒を重ねたものと等しい
一番上になる棒の長さがLであるものは1通り
なので
f(L) = Σ_[k=1.Ln-1]{f(k)} + 1 = 2^n-1

この式は L=1のときにも f(L) = 2^n-1 =2^1-1 = 1 なので当てはまる。

次ページ

続きを表示

1を表示