平成１９年１月１４日
[流れ星]
第1８４回数学的な応募問題解答
＜解答募集期間：１２月２４日〜１月１４日
［自然数の分割］
皆さん、今までのご愛顧に深く感謝しつつ、引き続き平成１９年もよろしくお願いします。
自然数ｎをいくつかの自然数の和として、ｎ＝ｎ１＋ｎ２＋・・・＋ｎｒ（ｒ≧１）
の形に表すことを考える。この分割の総数をＱ（ｎ）とする。
例えばｎ＝３のとき、１＋１＋１、１＋２、２＋１、３ の４通りに表されるから、Ｑ（３）＝４となる。
次に、項の順序を考えた１≦ｎ１≦ｎ２≦・・・≦ｎｒ のときの総数をＰ（ｎ）とする。
例えばｎ＝３のとき、１＋１＋１，１＋２，３の３通りになるからＰ（３）＝３となる。
さらに、ここで、ｎをこのような和で表すすべての表し方について、項の積 ｎ１×ｎ２×・・・×ｎｒ を考え、その最大値をＭ（ｎ） とする。例えばｎ＝３のとき、項の積は１×１×１＝１，１×２＝２，３となるから、Ｍ（３）＝３となる。
ここから、問題です。
問題１：Ｑ（ｎ）を求めよ。最初に、ｎ＝１，２，３，４，５，６と具体的に求めてから、考えてください。答えは指数の形でも良い。
問題２：Ｐ（ｎ）をｎで表したいのですが、未解決問題でして、そこで、ｎ＝１，２，３，４，５，６、７，８，と具体的に求めてから、ｎ＝20までのＰ（ｎ）を知りたい。ここは、オイラーの５角数定理を用いて、次の漸化式を利用してください。
Ｐ（ｎ）＝Ｐ（ｎ―１）＋Ｐ（ｎ―２）―Ｐ（ｎ―５）―Ｐ（ｎ―７）
＋Ｐ（ｎ―１２）＋Ｐ（ｎ―１５）―Ｐ（ｎ―２２）―Ｐ（ｎ―２６）＋・・・
ただし、Ｐ（０）＝１とする
問題３：Ｍ（ｎ）を求めよ。最初に、ｎ＝１，２，３，４，５，６、７、８と具体的に求めてから、考えてください。
＜参考文献１：数学の知性（ｗ・ダンハム著中村由子訳）「現代数学社」
２：オイラーの無限解析（高瀬正仁訳）「海鳴社」
３：整数の分割（佐藤文広訳）「数学書房」＞
＜水の流れコメント：参考文献の記述は平成１９年１月７日である＞
ＮＯ１「kashiwagi｣12/28 08時12分受信
更新1/14
184回
問1.着実に場合に分けて計算すると、
Q(1)＝1
Q(2)＝2
Q(3)＝4
Q(4)＝8
Q(5)＝16 であるから、推定してQ(ｎ)＝2ｎ-1
問2.これも地道に計算して、P（ｎ）のｎを変化させ以下の表を得る。
|
n |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
13 |
14 |
15 |
16 |
17 |
18 |
19 |
20 |
|
P（ｎ） |
1 |
2 |
3 |
5 |
7 |
11 |
15 |
22 |
30 |
42 |
56 |
77 |
101 |
135 |
176 |
231 |
297 |
385 |
490 |
627 |
問3.
最初は見当がつかなかったのですが、最大値を分解すると2と3の累乗で表せることに気づき、試行錯誤の結果、3の倍数、余り1及び余り2で分類すれば良いことが閃きました。
M(1)＝1
M(2)＝2
M(3)＝3
M(4)＝4
M(5)＝6
M(6)＝9
M(7)＝12
M(8)＝18
M(9)＝27
M(10)＝36
M(11)＝54
M(12)＝81
・ｎ＝3N の時 M（ｎ）＝3N 但し、N≧1
・ｎ＝3N+1 の時 M（ｎ）＝22×3N-1 但し、N≧0
・ｎ＝3N+2 の時 M（ｎ）＝2×3N 但し、N≧0
ＮＯ２「Toru」 12/28 12時54分受信 更新1/14
第１８４回解答を送ります。はやいものでもう今年もおわり、１年間いろいろ楽しい問題をありがとうございました。
最近はちょっと他のことが忙しくなって、数学に費やす時間が少なくなってしまっておりますが、それだけにここの
問題は貴重です。来年もよろしくお願いします。 ペンネーム Toru
問題１
n=1 1 でQ(1)=1
n=2 1+1,2 でQ(2)=2
n=3 1+1+1,1+2,2+1,3 でQ(3)=4
n=4 1+1+1+1,1+1+2,1+2+1,2+1+1,2+2,1+3,3+1,4でQ(4)=8
n=5 1+1+1+1+1,1+1+1+2,1+1+2+1,1+2+1+1,2+1+1+1 1+2+2,2+1+2,2+2+1,
1+1+3,1+3+1,3+1+1,1+4,4+1,2+3,3+2,5 でQ(5)=16
n=6 1+1+1+1+1+1,1+1+1+1+2,1+1+1+2+1,1+1+2+1+1.1+2+1+1+1,2+1+1+1+1,
1+1+2+2,1+2+1+2,1+2+2+1,2+1+1+2,2+1+2+1,2+2+1+1,
1+1+1+3,1+1+3+1,1+3+1+1,3+1+1+1,2+2+2,
1+2+3,1+3+2,2+1+3,2+3+1,3+1+2,3+2+1,1+1+4,1+4+1,4+1+1,
1+5,5+1,2+4,4+2,3+3,6 Q(6)=32
n個のおはじきを並べてn-1個の間に+を入れるか入れないかと考えれば
Q(n)=2^(n-1)となります。
問題２
上記よりP(1)=1,P(2)=2,P(3)=3,P(4)=5,P(5)=7 P(6)=11
n=7のとき
1+1+1+1+1+1+1,1+1+1+1+1+2,1+1+1+1+3,1+1+1+2+2,1+1+1+4,1+1+2+3,
1+2+2+2,1+1+5,1+2+4,1+3+3,2+2+3,1+6,2+5,3+4,7 で p(7)=15
n=8のとき
1+1+1+1+1+1+1+1,1+1+1+1+1+1+2,1+1+1+1+1+3,1+1+1+1+2+2
1+1+1+1+4,1+1+1+2+3,1+1+2+2+2,1+1+1+5,1+1+2+4,1+1+3+3,
1+2+2+3,2+2+2+2,1+1+6,1+2+5,1+3+4,2+2+4,2+3+3,1+7,2+6,3+5,4+4,
8 で22
漸化式を使うと
P(1)=1,P(2)=2
より
P(3)=P(1)+P(2)=3, P(4)=P(3)+P(2)=5, P(5)=P(4)+P(3)-P(0)=7,
P(6)=P(5)+P(4)-P(1)=11, P(7)=P(6)+P(5)-P(2)-P(0)=15
P(8)=P(7)+P(6)-P(3)-P(1)=22, P(9)=P(8)+P(7)-P(4)-P(2)=30,
P(10)=P(9)+P(8)-P(5)-P(3)=42,P(11)=P(10)+P(9)-P(6)-P(4)=56
P(12)=P(11)+P(10)-P(7)-P(5)+P(0)=77, P(13)=P(12)+P(11)-P(8)-P(6)+P(1)=101,
P(14)=P(13)+P(12)-P(9)-P(7)+P(2)=135,P(15)=P(14)+P(13)-P(10)-P(8)+P(3)+P(0)=
176,
P(16)=P(15)+P(14)-P(11)-P(9)+P(4)+P(1)=231
P(17)= P(16)+P(15)-P(12)-P(10)+P(5)+P(2)=297
P(18)=P(17)+P(16)-P(13)-P(11)+P(6)+P(3)=385
P(19)=P(18)+P(17)-P(14)-P(12)+P(7)+P(4)=490
P(20)= P(19)+P(18)-P(15)-P(13)+P(8)+P(5)=627
問題３ M(1)=1,M(2)=2,M(3)=3,M(4)=4,M(5)=2x3=6,M(6)=3x3=9,M(7)=2x2x3=12,
M(8)=2x3x3=18
ある因子nk≧４とするとこれを２とnk-2に分割すると 2(nk-2)-nk=nk-4≧0
よりさらに分割できるので各因子は3以下としてよい。
2^3<3^2だから2が３つあれば3を２つにした方がよいので2は２つ以下
1x1<2, 1x2<3,1x3<2x2だから1は含まない
よって
n=3kのとき因子はすべて３でM(n)=3^k
n=3k+1のとき２が２つと３が(k-1)個でM(n)=4x3^(k-1)
n=3k+2の時2が１つと３がk個 M(n)=2x3^k
ただしk=1,2,3,----で M(1)=1,M(2)=2
ＮＯ３「uchinyan」12/29 17時21分受信
1/14
何とか，第１８４回数学的な応募問題への解答が年内に間に合いました。送ります。
今回も結構奥が深く大変でした。しかも年末で，なかなか時間が取れなくて．．．
ただ，オイラーの５角数定理など，勉強になることも多く，楽しい時間を過ごせました。
2007年も宜しくお願い致します
第１８４回数学的な応募問題
［自然数の分割］
問題1：
取り敢えず，地道にやってみます。
n =
1 の場合，1 = 1 だけで，Q(1) = 1 通り。
n =
2 の場合，2 = 1 + 1 = 2 で，Q(2) = 2 通り。
n =
3 の場合，3 = 1 + 1 + 1 = 2 + 1 = 1 + 2 = 3 で，Q(3) = 4 通り。
n =
4 の場合，
4 =
1 + 1 + 1 + 1 = 2 + 1 + 1 = 1 + 2 + 1 = 1 + 1 + 2 = 3 + 1 = 2 + 2 = 1 + 3 = 4
で，Q(4) = 8 通り。
n =
5 の場合，
5
= 1
+ 1 + 1 + 1 + 1
= 2
+ 1 + 1 + 1 = 1 + 2 + 1 + 1 = 1 + 1 + 2 + 1 = 1 + 1 + 1 + 2
= 3
+ 1 + 1 = 2 + 2 + 1 = 2 + 1 + 2 = 1 + 3 + 1 = 1 + 2 + 2 = 1 + 1 + 3
= 4
+ 1 = 3 + 2 = 2 + 3 = 1 + 4 = 5
で，Q(5) = 16 通り。
n =
6 の場合，
6
= 1
+ 1 + 1 + 1 + 1 + 1
= 2
+ 1 + 1 + 1 + 1 = 1 + 2 + 1 + 1 + 1 = 1 + 1 + 2 + 1 + 1 = 1 + 1 + 1 + 2 + 1
= 1
+ 1 + 1 + 1 + 2= 3 + 1 + 1 + 1 = 2 + 2 + 1 + 1 = 2 + 1 + 2 + 1 = 2 + 1 + 1 + 2
= 1
+ 3 + 1 + 1 = 1 + 2 + 2 + 1 = 1 + 2 + 1 + 2 = 1 + 1 + 3 + 1 = 1 + 1 + 2 + 2
= 1
+ 1 + 1 + 3 = 4 + 1 + 1 = 3 + 2 + 1 = 3 + 1 + 2 = 2 + 3 + 1 = 2 + 2 + 2
= 2
+ 1 + 3 = 1 + 4 + 1 = 1 + 3 + 2 = 1 + 2 + 3 = 1 + 1 + 4 = 5 + 1 = 4 + 2
= 3 + 3 = 2 + 4 = 1 + 5 = 6
で，Q(6) = 32 通り。
さて，以上の計算から明らかですが，要するに，
n =
1 + 1 + ...(n個)... + 1 + 1
と 1 を n 個並べて，どこで区切って 1 のグループを作るか，という場合の数と同じです。
グループ内の 1 の和が，元の n を分割したときの数になり，それらの数の和が
n になります。
区切りを入れる隙間は n-1 箇所で，各箇所で区切るか区切らないかの 2 通りずつあるので，
Q(n)
= 2^(n-1) 通り，になります。
問題2：
何やら奥が深そうなのですが，それは(考察1)にまわして，取り敢えず，誘導どおりにやってみます。
P(6)までは，問題1：の途中結果が使えます。
n =
1 の場合，1 = 1 だけで，P(1) = 1 通り。
n =
2 の場合，2 = 1 + 1 = 2 で，P(2) = 2 通り。
n =
3 の場合，3 = 1 + 1 + 1 = 2 + 1 = 3 で，P(3) = 3 通り。
n =
4 の場合，
4
= 1
+ 1 + 1 + 1
= 2
+ 1 + 1
= 3
+ 1 = 2 + 2
= 4
で，P(4) = 5 通り。
n =
5 の場合，
5
= 1
+ 1 + 1 + 1 + 1
= 2
+ 1 + 1 + 1
= 3
+ 1 + 1 = 2 + 2 + 1
= 4
+ 1 = 3 + 2
= 5
で，P(5) = 7 通り。
n =
6 の場合，
6
= 1
+ 1 + 1 + 1 + 1 + 1
= 2
+ 1 + 1 + 1 + 1
= 3
+ 1 + 1 + 1 = 2 + 2 + 1 + 1
= 4
+ 1 + 1 = 3 + 2 + 1 = 2 + 2 + 2
= 5
+ 1 = 4 + 2 = 3 + 3
= 6
で，P(6) = 11 通り。
n =
7 の場合，
7
= 1
+ 1 + 1 + 1 + 1 + 1 + 1
= 2
+ 1 + 1 + 1 + 1 + 1
= 3
+ 1 + 1 + 1 + 1 = 2 + 2 + 1 + 1 + 1
= 4
+ 1 + 1 + 1 = 3 + 2 + 1 + 1 = 2 + 2 + 2 + 1
= 5
+ 1 + 1 = 4 + 2 + 1 = 3 + 3 + 1 = 3 + 2 + 2
= 6
+ 1 = 5 + 2 = 4 + 3
= 7
で，P(7) = 15 通り。
n =
8 の場合，
8
= 1
+ 1 + 1 + 1 + 1 + 1 + 1 + 1
= 2
+ 1 + 1 + 1 + 1 + 1 + 1
= 3
+ 1 + 1 + 1 + 1 + 1 = 2 + 2 + 1 + 1 + 1 + 1
= 4
+ 1 + 1 + 1 + 1 = 3 + 2 + 1 + 1 + 1 = 2 + 2 + 2 + 1 + 1
= 5
+ 1 + 1 + 1 = 4 + 2 + 1 + 1 = 3 + 3 + 1 + 1 = 3 + 2 + 2 + 1 = 2 + 2 + 2 + 2
= 6
+ 1 + 1 = 5 + 2 + 1 = 4 + 3 + 1 = 4 + 2 + 2 = 3 + 3 + 2
= 7
+ 1 = 6 + 2 = 5 + 3 = 4 + 4
= 8
で，P(8) = 22 通り。
そこで，これ以上は，与えられた漸化式，ただし P(n) の引数は正の整数又は 0 として，
P(n)
= P(n-1) + P(n-2) - P(n-5) - P(n-7) + P(n-12) + P(n-15) - P(n-22) - P(n-26) +
...
P(0)
= 1
を使って，計算があっていれば (^^;
P(9)
= P(8) + P(7) - P(4) - P(2) = 22 + 15 - 5 - 2 = 30
P(10)
= P(9) + P(8) - P(5) - P(3) = 30 + 22 - 7 - 3 = 42
P(11)
= P(10) + P(9) - P(6) - P(4) = 42 + 30 - 11 - 5 = 56
P(12)
= P(11) + P(10) - P(7) - P(5) + P(0) = 56 + 42 - 15 - 7 + 1 = 77
P(13)
= P(12) + P(11) - P(8) - P(6) + P(1) = 77 + 56 - 22 - 11 + 1 = 101
P(14)
= P(13) + P(12) - P(9) - P(7) + P(2) = 101 + 77 - 30 - 15 + 2 = 135
P(15) = P(14) + P(13) -
P(10) - P(8) + P(3) + P(0) = 135 + 101 - 42 - 22 + 3 + 1 = 176
P(16) = P(15) + P(14) -
P(11) - P(9) + P(4) + P(1) = 176 + 135 - 56 - 30 + 5 + 1 = 231
P(17) = P(16) + P(15) -
P(12) - P(10) + P(5) + P(2) = 231 + 176 - 77 - 42 + 7 + 2= 297
P(18) = P(17) + P(16) -
P(13) - P(11) + P(6) + P(3) = 297 + 231 - 101 - 56 + 11 + 3 = 385
P(19) = P(18) + P(17) -
P(14) - P(12) + P(7) + P(4) = 385 + 297 - 135 - 77 + 15 + 5 = 490
P(20) = P(19) + P(18) -
P(15) - P(13) + P(8) + P(5) = 490 + 385 - 176 - 101 + 22 + 7 = 627
...
になります。
(考察1)
「オイラーの５角数定理」というのはよく分からなかったので，Webで調べてみました。
ここでは，その調査結果をまとめておきます。なおこれは，
http://www.geocities.jp/ikuro_kotaro/koramu/383_ip.htm
に従っています。なお，このサイトには，少し難しいのですが，いろいろなことが書いてあるようです。
まず，P(n) の話から始めます。P(n) の定義は，今回の問題の最初にあるように，
[P(n)の定義]
自然数 n を幾つかの自然数の和として，
n = n1 + n2 + ... + n_r, r >= 1, n_r >= ... >= n2 >= n1
の形に表した場合，この分割の総数を P(n) とする。
[P(n)の定義終]
になります。これを n1, n2, ..., n_r に実際に現れる数に注目すると，
[P(n)の言い換え]
P(n)
は，自然数 n に対して，
n = 1 * k1 + 2 * k2 + 3 * k2 + ..., k1 >= 0, k2 >= 0, k3 >= 0, ...
となる (k1, k2, k3, ...) の個数である。
[P(n)の言い換え終]
と考えることもできます。例えば，
5
= 1
+ 1 + 1 + 1 + 1 = 1 * 5 ---> (5, 0, 0, 0, 0, ...すべて 0 ...)
= 2
+ 1 + 1 + 1 = 1 * 3 + 2 * 1 ---> (3, 1, 0, 0, 0, ...すべて 0 ...)
= 3
+ 1 + 1 = 1 * 2 + 2 * 0 + 3 * 1 ---> (2, 0, 1, 0, 0, ...すべて 0 ...)
= 2
+ 2 + 1 = 1 * 1 + 2 * 2 ---> (1, 2, 0, 0, 0, ...すべて 0 ...)
= 4
+ 1 = 1 * 1 + 4 * 1 ---> (1, 0, 0, 1, 0, ...すべて 0 ...)
= 3
+ 2 = 1 * 0 + 2 * 1 + 3 * 1 ---> (0, 1, 1, 0, 0, ...すべて 0 ...)
= 5
= 1 * 0 + 2 * 0 + 3 * 0 + 4 * 0 + 5 * 1 ---> (0, 0, 0, 0, 1, ...すべて 0 ...)
です。
この P(n) を「オイラーの分割関数」ともいうそうです。
さて，こうした準備をすると，次のことが分かります。
次のような式 f(x) を考えます。ただし，以下の議論では x の値は関係しないので，
適宜，無限級数が収束する範囲にある，と仮定して議論を進めます。
f(x)
=
(1 + x + x^2 + ...) * (1 + x^2 + x^4 + ...) * (1 + x^3 + x^6 + ...) * ...
= 1
+ P(1) * x^1 + P(2) * x^2 + P(3) * x^3 + P(4) * x^4 + P(5) * x^5 + ...
= Σ[n=0,∞]
P(n) * x^n
つまり，f(x) を展開した形式の多項式の x^n の係数が P(n) になっています。
その意味で，f(x) のことを P(n) の母関数といいます。
x^n の係数が P(n) になるのはどうしてかというと，
x^k1
を (1 + x + x^2 + ...) の一般項
x^(2
* k2) を (1 + x^2 + x^4 + ...) の一般項
x^(3
* k3) を (1 + x^3 + x^6 + ...) の一般項
...
などとすると，
n =
1 * k1 + 2 * k2 + 3 * k2 + ..., k1
>= 0, k2 >= 0, k3 >= 0, ...
となる項の和，展開する前の式の係数は 1 なので個数と同じ，が x^n の係数になる
ことから明らかでしょう。
そこで，f(x) を実際に展開してその係数を調べれば P(n) が求まります。
しかし，これは結構大変です。
そこで，さらに次のような工夫をします。(収束すると仮定したからできるわけですが。)
f(x)
=
(1 + x + x^2 + ...) * (1 + x^2 + x^4 + ...) * (1 + x^3 + x^6 + ...) * ...
=
1/(1 - x) * 1/(1 - x^2) * 1/(1 - x^3) * ...
= Π[m=1,∞]
1/(1 - x^m)
そこで，
Σ[n=0,∞] P(n) * x^n = Π[m=1,∞] 1/(1 - x^m)
Π[m=1,∞] (1 - x^m) * Σ[n=0,∞] P(n) * x^n = 1
(1
- x) * (1 - x^2) * (1 - x^3) * ... * {1 + P(1) * x^1 + P(2) * x^2 + P(3) * x^3
+ ...{ = 1
になります。
ここで，g(x) = Π[m=1,∞] (1 - x^m) = (1 - x) * (1 -
x^2) * (1 - x^3) * ... を展開してみると，
級数中の係数がすべて 0 か +1, -1 の級数になり，とても思い付きそうにないのですが (^^;，
Π[m=1,∞] (1 - x^m)
= 1
- x - x^2 + x^5 + x^7 - x^12 - x^15 + x^22 + x^26 - x^35 - x^40 + x^51 + ...
= Σ[m=-∞,∞]
{x^(6 * m^2 - m) - x^(6 * m^2 + 5 * m + 1)}
= Σ[m=-∞,∞]
(-1)^m * x^(m(3m-1)/2))
が得られます。正直に言うと，得られるそうです (^^;
ここで，最後は，2m, 2m+1 をまとめて m としています。
また，m は負を取りますが，指数の m(3m-1)/2 は負にならないことに注意してください。
さらに，指数が m(3m-1)/2，すなわち，1, 5, 12, 22, 35, 51, ... という数列になっており，
これがピタゴラスの五角数になっています！
さて，この式の意味を考えてみましょう。
g(x)
= Π[m=1,∞] (1 - x^m) = (1 - x) * (1 - x^2) * (1 -
x^3) * (1 - x^4) * (1 - x^5) * ...
= 1
+ a(1) * x^1 + a(2) * x^2 + a(3) * x^3 + a(4) * x^4 + a(5) * x^5 + ...
= Σ[n=0,∞]
a(n) * x^n
は，(1 - x^m) の -x^m
が集まって x^n を作っており，n = m1 + m2 + m3 + ... となっています。
しかも，m = 1, 2, 3, ... と異なる自然数なので，これは，n を異なる自然数に分割しています。
さらに，-x^m とマイナスがあるので，これの偶数個の積は +，奇数個の積は - で，
n を異なる偶数個の自然数に分割する総数を Peven(n)
n を異なる奇数個の自然数に分割する総数を Podd(n)
とすると，
Peven(n) - Podd(n) = a(n)
を表しています。そころが，a(n) は実際には，
a(n)
= (-1)^m, for n = m(3m-1)/2, m = -∞ 〜 ∞
a(n)
= 0, それ以外
なので，
Peven(n) - Podd(n) = (-1)^m, for n =
m(3m-1)/2, m = -∞ 〜 ∞
Peven(n) - Podd(n) = 0, それ以外
となります。
実際，例えば，
n =
8 の場合
偶数個の異なる自然数への分割は 7 + 1 = 6 + 2 = 5 + 3 の 3 通り
奇数個の異なる自然数への分割は 8 = 5 + 2 + 1 = 4 + 3 + 1 の 3 通り
なので，その差は 0 となります。
n =
5 の場合
偶数個の異なる自然数への分割は 4 + 1 = 3 + 2 の 2 通り
奇数個の異なる自然数への分割は 5 の 1 通り
なので，その差は 1 となります。
この g(x) = Π[m=1,∞] (1 - x^m) の解釈から導かれる性質を，
オイラーの５角数定理，というらしいです。
一応まとめておくと，
[オイラーの５角数定理]
数 n に対する補正項をe(n)とおいて
#{偶数個の異なる整数への分割} = #{奇数個の異なる整数への分割} + e(n)
ここで，
e(n) = (-1)^m for n = m(3m±1)/2
e(n) = 0 それ以外
である。なお，
Π[m=1,∞] (1 - x^m) = Σ[n=0,∞] e(n) * x^n
となっている。
[オイラーの５角数定理終]
さて，このことを使うと，
Π[m=1,∞] (1 - x^m) * Σ[n=0,∞] P(n) * x^n = 1
(Σ[m=-∞,∞]
(-1)^m * x^(m(3m-1)/2))) * (Σ[n=0,∞] P(n) * x^n) = 1
Σ[m=-∞,∞]Σ[n=0,∞] P(n) * (-1)^m * x^(m(3m-1)/2 + n) = 1
ここで，m(3m-1)/2 + n を改めて n とおくと，以前の n は n - m(3m-1)/2 になり，
これが 0 以上の範囲で和を求めることになります。
Σ[n=0,∞] {Σ[m=-∞,∞ : n - m(3m-1)/2 >= 0] P(n - m(3m-1)/2) *
(-1)^m} * x^n = 1
そこで，
P(0)
= 1
Σ[m=-∞,∞ : n - m(3m-1)/2 >= 0] P(n - m(3m-1)/2) * (-1)^m = 0
P(n)
- P(n-1) - P(n-2) + P(n-5) + P(n-7) - P(n-12) - P(n-15) + P(n-22) + P(n-26) -
... = 0
P(n)
= P(n-1) + P(n-2) - P(n-5) - P(n-7) + P(n-12) + P(n-15) - P(n-22) - P(n-26) +
...
が得られます。
これが，問題2：で与えられていた漸化式，というわけです。
(考察2)
P(n)
の計算は，実は以前に考えたことがありました。
やはり漸化式です。ナイーブな式なので，結構計算は大変ですが，一応，紹介しておきます。
P(n)
は，
n = n1 + n2 + ... + n_r, r >= 1, n_r >= ... >= n2 >= n1
ということなので，
m を少なくとも一つ含み
m 以上だけの数の和で n を 表す場合の数を P(n,m) とすると，
P(n,m) = 0 for m > n/2
P(n,n/2)
= 1 for n：偶数
P(n)
= P(n,1) + P(n,2) + ... + P(n,[n/2]) + 1
P(n,m) = 1 + P(n-m,m) + P(n-m,m+1)
+ ... + P(n-m,m+k) for m+k
>= [(n-m)/2]
P(n,m) = 1 for m < [(n-m)/2]
ただし，[ ] はガウス記号です。特に
P(n,1)
= 1 + P(n-1,1) + P(n-1,2) + ... + P(n-1,[(n-1)/2]) = P(n-1)
具体的には，
P(1)
= 1
P(2)
= P(2,1) + 1 = 2
P(3)
= P(3,1) + 1 = P(2) + 1 = 3
P(4)
= P(4,1) + P(4,2) + 1 = P(3) + 1 + 1 = 3 + 1 + 1 = 5
P(5)
= P(5,1) + P(5,2) + 1 = f(4) + 1 + P(3,2) + 1 = 5 + 1 + 0 + 1 = 7
P(6) = P(6,1) + P(6,2) +
P(6,3) + 1 = P(5) + 1 + P(4,2) + 1 + 1= 7 + 1 + 1 + 1 + 1= 11
P(7) = P(7,1) + P(7,2) +
P(7,3) + 1 = P(6) + 1 + P(5,2) + 1 + 1 = 11 + 1 + 1 + 1 + 1= 15
P(8) = P(8,1) + P(8,2) +
P(8,3) + P(8,4) + 1 = P(7) + 1 + P(6,2) + P(6,3) + 1 + 1 + 1
=
15 + 1 + 1 + P(4,2) + 1 + 1 + 1 + 1
=
15 + 1 + 1 + 1 + 1 + 1 + 1 + 1
=
22
P(9)
= P(9,1) + P(9,2) + P(9,3) + P(9,4) + 1
=
P(8) + 1 + P(7,2) + P(7,3) + 1 + P(6,3) + 1 + 1
=
22 + 1 + 1 + P(5,2) + 1 + 1 + 1 + 1 + 1
=
22 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1
=
30
P(10)
= P(10,1) + P(10,2) + P(10,3) + P(10,4) + P(10,5) + 1
=
P(9) + 1 + P(8,2) + P(8,3) + P(8,4) + 1 + P(7,3) + 1 + 1 + 1
=
30 + 1 + 1 + P(6,2) + P(6,3) + 1 + 1 + 1 + 1 + 3
=
30 + 2 + 1 + P(4,2) + 1 + 7
=
30 + 3 + 1 + 8
=
42
P(11)
= P(11,1) + P(11,2) + P(11,3) + P(11,4) + P(11,5) + 1
=
P(10) + 1 + P(9,2) + P(9,3) + P(9,4) + 1 + P(8,3) + P(8,4) + 1 + 1 + 1
=
42 + 1 + 1 + P(7,2) + P(7,3) + 1 + P(6,3) + 1 + 1 + 1 + 1 + 3
=
42 + 2 + 1 + P(5,2) + 1 + 1 + 1 + 7
=
42 + 3 + 1 + 10
=
56
P(12)
= P(12,1) + P(12,2) + P(12,3) + P(12,4) + P(12,5) + P(12,6) + 1
=
P(11) + 1 + P(10,2) + P(10,3) + P(10,4) + P(10,5) + 1 + P(9,3) + P(9,4) + 1 +
P(8,4) + 1 + 1 + 1
=
56 + 1 + 1 + P(8,2) + P(8,3) + P(8,4) + 1 + P(7,3) + 1 + 1 + 1 + 1 + P(6,3) + 1
+ 1 + 1 + 3
=
56 + 2 + 1 + P(6,2) + P(6,3) + 1 + 1 + 1 + 1 + 4 + 1 + 6
=
56 + 3 + 1 + P(4,2) + 1 + 15
=
56 + 4 + 1 + 16
=
77
P(13)
= P(13,1) + P(13,2) + P(13,3) + P(13,4) + P(13,5) + P(13,6) + 1
=
P(12)
+ 1
+ P(11,2) + P(11,3) + P(11,4) + P(11,5)
+ 1
+ P(10,3) + P(10,4) + P(10,5)
+ 1
+ P(9,4)
+ 1
+ 1 + 1
=
77
+ 1
+ 1 + P(9,2) + P(9,3) + P(9,4) + 1 + P(8,3) + P(8,4) + 1 + 1
+ 1
+ 1 + P(7,3) + 1 + 1
+ 1
+ 1
+ 3
=
77
+ 2
+ 1 + P(7,2) + P(7,3) + 1 + P(6,3) + 1 + 1 + 1 + 1 + 2
+ 2
+ 1 + 2
+ 5
=
77
+ 3
+ 1 + P(5,2) + 1 + 1 + 1 + 6
+
10
=
77 + 4 + 1 + 9 + 10
=
101
...
などです。P(13) までは，確かに一致しています。
これ以上も可能ですが，計算が大変なので，以下省略します。
問題3：
これも，取り敢えず，地道にやってみます。
問題2：の途中結果が使えます。右側に不等式で最大以外の積も書いておきます。
M(1)
= 1
M(2)
= 2 > 1
M(3)
= 3 > 2 > 1
M(4)
= 4 > 3 > 2 > 1
M(5)
= 6 > 5 > 4 > 3 > 2 > 1
M(6)
= 9 > 8 > 6 > 5 > 4 > 3 > 2 > 1
M(7)
= 12 > 10 > 9 > 8 > 7 > 6 > 5 > 4 > 3 > 2 > 1
M(8)
= 18 > 16 > 15 > 12 > 10 > 9 > 8 > 7 > 6 > 5 > 4
> 3 > 2 > 1
最大を並べてみると，
1,
2, 3, 4, 6, 9, 12, 18, ...
これを見ると，どうやら，因数に 2, 3 だけを含む場合になるようです。
そこで，これを念頭に置きながら考えてみました。
問題は，
n = n1 + n2 + ... + n_r, r >= 1, n_r >= ... >= n2 >= n1 >= 1
において，n1 * n2 * ... * n_r の最大値 M(n) を求めよ。
となります。
今，n1, n2, ..., n_r は，M(n) を与えるものとします。すると次のことがいえます。
まず，n1, n2, ..., n_r には，1 は含まれません。
もし含まれたとすると，n1 = 1 となります。
このとき，1 と n2 を足した 1 + n2 を一つの項とする分割が存在します。そして，
n1
* n2 * n3 * ... * n_r = n2 * n3 * ... * n_r
(1
+ n2) * n3 * ... * n_r = n3 * ... * n_r + n2 * n3 * ... * n_r
n3
* ... * n_r >= 1 なので，
(1
+ n2) * n3 * ... * n_r > n1 * n2 * n3 * ... * n_r
です。これは，n1 * n2 * ... * n_r が最大であることに矛盾します。
次に，n1, n2, ..., n_r には，5 以上は含まれません。
もし含まれたとすると，例えば，n_k >= 5, r
>= k >= 1 となります。
このとき，n_k を 2 と n_k - 2 >= 3 の二つに分ける分割が存在します。 そして，
n1
* n2 * ... * 2 * (n_k - 2) * ... * n_r - n1 * n2 * ... * n_k * ... *
n_r
=
n1 * n2 * ... * (n_k - 4) * ... * n_r
> 0
n1
* n2 * ... * 2 * (n_k - 2) * ... * n_r > n1 * n2 * ... * n_k *
... * n_r
です。これは，n1 * n2 * ... * n_r が最大であることに矛盾します。
そして，n1, n2, ..., n_r には，4 を含める必要はありません。
これは，先ほどの議論で n_k = 4 とすると，積が同じになってしまうので，
最初から，4 を 2 + 2 と分割したもので考えれば十分だからです。
結局，ここまでで，n1, n2, ..., n_r には，2 と 3 しか含まれないことが分かりました。
さらに，2 の個数に関して，2 は 2 個以下しか含まれない，ことが，次のようにして分かります。
2 が
m >= 3 個あったとします。この和は 2m >= 6 ですが，これを 3 で分割し直すことができて，
2m
= 3k or 3k + 1 or 3k + 2, k >= 2
と書けます。1 は先ほどの議論から分割には含められないので，少し変えて，
2m が
3 の倍数のとき：2m = 3k
2m が
3 で割って 1 余るとき：2m = 3(k-1) + 2 + 2
2m が
3 で割って 2 余るとき：2m = 3k + 2
と，2 の個数が 2 個以下になるユニ分割し直すことができます。
このときの積は，最初の分割で 2 以外の積を N とすると，
再分割前 N * 2^m
再分割後 N * 3^k or N * 3^(k^1) * 4 or N * 3^k * 2
これらの大小を比を取って調べます。ただし，値は正なので二乗して調べても同じなので，そうします。
・2m が 3 の倍数のとき：2m = 3k
(N
* 3^k)^2/(N * 2^m)^2 = 3^2k/2^2m = 3^2k/2^3k = (9/8)^k > 1
つまり，再分割後の方が大きくなります。
・2m が 3 で割って 1 余るとき：2m = 3(k-1) + 2 + 2
(N
* 3^(k-1) * 4)^2/(N * 2^m)^2 = 3^(2k-2) * 16/2^2m
=
3^(2k-2) * 16/2^(3k+1) = 3^(2k-2)/2^(3k-3) = (9/8)^(k-1) > 1 (k >= 2)
つまり，再分割後の方が大きくなります。
・2m が 3 で割って 2 余るとき：2m = 3k + 2
(N
* 3^k * 2)^2/(N * 2^m)^2 = 3^2k * 4/2^2m
=
3^2k * 4/2^(3k+2) = 3^2k/2^3k = (9/8)^k > 1
つまり，再分割後の方が大きくなります。
結局，いずれの場合も，3 で再分割した後の方が積は大きくなります。
これで，M(n) を与える n1, n2, ..., n_r には，
2 と
3 しか含まれず，しかも，2 は 2 個以下しか含まれない，
ことが分かりました。
以上のことから，n をできるだけ 3 で分割して 2 の個数が 2 個以下になるようにしたとき，
分割で現れる数の積は最大になることが分かります。
これは，n を 3 で割って，余りが 1 になっときだけ，2 を 2 個使う分割にすることと同じです。
結局，n >= 1 として，
・n が 3 で割って 0 余るとき：M(n) = 3^(n/3)
・n が 3 で割って 1 余るとき：M(n) = 4 * 3^((n-4)/3) for n >= 4, M(1) = 1
・n が 3 で割って 2 余るとき：M(n) = 2 * 3^((n-2)/3)
になります。
(考察3)
意味があるのかどうかよく分かりませんが，分割を実数まで拡張すると，
ちょっと面白いことが分かります。
今，正の実数 a が与えられたとして，
これを k 個の正の実数 a(1), a(2), ..., a(k) に分割したとします。
a(1)
+ a(2) + ... + a(k) = a
このときの，M(a) = a(1) * a(2) * ... * a(k) の最大を考えます。
最初に，k を固定して考えます。
正の実数を考えているので，相加相乗平均から
a/k
= (a(1) + a(2) + ... + a(k))/k >= (a(1) * a(2) * ... * a(k))^(1/k) =
(M(a))^(1/k)
なので，M(a) の最大値は，a(1) = a(2) = ... = a(k) のときで，(a/k)^k になります。
つまり，a を k 個に分割したときの最大値は (a/k)^k になります。
次に，k を 1, 2, 3, 4, ... と変化させたときに，(a/k)^k がどのように変化するかを調べます。
k は自然数ですが，様子を調べるために，正の実数
x に拡張して，y = (a/x)^x のグラフを考えます。
底を e とする自然対数を取って，
log(y)
= x * (log(a) - log(x))
両辺を x で微分して
y'/y
= (log(a) - log(x)) + x * (- 1/x) = log(a) - log(x) - 1 = log(a/e * 1/x))
y'
= 0 は x = a/e で，y > 0 なので，x = a/e の前後で，y' は + -> 0 -> - となり，
y は
x = a/e で最大値 e^(a/e) を取ります。
x は実際には自然数
k なので，a/e を計算してそれをはさむ二つの整数のどちらかで，
(a/k)^k
が，したがって，M(a) が最大値を取ることになります。
問題2：に戻ると，a は自然数 n，a(1), a(2), ..., a(k) も自然数 n1, n2, ..., n_r なので，
a(1)
= a(2) = ... = a(k) が成立するとは限らず，その後の議論もうまくは行きません。
しかし，e = 2.71828... で 2 と 3 の間，しかも，3 に近いことを考えると，
最大値を与える x = a/e は r = n/3 に近く，最大値 M(a) = e^(a/e) は M(n) = 3^r に近く，
近似的に数値の間でも対応関係が見て取れると思います。
(感想)
今回も結構奥が深く大変でした。しかも年末で，なかなか時間が取れなくて．．．(^^;
ただ，オイラーの５角数定理など，勉強になることも多く，楽しい時間を過ごせました。
2007年も宜しくお願い致します
m(__)m
ＮＯ４「浜田明巳」01/04 12時01分受信 1/14
| ｎ | Ｑ(ｎ) | Ｐ(ｎ) | Ｍ(ｎ) |
| 1 | 1 | 1 | 1 |
| 2 | 2 | 2 | 2 |
| 3 | 4 | 3 | 3 |
| 4 | 8 | 5 | 4 |
| 5 | 16 | 7 | 6 |
| 6 | 32 | 11 | 9 |
| 7 | 64 | 15 | 12 |
| 8 | 128 | 22 | 18 |
| 9 | 256 | 30 | 27 |
| 10 | 512 | 42 | 36 |
| 11 | 1024 | 56 | 54 |
| 12 | 2048 | 77 | 81 |
| 13 | 4096 | 101 | 108 |
| 14 | 8192 | 135 | 162 |
| 15 | 16384 | 176 | 243 |
| 16 | 32768 | 231 | 324 |
| 17 | 65536 | 297 | 486 |
| 18 | 131072 | 385 | 729 |
| 19 | 262144 | 490 | 972 |
| 20 | 524288 | 627 | 1458 |
これにより，Ｑ(ｎ)＝２ｎ−１となることが分かるが，Ｐ(ｎ)，Ｍ(ｎ)については残念ながら分からない．
Option Explicit
Const n_max As Integer = 20
Public a(n_max, 2) As Integer
Public n As Integer
Sub Macro1()
Sheets("Sheet1").Select
Dim j As Integer
For n = 1 To n_max
Cells(n, 1).Value = n
For j = 2 To 4
Cells(n, j).Value = 0
Next j
For j = 1 To 2
Call saiki(1, j)
Next j
Next n
End Sub
Sub saiki(ByVal p As Integer, ByVal q As Integer)
Dim wa As Integer
Dim seki As Long
Dim j As Integer
If q = 1 Or (p = 1 And q = 2) Then
a(p, q) = 1
Else
a(p, q) = a(p - 1, q)
End If
While a(p, q) <= n
wa = 0
For j = 1 To p
wa = wa + a(j, q)
Next j
If wa < n And p < n Then
Call saiki(p + 1, q)
ElseIf wa = n Then
Cells(n, q + 1).Value = Cells(n, q + 1).Value + 1
If q = 2 Then
seki = 1
For j = 1 To p
seki = seki * a(j, 2)
Next j
If Cells(n, 4).Value < seki Then
Cells(n, 4).Value = seki
End If
End If
End If
a(p, q) = a(p, q) + 1
Wend
End Sub
