わりと好きかもしれません。

お気に入りの数学の話題について、ぽつりぽつりと書きつづっていければと思います。

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。
もう1回だけ分割の話をします。

前回は「k 以下の数だけを使った n の分割の個数」を考えると、
それらの間には簡単な関係式が成り立つことを観察しました。
そのおかげで、分割の個数の計算が
計算機に乗っけることができるアルゴリズムに帰着されたのだったね。

今回は、p(n) そのものがみたす関係式を
証明は抜きで紹介だけしようと思うのです。
一つめは、ここで証明を書くのはちょいと難しいというか大変だけれども、
ほんの少しの予備知識を準備すればなんとかなるもので、
それは次のようなものです。

 p(n)=(σ(1)p(n?1)+σ(2)p(n?2)+…+σ(n)p(0)) / n

ただし、σ(n) は n の約数の和を表します。
つまり、たとえば 12 の約数は 1, 2, 3, 4, 6, 12 なので
 σ(12)=1+2+3+4+6+12=28
といった具合。
それにしてもいったいどうして、
分割の個数の間の関係式に「約数の和」なんてものが
するりと潜り込んでくるのでしょう。不思議ですね。

せっかくなので、この式をちょっと試してみましょう。
n=6 とすると

 p(6)=(σ(1)p(5)+σ(2)p(4)+σ(3)p(3)+σ(4)p(2)+σ(5)p(1)+σ(6)p(0)) / 6

です。σ(n) の値を計算しておくと、
 σ(1)=1
 σ(2)=1+2=3
 σ(3)=1+3=4
 σ(4)=1+2+4=7
 σ(5)=1+5=6
 σ(6)=1+2+3+6=12
となります。
前々回に計算した p(1) から p(5) の値を思い出しておくと
 p(0)=1, p(1)=1, p(2)=2, p(3)=3, p(4)=5, p(5)=7
でした。というわけで、上の関係式の右辺に代入すると

 p(6)=(1×7+3×5+4×3+7×2+6×1+12×1) / 6
   =(7+15+12+14+6+12) / 6
   =66 / 6
   =11

となりました。確かに成り立っているようですよ?

もう一つは、本当に p(n) だけの間の関係式です。
こちらの漸化式を発見・証明したのはオイラーです。
(こっちの方がメジャーかな?)

 p(n)?p(n?1)?p(n?2)+p(n?5)+p(n?7)?p(n?12)?p(n?15)+…=0
(ただし、n が負の数のときは p(n)=0 と約束しておく)

ん???
これはいったい、どういう規則性で足したり引いたりしているのでしょう?
ともかく、この式が成り立っているかどうかを
n が小さいときに試してみると…

 p(1)?p(0)=1?1=0
 p(2)?p(1)?p(0)=2?1?1=0
 p(3)?p(2)?p(1)=3?2?1=0
 p(4)?p(3)?p(2)=5?3?2=0
 p(5)?p(4)?p(3)+p(0)=7?5?3+1=0
 p(6)?p(5)?p(4)+p(1)=11?7?5+1=0

うんうん、正しいみたいです。
さらに、これを使って p(7) を計算してみますね。
漸化式より

 p(7)?p(6)?p(5)+p(2)+p(0)=0

なので、

 p(7)=p(6)+p(5)?p(2)?p(0)=11+7?2?1=15

となります。

さて、漸化式はいったいどういう規則性で決まっているんでしょうか?

世の中は便利になってきていて、こういうとき、
既にあるウェブ上の資産にリンクをぽちっと張るだけで
済ませられるのがいいよね。
スポンサーサイト
テーマ:数学 - ジャンル:学問・文化・芸術
コメント
コメントする
URL:
Comment:
Pass:
秘密: 管理者にだけ表示を許可する
 
この記事のトラックバックURL
http://kinginsunago.blog63.fc2.com/tb.php/3-c1ed0fe4
この記事にトラックバックする(FC2ブログユーザー)
トラックバック
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。