『整数の分割』解答

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

【問題１】

ｆ（ｎ）＝「ｎ個の○のｎ−１個の間をつなぐか否かの場合の数」＝２^ｎ−１・・・（答）

【感想】

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

【問題２】

ｎ＋２の表し方は、ｎ＋１の表し方の最後の数に１を加えるか、ｎの表し方の最後に＋２をつけるか、のいずれかである。

従って、ｇ（ｎ＋２）＝ｇ（ｎ＋１）＋ｇ（ｎ）であり、
ｇ（１）＝ｇ（２）＝１に注意すれば、
ｇ（ｎ）はｇ（１）＝ｇ（２）＝１のフィボナッチ数列。

ｇ（ｎ）＝（（

＋１ ２

）

n

＋（

−１ ２

）

n

）／・・・（答）

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

【問題１】

２の冪　１、２、４、８、１６、。。。。

【問題２】

フィボナッチ数列　　０、１、１、２、３、５、８。。。。

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

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

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

最初の分割値がｐ＋１であるとき、残りｎ−ｐ−１の分割数はＨ（ｐ，ｎ−ｐ−１）である。
最初の分割値がｐ＋２以上であるとき、分割数はｎ−１の分割数と等しくＨ（ｐ，ｎ−１）である。

よって、Ｈ（ｐ，ｎ）＝Ｈ（ｐ，ｎ−１）＋Ｈ（ｐ，ｎ−ｐ−１）　である。
なお、初項は　Ｈ（ｐ、１≦ｎ≦ｐ）＝０，Ｈ（ｐ、ｐ＋１）＝１　です。

特に　p=０　のとき　Ｈ（１，ｎ）＝２Ｈ（０，ｎ−１）、
ｐ＝１のとき　Ｈ（１，ｎ）＝Ｈ（１，ｎ−１）＋Ｈ（１，ｎー２）である。
また、特性方程式は　ｘ^ｐ＋１−ｘ^ｐ−１＝０です。

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

　『整数の分割』へ

　数学の部屋へもどる