FC2ブログ

Welcome to my blog

[答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

.

スポンサーサイト



Comments 17

There are no comments yet.
アキチャン  
No title

おはようございます。
ハツユキカズラ、家のも今年はとても色づいてます(o^-^o)

こっこちゃん  
No title

おはようございます !(^^)!

ハツユキカズラ 年中美しく咲いてくれるので

嬉しいですよね この時期 名前からも涼しさ貰え嬉しいですよね
ナイス☆

樹☆  
No title

おはようございます
友達のとこに咲いてますが・・
初めは、こんなピンクや白で可愛かlったのに色が
かわって嘆いてました。
発色させるのは難しいのでしょうか。ナイス

ニリンソウ  
No title

ハツユキカズラは今が一番美しいです!
寒さにも暑さにもめげずに前進あるのみです。

ナイス

スモークマン  
No title

グーテンターク ^^
これも面白かったんだけど..何せわたしにゃ複雑すぎぃ~... ^^;
so...途中で思考放棄…Orz
解答の解読に努めてみたいと思います^^☆

uch*n*an  
No title

うーむ,これはなかなか大変でした。ただ,いろいろと考えられて楽しかったです (^^;
>よって、f(n) は「和が n になる式」全部の最初の項の総和 とも言えます。
このアイディアは秀逸ですね。とても思い付かなかった。
もっとも,これに思い付いたとしてもそれ以降の議論に思い至るのも難しそうです。
私の解法は三つ。
(解法1)は,a 項の和が b 個あることを状態 (a,b) と書くことにして,
これを n = 1 ~ 14 で順次調べる,という解法です。一見大変そうですが,
やってみるとチェック自体は単純な繰り返しで,面倒ではありますが,
面白いように例として挙げられている f(n) の値を再現でき,答えにも自信が持てました。
(解法2)は,(解法1)の改良版で,既存の f(n) の値を使って新たな f(n) の値を求めるものです。
手法は全く違うのですが,結果として[解答]と似たような式が出てきます。
ただし,私の式の方が複雑です。

uch*n*an  
No title

(解法3)は,手計算よりもプログラムに向く漸化式っぽい単純な解法で,
自然数 n を m 以上の自然数 k 個の和にするのを a(n,m,k) 通りとすると,
a(n,m,k) = Σ[i=m,[(n-m)/2]]{a(n-m,i,k-1)} + a(n-m,n-m,k-1),a(n,n,1) = 1,他は 0
f(n) = Σ[m=1,[n/2]]{Σ[k=2,[n/m]]{k * a(n,m,k)}} + 1
と書けることを使いました。[参考]の結果はこれをプログラムにして計算したものです。

tsuyoshik1942  
No title

「解答」ならびにuchinyanさんのコメント読ませていただきました。
一読、二読すれど未消化です。難しく、面倒な問題であったこと、再認識しました。

自分の解答は、いわゆるカンニングです。
解答送信後、再考しましたが、結局分からずじまいでした。
ただ、PCの力を借り、f(13),f(14)の値だけは、きちんと確認しました。

さっちゃんこ  
No title

今日は
ハツユキカズラは真夏の暑さにもめげず何時見ても爽やかな感じがして良いですネ

ナイス☆彡

ヤドカリ  
No title

アキチャンさん、早速のコメントとナイス!を有難うございます。
ハツユキカズラはよく見られますね。
上手く色づけばいいですね。

ヤドカリ  
No title

こっこちゃんさん、早速のコメントとナイス!を有難うございます。
やはり夏に涼しさを感じさせる花ですね。
ハツユキソウもハツユキカズラも好きな植物です。

ヤドカリ  
No title

樹ちゃん、早速のコメントとナイス!を有難うございます。
私は見つけて撮るだけですので、育て方は分かりませんが、
方々で見られる素敵な花です。

ヤドカリ  
No title

ニリンソウさん、早速のコメントを有難うございます。
よく目にするハツユキカズラ、今が一番美しいですね。
朝に散歩した時もよく癒されます。

ヤドカリ  
No title

スモークマンさん、コメントを有難うございます。
けっこう面倒な問題だったと思います。

ヤドカリ  
No title

uch*n*anさん、コメントを有難うございます。
最初の項の総和であることを利用しても、
簡潔な形にはまとまりませんでした。
最初の項の総和をテーマに問題にして、
もっとスッキリ解ける問題にしたかったのですが、
思うようにできませんでした。

ヤドカリ  
No title

tsuyoshik1942さん、コメントを有難うございます。
真っ先に解答を送られたので、調べればこの数列もありました。
プログラムを組めば、f(13),f(14)は求められますね。

ヤドカリ  
No title

さっちゃんこさん、コメントとナイス!を有難うございます。
真夏に爽やかに咲いてくれる花に癒されます。
今年は気温は例年より低いものの湿度が高くてまいりました。