分割数

先日読んだ『数学ガール　ゲーデルの不完全性定理』が面白かったので、結城浩さんの他の「数学ガール」シリーズを読み始めました。

「数学ガール」シリーズは、2011年6月現在、4冊出版されているようです。

1. 『数学ガール』（2007年）
2. 『数学ガール　フェルマーの最終定理』（2008年）
3. 『数学ガール　ゲーデルの不完全性定理』（2009年）
4. 『数学ガール　乱択アルゴリズム』（2011年）

今回読み始めたのは、第1作目の『数学ガール』

そこで、面白そうな問題が出ていたので考えてみたいと思います。

額面が、1円、2円、3円、4円、……になっているコインがあるとする。合計n円を支払うためのコインの組み合わせが何通りあるのかを考えよう。この組み合わせの個数をPnとする（各支払い方法をnの分割と呼び、分割の個数すなわちPnを、nの分割数と呼ぶ）。

たとえば、3円を支払う方法には「3円玉が1枚」「2円玉が1枚と1円玉が1枚」「1円玉が3枚」という3通りがあるため、P3=3である。

問題10-1
P9を求めよ。

問題10-2
P15＜1000は成り立つか。

実際の解法（考え方）は、このブログで数式が表現できない（できるとは思いますが、めんどくさそう…）ため、実際に本でお読みください。特に問題10-2については、私にはまだ上手く説明する力量がありませんし…。



この問題に興味を持った理由は、以前に森博嗣さんの『笑わない数学者』で出てきた問題を考えているときに、自然数を素数の積で表わす方法がある（素因数分解の一意性）のに、自然数を和で表わす方法はないのかな、と考えたときがあるからです。（以前のブログ「素数について」参照）

もちろん一意には決まりませんが…

そこで、何通りあるのか、ということを考えていて、途中放棄していました。


では、問題に戻って。

まずは、具体的に確認していきましょう。

n=0のとき、つまり、支払う金額が0円の場合は、「支払わない」という方法が一つだけあります。したがって、

P0=1

です。

次にn=1のとき、つまり支払う金額が1円の場合は、「1円玉を1枚使う」という方法のみ。これも一つのみです。

P1=1

n=2のとき、つまり支払う金額が2円のときは、「1円玉を2枚使う」「2円玉を1枚使う」の2通り。

P2=2

ここで、書き方を整理します。

n=3のときの分割数を以下のように表わします。

3=3
3=2+1
3=1+1+1

一番上の「3=3」は、「3円の支払いを3円玉1枚を使って支払った」という意味です。「3=2+1」は、「3円の支払いを2円玉1枚と1円玉1枚で支払った」という意味。3通りあるので、

P3=3

です。

同様にn=4の場合は、

4=4
4=3+1
4=2+2
4=2+1+1
4=1+1+1+1

の5通りなので、

P4=5

『数学ガール』の主人公「僕」は、このように具体例を挙げていき、Pnの一般項を求めようとしていきます。

分割数の一般項Pnを表わす式も『数学ガール』のエピローグに載っていましたが、「とんでもない式」です。

Wikipediaにも分割数についての記述がありましたが、私には意味不明…（Wikipedia「整数分割」）

とりあえずn=5のときも書いておくと、

5=5
5=4+1
5=3+2
5=3+1+1
5=2+2+1
5=2+1+1+1
5=1+1+1+1+1

の7通りなので、

P5=7

さて、問題10-1のP9の値ですが、これは30通りあります。つまりP9=30です。


今まで、分割数についての説明をしてきましたが、（一般項も複雑ですし、）ちょっと簡単に考えてみたいと思います。

分割数は基本的に順番は問いませんでした。並べる順序のみが違うものは同じ分割と見なされています。つまり、「5=3+2」と「5=2+3」は同じ分割です。

この条件を外すとどうなるでしょうか？

同じ「分割」と呼ぶと混乱しますので、ここでは「分断」と書きます（「分断」は私が勝手につけた用語です）。そして、分断の個数を「分断数」としましょう。この組み合わせの個数をQnとすると、分断の個数すなわちQnを、nの分断数と呼びます。

すると、

n=0のときは、Q0=1
n=1のときは、Q1=1
n=2のときは、Q2=2
n=3のときは、Q3=4
n=4のときは、Q4=8
n=5のときは、Q5=16

となります。

n=5を例にとると、

5=5
5=4+1
5=3+2
5=2+3
5=1+4
5=3+1+1
5=2+2+1
5=2+1+2
5=1+3+1
5=1+2+2
5=1+1+3
5=2+1+1+1
5=1+2+1+1
5=1+1+2+1
5=1+1+1+2
5=1+1+1+1+1

の16通り、つまり、

Q5=16

です。

これならば、ひょっとすると一般項が求められるかもしれません。まだ、試していませんが…。