[答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 になる式」全部の最初の項の総和 とも言えます。

　ここで、f_k(n) を

　「和が n になる式」のうち 最後の項が k 以上の自然数であるもの全部の最初の項の総和 とすれば、

　f₁(n)＝f(n) で、

　f_k(n) を求めるとき 最後が「＋k」で終わる式と それ以外の式に分けて考えれば、

　n＞k のとき f_k(n)＝f_k(n－k)＋f_k+1(n) になります。

　従って、

　n＞1 のとき f₁(n)＝f₁(n－1)＋f₂(n) 、

　すなわち、f(n)＝f(n－1)＋f₂(n) が得られます。

　n＞3 のとき n の代わりに n－2 にして両辺に －1 をかければ、

　－f(n－2)＝－f(n－3)－f₂(n－2) 、

　また、n＞2 のとき f₂(n)＝f₂(n－2)＋f₃(n)

　この３式を辺々加えて、簡単にすれば、

　n＞3 のとき f(n)＝f(n－1)＋f(n－2)－f(n－3)＋f₃(n) が得られます。

　n＞6 のとき n の代わりに n－3 にして両辺に －1 をかければ、

　－f(n－3)＝－f(n－4)－f(n－5)＋f(n－6)－f₃(n－3) 、

　また、n＞3 のとき f₃(n)＝f₃(n－3)＋f₄(n)

　この３式を辺々加えて、簡単にすれば、

　n＞6 のとき f(n)＝f(n－1)＋f(n－2)－f(n－4)－f(n－5)＋f(n－6)＋f₄(n) が得られます。

　この式変形は続けられますが、式が長くなるので、ここで打ち切って、

　「和が 13 になる式」のうち 最後の項が 4 以上の自然数であるものは、

　13，9＋4，8＋5，7＋6，5＋4＋4 だから、

　f₄(13)＝13＋9＋8＋7＋5＝42 、

　「和が 14 になる式」のうち 最後の項が 4 以上の自然数であるものは、

　14，10＋4，9＋5，8＋6，7＋7，6＋4＋4，5＋4＋4 だから、

　f₄(14)＝14＋10＋9＋8＋7＋6＋5＝59 、

　f(13)＝f(12)＋f(11)－f(9)－f(8)＋f(7)＋f₄(13)＝399＋275－128－86＋54＋42＝556 、

　f(14)＝f(13)＋f(12)－f(10)－f(9)＋f(8)＋f₄(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

.