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

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

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。
自然数 n の分割の個数 p(n) を計算するのは大変そう、
というあたりで前回の話を終わりました。
今回は、p(n) の実際的な計算についてちょっと触れてみます。

いまや、かなり高性能のコンピュータを個人で自由に使える時代です。
大変そうな計算はコンピュータにお願いする、
ということを考えてみます。
そのために、p(n) をどうやってコンピュータに計算させるか、
もう少しきちんと言えば、
どういったアルゴリズムで p(n) が計算できるのか、
ちょっと考えてみますね。
そのための例として、6 の分割を具体的に全部書き出してみると:

6
5+1
4+2
4+1+1
3+3
3+2+1
3+1+1+1
2+2+2
2+2+1+1
2+1+1+1+1
1+1+1+1+1+1

6 の分割は以上の 11 個です(つまり p(6)=11 ということ)。
これ、私はいったいどういう風に考えて書き出したのでしょうか。
分割は
「足し算の順番を入れ替えたものも、同じ分割だと思っちゃう」
という約束をしていたので、たとえば
 2+2+1+1, 2+1+2+1, 2+1+1+2,
 1+2+2+1, 1+2+1+2, 1+1+2+2
はすべて同じ分割だとみなすわけだったんだね。
それでは、この6つの書き表し方のうち、どれを代表に選ぶか。
どちらでもいいけれど、たとえば、大きい順番に並んだ
 2+2+1+1
を選ぶことにします。
このように、分割を書くときはいつでも、
登場人物たちは大きい順番に並んでいるとしておくわけ。
そうすると、
「一番大きい人は誰か?」つまり「一番左の数は何か?」
に着目することで、上に書いたようなリストに並べるのが自然です。

で、たとえば「一番左が 4 であるような 6 の分割」を見てみます。
それは 4+2, 4+1+1 の2つです。
この「2つ」はどこからやってきたかというと、
4 を取り除いて出来る太字の部分が、ちょうど 2 の分割になっていることから
p(2)=2 に由来してやってきている、と思うことが出来るわけ。

同じ観察が「一番左が 3 であるような 6 の分割」でも出来ます。
それは 3+3, 3+2+1, 3+1+1+1 の3つですが、
この「3つ」はさっきと同じようにして、
3 を取り除いて出来る太字の部分が、ちょうど 3 の分割になっていることから
p(3)=3 に由来してやってきている、と思うことが出来るんだね。

ははあ。

だんだん分かってきたところで、次に
「一番左が 2 であるような 6 の分割」を観察します。
それは 2+2+2, 2+2+1+1, 2+1+1+1+1 の3つです。
え?3つ?
2 を取り除いて出来る太字の部分が、今度は 4 の分割になっているんだけれど、
2+4 や 2+3+1 は登場しないんだね。
だって、先頭の 2 よりも右に、2 より大きい数が登場しちゃうから、
「大きい順番に並んでいること!」
という約束を守っていないことになるからだ。
というわけで、今度の「3つ」は
「2 以下の数だけを使った 4 の分割が3つある」
に由来するわけ。
さっきの2つの観察は、だから正確には
「4 以下の数だけを使った 2 の分割が2つある」
「3 以下の数だけを使った 3 の分割が3つある」
ということに由来しているわけだ。
でも、たとえば 2 の分割に 4 より大きい数が登場するわけはないので、
「4 以下の数だけを使った」という条件は、
あってもなくても同じことなんだね。

かくして、p(n) を計算するためのアルゴリズムが分かった。

つまり、単に p(n) だけを考えるのではなくて、補助的に
「k 以下の数だけを使った n の分割」
の個数をたとえば p(n, k) とか書くことにしておけば、
k≧n ならば p(n, k)=p(n) で、

p(n, k)=p(n?1, 1)+p(n?2, 2)+…+p(n?k, k)

という関係式(漸化式)が成り立っていることを利用すれば良い。

上の 6 の分割の例だと、
 p(6)=p(6, 6)=p(5, 1)+p(4, 2)+p(3, 3)+p(2, 4)+p(1, 5)+p(0, 6)
だけれども、
 p(3, 3)=p(3)=3,
 p(2, 4)=p(2)=2,
 p(1, 5)=p(1)=1,
 p(0, 6)=p(0)=1
となっています。
(言い忘れていたけれど「0 の書き表し方は1通りだ」
 と数えるとつじつまが合うので p(0)=1 と約束しておきます)
残りについては漸化式から
 p(5, 1)=p(4, 1),
 p(4, 2)=p(3, 1)+p(3, 2)
であり、 さらに漸化式から
 p(4, 1)=p(3, 1),
 p(3, 1)=p(2, 1),
 p(3, 2)=p(2, 1)+p(1, 2)
であって、p(1, 2)=p(1)=1 だ。
もう一度だけ漸化式を使って
 p(2, 1)=p(1, 1)=p(1)=1
なので、ずーっとさかのぼって代入していくことによって
 p(5, 1)=p(4, 1)=p(3, 1)=p(2, 1)=p(1, 1)=1,
 p(4, 2)=p(3, 1)+p(2, 1)+p(1, 2)=1+1+1=3
となる。これを最初の漸化式に代入して
 p(6)=1+3+3+2+1+1=11
のように計算できることになるわけ。

ややこしいね。
でも、大事なことは、漸化式だけを使って p(n) が計算できる仕組みが得られた、
ということ。
具体的な計算は、プログラムでも組んでおいて、
コンピュータに任せれば良いのです。
スポンサーサイト
テーマ:数学 - ジャンル:学問・文化・芸術
コメント
コメントする
URL:
Comment:
Pass:
秘密: 管理者にだけ表示を許可する
 
この記事のトラックバックURL
http://kinginsunago.blog63.fc2.com/tb.php/2-6006aa5b
この記事にトラックバックする(FC2ブログユーザー)
トラックバック
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。