今回は自然数を自然数の和に分割させる問題。


問題

自然数をそれ以下の自然数の和として表すこと考えます。

ただし、1+2+1と1+1+2のように順序が違うものは別の表し方とします。

例えば、3は1+1+1,1+2,2+1,3の4通りの表し方があります。

では、5の表し方は何通りありますか。


1→1の1通り

2→1+1,2の2通り

3→1+1+1,1+2,2+1,3の4通り

まぁ、このくらいまではすぐにわかりますね。


次の4は書き出さずに、場合分けして考えてみたいと思います。

左端が1のとき、残りの和が3で、3の表し方は4通り

左端が2のとき、残りの和が2で、2の表し方は2通り

左端が3のとき、残りの和が1で、1の表し方は1通り

これらに4自身の1通りも含めて、4+2+1+1=8通り


5だと、、

左端が1のとき、残りの和が4で、4の表し方は8通り

左端が2のとき、残りの和が3で、3の表し方は4通り

左端が3のとき、残りの和が2で、2の表し方は2通り

左端が4のとき、残りの和が1で、1の表し方は1通り

これらに5自身の1通りも含めて、8+4+2+1+1=16通り




という風に、こういった場合の数では漸化式の考え方が有効ですが、各数の場合の数から何かに気付きませんか??

とりあえず、、2の累乗になっています。では、そのわけを別のアプローチから考えてみたいと思います。


「5=1+1+1+1+1」と、1が5個の和として書くと、間の+は4個です。

ここで、4個の+をそれぞれ計算するかしないかの話だけなので、2×2×2×2=16通り

だから、必ず2の累乗になりますね。


[←戻る]