平成１９年１月１４日

[流れ星]

　　　　　第1８５回数学的な応募問題

　　　　　　＜解答募集期間：１月１４日〜２月４日

［部分集合の個数］

皆さん、ここに１からｎまでの自然数｛１，２，３，・・・，ｎ｝があり、その中から隣り合う数を含まないようにｓ個の数を取り出した部分集合の個数ｆ（ｎ，ｓ）を考えます。

　例えば、ｎ＝５のときを考えます。

ｓ＝１ならば、｛１｝，｛２｝，｛３｝，｛４｝，｛５｝でｆ（５、１）＝５

ｓ＝２ならば、｛１，３｝，｛１，４｝，｛１，５｝，｛２，４｝，｛２，５｝，｛３，５｝

　　　　　　　　で、ｆ（５、２）＝６

ｓ＝３ならば、｛１，３，５｝でｆ（５、３）＝１　となります。

　ここで問題です。

問題１：ｆ（８、ｓ）（１≦ｓ≦４）の値を求めてください。

問題２：ｎが与えられているとき、題意を満たすｓの範囲をｎで表してください。

問題３：ここで、Ｆ（ｎ）＝ｆ（ｎ，０）＋ｆ（ｎ，１）＋ｆ（ｎ，２）＋・・・＋ｆ（ｎ，ｓ）を

　　　　考えます。ただし、便宜的にｓ＝０のときは、｛φ｝を考えてｆ（ｎ，０）＝１とする。

　　　　Ｆ（ｎ）（１≦ｎ≦８）の値を求めよ。

問題４：一般にｆ（ｎ，ｓ）の値をｎ，ｓで表してください。

問題５：Ｆ（ｎ）の漸化式を導いて、Ｆ（ｎ）をｎで表してください。

＜参考文献１：数学セミナー（日本評論社）９９年２月号エレガントな解答を求む＞

＜参考文献２：順列・組合せと確率（岩波書店）「山本幸一著」＞

皆さん、答えがわかったら、一部でも構いませんから、解答とペンネームを添えて、メールで送ってください。待っています。