平成19年1月14日
[流れ星]
第185回数学的な応募問題
<解答募集期間:1月14日〜2月4日
[部分集合の個数]
皆さん、ここに1からnまでの自然数{1,2,3,・・・,n}があり、その中から隣り合う数を含まないようにs個の数を取り出した部分集合の個数f(n,s)を考えます。
例えば、n=5のときを考えます。
s=1ならば、{1},{2},{3},{4},{5}でf(5、1)=5
s=2ならば、{1,3},{1,4},{1,5},{2,4},{2,5},{3,5}
で、f(5、2)=6
s=3ならば、{1,3,5}でf(5、3)=1 となります。
ここで問題です。
問題1:f(8、s)(1≦s≦4)の値を求めてください。
問題2:nが与えられているとき、題意を満たすsの範囲をnで表してください。
問題3:ここで、F(n)=f(n,0)+f(n,1)+f(n,2)+・・・+f(n,s)を
考えます。ただし、便宜的にs=0のときは、{φ}を考えてf(n,0)=1とする。
F(n)(1≦n≦8)の値を求めよ。
問題4:一般にf(n,s)の値をn,sで表してください。
問題5:F(n)の漸化式を導いて、F(n)をnで表してください。
<参考文献1:数学セミナー(日本評論社)99年2月号エレガントな解答を求む>
<参考文献2:順列・組合せと確率(岩波書店)「山本幸一著」>
皆さん、答えがわかったら、一部でも構いませんから、解答とペンネームを添えて、メールで送ってください。待っています。