自然数分割の問題

質問

与えられた自然数ｎを３個の自然数の和への分割の仕方の数をp(n,3)と書きます。
例えば、n=6の分割は4+1+1,3+2+1,2+2+2の３通りですから
p(6,3)=3が言えます。

このとき、p(n,3)={n^2/12}が成り立つことが知られています。但し、{}はその中の数を四捨五入することを表わします。
この式の証明は差分方程式の理論を使って行われますが、
問題の意味は誰でも分かるので、証明も誰でも分かるような（所謂初等的な)ものがあればうれしいです。

あるかどうかわかりませんが、そのような証明をご存知の方、或いは知らないけれど「このような方針ではどうか」等のアドバイスがあればお答えよろしくお願いします。

回答No.8

stomachman · ベストアンサー

一般にnをk項の和に分解する場合はどうなるか、あくまで「初等的」の範囲で、検討してみました。

　nをk個の項の和に分けることを、
n = s[1]+2s[2]+…+n s[n]
と表現することにします。ただし、
s[j]≧0, s[1]+s[2]+…+s[n] = k
です。
　これは「nを(s[1]個の1),(s[2]個の2),…,(s[n]個のn )の和に分解した」という意味です。従って、列<s[1],s[2],…>によって分け方を表せます。（この記法を使えば、分割した「かけら」の並び順を心配する必要はありませんね。）

　このような列s全部の集合をS(n,k)と書きましょう。すると明らかに、ご質問のp(n,k)はS(n,k)の濃度（要素の個数）に等しい。すなわち
p(n,k) = ｜S(n,k)｜
です。たとえば
S(6,3)={<2,0,0,1,0,0>,<1,1,1,0,0,0>,<0,3,0,0,0,0>}
ですから、
p(6,3)=3
となります。

　さて、S(6,3)の３つの要素は、以下のどちらかの方法で「生成」された、と解釈できます。

