[答780] 全部の式の項の数
'
[答780] 全部の式の項の数
自然数 n を n 自身 または 後の数が前の数以下になるような自然数の和で表します。
このときの全部の式の項の数の合計を f(n) とします。
例えば n=5 のとき、 5,4+1,3+2,3+1+1,2+2+1,2+1+1+1,1+1+1+1+1 だから、
f(5)=1+2+2+3+3+4+5=20 になります。
f(1)=1,f(2)=3,f(3)=6,f(4)=12,f(5)=20,f(6)=35,f(7)=54,f(8)=86,f(9)=128,f(10)=192,
f(11)=275,f(12)=399 に続く f(13)=? ,f(14)=?
[解答]
自然数 n を n 自身 または 後の数が前の数以下になるような自然数の和で表した式を
単に「和が n になる式」ということにします。
例えば 「和が 13 になる式」の例として、6+5+2 がありますが、●を使って
●●●●●●
●●●●●
●●
と表し、左から●の個数を数えると、「和が 13 になる式」の 3+3+2+2+2+1 が得られます。
これは、6+5+2 の項の個数が、3+3+2+2+2+1 の先頭の数であり、
3+3+2+2+2+1 の項の個数が、6+5+2 の先頭の数であることを示しています。
よって、f(n) は「和が n になる式」全部の最初の項の総和 とも言えます。
ここで、fk(n) を
「和が n になる式」のうち 最後の項が k 以上の自然数であるもの全部の最初の項の総和 とすれば、
f1(n)=f(n) で、
fk(n) を求めるとき 最後が「+k」で終わる式と それ以外の式に分けて考えれば、
n>k のとき fk(n)=fk(n-k)+fk+1(n) になります。
従って、
n>1 のとき f1(n)=f1(n-1)+f2(n) 、
すなわち、f(n)=f(n-1)+f2(n) が得られます。
n>3 のとき n の代わりに n-2 にして両辺に -1 をかければ、
-f(n-2)=-f(n-3)-f2(n-2) 、
また、n>2 のとき f2(n)=f2(n-2)+f3(n)
この3式を辺々加えて、簡単にすれば、
n>3 のとき f(n)=f(n-1)+f(n-2)-f(n-3)+f3(n) が得られます。
n>6 のとき n の代わりに n-3 にして両辺に -1 をかければ、
-f(n-3)=-f(n-4)-f(n-5)+f(n-6)-f3(n-3) 、
また、n>3 のとき f3(n)=f3(n-3)+f4(n)
この3式を辺々加えて、簡単にすれば、
n>6 のとき f(n)=f(n-1)+f(n-2)-f(n-4)-f(n-5)+f(n-6)+f4(n) が得られます。
この式変形は続けられますが、式が長くなるので、ここで打ち切って、
「和が 13 になる式」のうち 最後の項が 4 以上の自然数であるものは、
13,9+4,8+5,7+6,5+4+4 だから、
f4(13)=13+9+8+7+5=42 、
「和が 14 になる式」のうち 最後の項が 4 以上の自然数であるものは、
14,10+4,9+5,8+6,7+7,6+4+4,5+4+4 だから、
f4(14)=14+10+9+8+7+6+5=59 、
f(13)=f(12)+f(11)-f(9)-f(8)+f(7)+f4(13)=399+275-128-86+54+42=556 、
f(14)=f(13)+f(12)-f(10)-f(9)+f(8)+f4(14)=556+399-192-128+86+59=780 です。
[参考] uch*n*anさんがプログラムで f(50) まで求めてくれました。
1,3,6,12,20,35,54,86,128,192,
275,399,556,780,1068,1463,1965,2644,3498,4630,
6052,7899,10206,13174,16851,21522,27294,34545,43453,54563,
68135,84927,105366,130462,160876,198014,242812,297201,362587,441546,
536104,649791,785437,947812,1140945,1371173,1644136,1968379,2351597,2805218
.