『整数の分割』

『整数の分割』解答


◆東京都 かえる さんからの解答。

【問題1】

f(n)=「n個の○のn−1個の間をつなぐか否かの場合の数」=2n−1・・・(答)

【感想】

『決着の付き方』と同じですね。

【問題2】

n+2の表し方は、n+1の表し方の最後の数に1を加えるか、nの表し方の最後に+2をつけるか、のいずれかである。

従って、g(n+2)=g(n+1)+g(n)であり、
g(1)=g(2)=1に注意すれば、
g(n)はg(1)=g(2)=1のフィボナッチ数列。

g(n)=((+1
n +(−1
n )/・・・(答)


◆愛知県 Y.M.Ojisan さんからの解答

【問題1】

2の冪 1、2、4、8、16、。。。。

【問題2】

フィボナッチ数列  0、1、1、2、3、5、8。。。。

何れも 『決着の付き方』 のFootmark さんの考え方で解けます。

一般化してみます。
上の問題と同様にしてH(p,n)を定義する。
ただし,今度は和の中にp以下を使ってはならないとする。

f(n)=H(0,n) g(n)=H(1,n) です。

最初の分割値がp+1であるとき、残りn−p−1の分割数はH(p,n−p−1)である。
最初の分割値がp+2以上であるとき、分割数はn−1の分割数と等しくH(p,n−1)である。

よって、H(p,n)=H(p,n−1)+H(p,n−p−1) である。
なお、初項は H(p、1≦n≦p)=0,H(p、p+1)=1 です。

特に p=0 のとき H(1,n)=2H(0,n−1)、
p=1のとき H(1,n)=H(1,n−1)+H(1,nー2)である。
また、特性方程式は xp+1−x−1=0です。

下表に一部計算結果を示す。

n 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
H(0,n)=f 1 2 4 8 16 32 64 128 256 512 1024 2048 4096 8192 16384
H(1,n)=g 0 1 1 2 3 5 8 13 21 34 55 89 144 233 377
H(2,n) 0 0 1 1 1 2 3 4 6 9 13 19 28 41 60
H(3,n) 0 0 0 1 1 1 1 2 3 4 5 7 10 14 19
H(4,n) 0 0 0 0 1 1 1 1 1 2 3 4 5 6 8


 『整数の分割』へ

 数学の部屋へもどる