S(n,k)の任意の要素sに対して、
(A) 生成規則A[n-1,k-1]: (k-1≧0のとき）
　列tがt∈S(n-1,k-1)であって、
s[1]=t[1]+1
s[j]=t[j](j≧2)
であるような、そういうtがただ一つ存在する。
(B) 生成規則B[n-k,k]: (n-k≧kのとき）
　列t がt∈S(n-k,k)であって、
s[1]=0
s[j] = t[j-1](j≧2)
であるような、そういうtがただ一つ存在する。

　（ここで「A[n-1,k-1]」「B[n-k,k]」は規則を示す記号です。） 列を作る方法は(A)(B)どちらかであって他にはありませんし、生成規則の条件である(k-1≧0のとき）あるいは(n-k≧kのとき）が成り立つなら、生成されます。(これは証明するまでもないほど自明だと思います。）だから、要素s=<2,0,0,1,0,0>と要素s=<1,1,1,0,0,0>はどちらも生成規則A[5,2]によって、また、要素s=<0,3,0,0,0,0>は生成規則B[3,3]によって生成されたことになります。

　具体例を見てみましょう。（なお、以後、<>の末尾側にある0の連なり<　,0,0,0,…,0>の部分は省略して書くことにします。）

S(1,1)={<1>}
です。（つまりn=1を1個の項に分割する方法は1通りです。）これから、
S(2,1)={<0,1>} ∵B[1,1]より（A[1,0]は使えない。）
S(3,1)={<0,0,1>} ∵B[2,1]より（A[2,0]は使えない。）
S(4,1)={<0,0,0,1>} ∵B[3,1]より（A[3,0]は使えない。）
：
となります。これらを出発点にして、
S(1,1)={<1>}　
S(2,2)={<2>}　∵A[1,1]より（B[0,2]は使えない。）
S(3,3)={<3>} ∵A[2,2]より（B[0,3]は使えない。）
：
S(2,1)={<0,1>}
S(3,2)={<1,1>}　∵A[2,1]より(B[1,2]は使えない。）
S(4,3)={<2,1>}　∵A[3,2]より(B[1,3]は使えない。）
：
S(3,1) ={<0,0,1>}
S(4,2)={<1,0,1>, <0,2>}　∵A[3,1]とB[2,2]より。
S(5,3)={<2,0,1>, <1,2>}　∵A[4,2]より（B[2,3]は使えない。）
：
S(4,1)={<0,0,0,1>}
S(5,2)={<1,0,0,1>,<0,1,1>} ∵A[4,1]とB[3,2]より。
S(6,3)={<2,0,0,1>,<1,1,1>,<0,3>} ∵A[5,2]と、B[3,3]より。
S(7,4)={<3,0,0,1>,<2,1,1>,<1,3>} ∵A[6,3]より。（B[3,4]は使えない。）
S(8,5)={<4,0,0,1>,<3,1,1>,<2,3>} ∵A[7,4]より。（B[3,5]は使えない。）
：
てなことになります。

　要素の個数pについて書き直してみると、要するに、
(i) p(n,1) = 1
(ii) p(k,k)=1
(iii) 2k＞n＞k　→ p(n,k)=p(2(n-k),n-k)
(iv) n≧2k → p(n,k)=p(n-k,k)+p(n-1,k-1)
という漸化式になっています。(iii)はk-1個の「初項」を定めるだけなので、漸化式として本質的なのは(iv)だけですね。

k=2の場合、
(i) p(n,1) = 1
(ii) p(2,2)=1
(iii)p(3,2)=p(2,1)=1
(iv) n≧4 → p(n,2)=p(n-1,1)+p(n-2,2)=p(n-2,2)+1
だから、
n≧4のとき、m=floor(n/2)-1とおくと、（floor()は切り捨て関数）
p(n,2)=p(n-2,2)+1=p(n-4,2)+2=…=p(n-2m,2)+m
となり、
n-2m=n-2floor(n/2)+2=2または3
だから、p(2,2)=p(3,2)=1によって、
p(n-2m,2)=1
従って
p(n,2)=m+1
と決まります。すなわち、
p(n,2)=floor(n/2)
である。
さて、
p(3,2)=floor(3/2)=1
p(2,2)=floor(2/2)=1
であるから、結局、
n≧2 → p(n,2)=floor(n/2)
となります。これはfloor(x+1/2)={x}（{}は四捨五入）を使って、
n≧2 → p(n,2)={(n-1)/2}
と書いても同じです。（確かに、既知の結果と一致します。）

k=3の場合にも同じように力づくでやろうとすると、floor()関数の項が沢山並ぶことになる訳で、きっと場合分けが一杯生じて面倒でしょう。「差分方程式の理論」に任せた方が良さそうです。
でも、結果は{(n^2)/12}、つまりfloor関数1個で表せる形にまとまるのでした。ならばkが4以上の場合も、綺麗に整理できるに違いと予想できます。

お礼

取敢えず、初等的には示せないようだと言うことを結論としたいと思います。
他の方々も含め、回答有難うございました。

回答No.7

stomachman

No.6の

> そのうちのA通りがe=rとなる。

を

「そのうちのA通りがe=2rとなる。」

に訂正。

回答No.6

stomachman

久しぶりに眺めてたら、まだ閉めてないのを発見。で、もう一回考えてみたんです。
そしたら、ま、結局同じ事なんですが、ちょっと違う表現で綺麗に完結したのでupします。

　自然数nを1以上の３つの自然数a,b,cの和で表す。ただし、a≧b≧cとなるようにする。このうちで、
a=b=cになってる場合の数をA
a≠b=cまたはa=b≠cになってる場合の数をB
a≠b≠c≠aになってる場合の数をC
とするとき、A+B+Cを求める。

　さて、a,b,cの順番を入れ替えたものを別ものとして数えれば(n-1)(n-2)/2通りある。だから、
A+(3!/2!)B+(3!)C = (n-1)(n-2)/2
は自明である。なので、A,Bが分かればCも分かる。すなわち：
C = (n-1)(n-2)/12-A/6-B/2

　ところで求めるのはA+B+Cであるから、
A+B+C = 5A/6+B/2+(n-1)(n-2)/12
= (n^2)/12-n/4+1/6+5A/6+B/2
です。

●Aはnが3の倍数の時1, さもなくば0である。

●Bは、nを偶数１個e≧2と残りr≧1に分けるのが(ceil(n/2)-1)通りあり、そのうちのA通りがe=rとなる。従って、B=(ceil(n/2)-1-A)通りである。（ceil()は切り上げ関数です。）

まとめると
A+B+C = (n^2)/12-n/4+ceil(n/2)/2-α
と書ける。ただし、
(1) nが３の倍数のとき　α=0
(2) nが３の倍数でないとき　α=1/3

　あとは、
A+B+C={(n^2)/12}
つまり
(n^2)/12-1/2≦ A+B+C ＜(n^2)/12+1/2　…(X)
を証明すりゃいいですね。

切り上げの性質から、
0≦ceil(n/2)/2-n/4＜1/2
と言える。なので、
A+B+C-1/2＜A+B+C+n/4-ceil(n/2)/2≦A+B+C
すなわち
A+B+C-1/2＜(n^2)/12-α≦A+B+C
だから、
(n^2)/12-α≦A+B+C＜(n^2)/12-α+1/2
となる。

(1) α=0を代入すると
(n^2)/12≦A+B+C＜(n^2)/12+1/2
となって、(X)を満たす。
(2) α=1/3を代入すると
(n^2)/12-1/3≦A+B+C＜(n^2)/12-1/3+1/2
となって、(X)を満たす。

Q.E.Dデス。

回答No.5

stomachman

ううむ。初等的というのなら、こういうのはどうです？

n=a+b+c、a≧b≧c≧1
において、<b,c> を直交座標系だと思えば、
n-b-c≧b≧c≧1
とはすなわち
n≧2b+c、b≧c、c≧1
の三角形領域に含まれる格子点の個数を数える問題です。で、その個数は
[n/3]≧c≧1、n≧2b+c≧1-(n mod 3)
の平行四辺形に含まれる格子点の個数の丁度半分になることが簡単に示せます。

この平行四辺形は高さ(c)がだいたいn/3, 幅(b)がだいたいn/2ですから、格子点の数はだいたい(n^2)/６。あとはまじめに場合分けかな？

もっと鮮やかな手、ないでしょうかねえ。

お礼

しばらくぶりですので、忘れ去られているとは思いますが、感想を述べさせてもらいます。

整数論の相互法則の高木貞治博士による証明と似たような方針と言う事ですよね。
面白い方法だと思いますし、この流れから自然数分割と整数論が結びついてくるかも知れませんので良く検討してみたいと思います。

回答No.4

stomachman

No.3の訂正。
{x}は切り捨てだと勘違いして書いてます。{x}のところを[x]と読み替えて下さい。

ついでに、
「●n=a+b+m(a≧b≧m)すなわちn-3(m-1)-1=a+b(a≧b≧1)がp(n-3(m-1)-1,2)通り。」
などは
「●n=a+b+m(a≧b≧m)すなわちn-3(m-1)-1=(a-(m-1))+(b-(m-1))(a-(m-1)≧b-(m-1)≧1)。そこで(a-(m-1))と(b-(m-1)を改めてa,bと書くと、n-3(m-1)-1=a+b(a≧b≧1)がp(n-3(m-1)-1,2)通り。」
とでもやった方が親切だったかも。

お礼

返事が遅れ申し訳ありません。勝手ながらまとめて
お礼をさせて頂きます。
0shieteさん、kiriburiさん、stomachmanさん御回答有り難う御座います。
皆さん、ストレートな方法であり、差分方程式を使った証明を私は存じていませんが、多分同じ方針を理論的に発展させたもののような気がします。
が、無い物ねだりと存じますが全く新しい発想による回答が欲しいと思っていました。組合せ理論の問題は、数学の他の分野（代数学や幾何学など)と密接に絡んでくることが多いので、それらのつながりのある回答はないものでしょうかね。

回答No.3

stomachman

まず、p(n,2)はどうなっている？
n=a+b (a≧b≧1)
と分けるんです。すると、
p(n,2)={n/2}
は自明だ。

じゃあ、p(n,3)はどうか。
n=a+b+c, a≧b≧c
と分ける。
●n=a+b+1(a≧b≧1)すなわちn-1=a+b(a≧b≧1)がp(n-1,2)通り。
●n=a+b+2(a≧b≧2)すなわちn-4=a+b(a≧b≧1)がp(n-4,2)通り。
●n=a+b+3(a≧b≧3)すなわちn-7=a+b(a≧b≧1)がp(n-7,2)通り。
　 :
●n=a+b+m(a≧b≧m)すなわちn-3(m-1)-1=a+b(a≧b≧1)がp(n-3(m-1)-1,2)通り。
と、これだけある。ここでm={n/3}である。
つまり、
p(n,3)=Σp(n-3(k-1)-1,2) (k=1,2,....,{n/3})
p(n,3)=Σp(n-3k+2,2) (k=1,2,....,{n/3})
=Σ{(n-3k+2)/2} (k=1,2,....,{n/3})
これを計算すりゃいいのだね。

(1) n=6rのときには
p(n,3)=Σ{(6r-3k+2)/2} (k=1,2,....,2r)
=2r(3r+1)+Σ{-3k/2} (k=1,2,....,2r)
=2r(3r+1)+Σ({-3(2k-1)/2}+{-6k/2}) (k=1,2,....,r)
=2r(3r+1)+r-6Σk (k=1,2,....,r)
=2r(3r+1)+r-3r(r+1)
=3r^2
=3(n/6)^2
=(n^2/12)

(2) n=6r+1のときにはえーと、
とやっていけばできそうです。

回答No.2

kiriburi

ｎが3の倍数か否か、偶数か奇数かによって、4つの場合分けをする。

ｎが3の倍数でなく、奇数のとき
ｎを3分割し並べると(n-1)C2通り……(1)
(1)のうち、同じ数が重複する（たとえば2,2,7の様に）ものは3(n-1)/2通り……(2)
同じ数が重複する組み合わせは(n-1)/2種類……(3)

p(n,3)=((1)+(2))/6+(3)
=(n^2-1)/12

偶数のときは(2)=3(n-2)/2，(3)=(n-2)/2として
p(n,3)=(n^2-4)/12

3の倍数で奇数のときは………
というようにすれば、できそうです。
エレガントじゃないけど。

回答No.1

0shiete

一度に３つにわけることを考えると難しいので、まず、kだけひいておき、n-kを２つにわける問題にすれば数え上げれるのではないでしょうか？

ただし、２つに分けるときは、２つともk以上の数字になるように切り分けます。こうすることによってkを1から増やしていったときに、同じ切り分け方が出てこないようになります。

（実際、やってみたら難しいかもしれません）