分割数の公式の歴史

分割数

突然ですが、次のような問題を考えてみましょう。


n 個のボールを r 個の箱に入れるとき、入れ方は何通りあるか。

非常にシンプルな問題です。何が難しいのかと思った人もいるでしょう。
しかし！
設定を変えることで、様々に異なった問題ができます。


ボールが互いに区別できるかどうか。
箱が互いに区別できるかどうか。
箱の入れ方には制限がないか、各箱には最低でも1個はボールを入れるのか、各箱には高々1個しかボールを入れられないのか。


このように考えると、2 \times 2 \times 3 = 12 通りもの問題が出来上がります。

ボール 箱 制限なし 最低1個 高々1個
異 異 　 　 　
異 同 　 　 　
同 異 　 　 　
同 同 　 　 　


この表の空欄を埋めてみたいと思います。
えいやっ！

ボール 箱 制限なし 最低1個
n < r なら 0		 高々1個
n > r なら 0
異 異 r^n \sum_{i=1}^r(-1)^{r-i} \cdot {}_{r}\mathrm{C}_{i} \cdot i^n {}_{r}\mathrm{P}_{n}
異 同 \sum_{i=1}^r \frac{1}{i!} \sum_{j=1}^i(-1)^{i-j} \cdot {}_{i}\mathrm{C}_{j} \cdot j^n \frac{1}{r!} \sum_{i=1}^r(-1)^{r-i} \cdot {}_{r}\mathrm{C}_{i} \cdot i^n 1
同 異 {}_{n+r-1}\mathrm{C}_{n} {}_{n-1}\mathrm{C}_{r-1} {}_{r}\mathrm{C}_{n}
同 同 　 　 1


なかなか壮観ですねっ！
これは割と有名な話で、写像12相と呼ばれています。
制限がないのが写像の総数、最低1個は入れるのが全射の総数、高々1個しか入れられないのが単射の総数に相当します。
また、ここにある公式の全ては、高校レベルの数学の知識があれば導くことができます。
詳細はこちらをどうぞ。


ところで。
表の中には、まだ空欄がありますね。何故かしら。


実は、この空欄に入れるべき公式がどんな形をしているのかは、未解決問題だったのです！


特にボールと箱がそれぞれ互いに区別できず、入れ方に制限がない場合は分割数と呼ばれ、注目を集めてきました。
これは例えば、次のように言い換えることができます。


自然数 n をそれ以下のいくつかの自然数の和として表す場合の数
（ここでは自然数は 1 以上の整数を指すものとする）

例えば、
1 = 1
2 = 1+1, 2
3 = 1+1+1, 1+2, 3
4 = 1+1+1+1, 1+1+2, 1+3, 2+2, 4
5 = 1+1+1+1+1, 1+1+1+2, 1+1+3, 1+2+2, 1+4, 2+3, 5
となっているので、1〜5 までの分割数はそれぞれ
1, 2, 3, 5, 7
となります。


分割数は小学生にでも理解できるくらいに簡単な概念であるにも関わらず、簡単な公式は長らく発見されていませんでした。


まず、1918年、G. H. Hardy と Ramanujan が次のような漸近公式を発見しました。
p(n) \sim \frac{1}{4n\sqrt{3}}e^{\pi \sqrt{\frac{2n}{3}}}


うへー。
根号とか、自然対数の底 e とか、円周率 \pi が出てきちゃってるよ！
とりえあえず解説をすると、これは、n を無限大に近づけていったとき、n の分割数 p(n) が右辺の式の値に限りなく近づく、という意味です。
p(n) は自然数なので、その十分な近似値が与えられれば、正確な値を求めることは容易です。
例えば p(n) が 10.2 に近いということが分かれば、じゃあ p(n) は 10 だろう、と推測できます。
ただ、あくまでも近似値を求める公式なのであって、そのものずばりを求められるわけではないので、ちょっと微妙ですね。
おまけに、この式は収束率がとても悪く、p(1000) でさえ 1.415% もの誤差があるようです。


1937年、Hans Rademacher が、ついに完璧な公式（漸近公式でないという意味）を発見しました！
p(n) = \frac{1}{\pi\sqrt{2}}\sum_{k=1}^{\infty}\sqrt{k}A_k(n)\frac{d}{dn}\left(\frac{1}{\sqrt{n-\frac{1}{24}}}\sinh\left(\frac{\pi}{k}\sqrt{\frac{2}{3}\left(n-\frac{1}{24}\right)}\right)\right)


さらに、うへー！な感じですねっ。
一応解説します。
A_k(n) は自然数 n についてのとある関数なのですが、ここでは割愛します。
\frac{d}{dn} は、n についての微分ですね。
\sinh はハイパボリックサインといって、サインの友達のような感じです。
いい加減な解説ですが、何はともあれ、この公式は左辺と右辺がイコールで結ばれていますので、そういう意味では完璧です。
やったね！
しかしながら。
式をよーく見てみると、\infty の文字がありますね。
そうです。これは右辺のシグマの中を無限回計算して足し合わせないと、正確な値が出ないのです。
そして、そんなことが不可能なのは陽の目を見るより明らかですね。
あれまー。
そういった意味では、これは前述の漸近公式と大差ないと言えるかもしれません。


というわけで、上記二つの公式は、色々な面で問題を含んでいたわけです。
できることならば、有限個の何らかの数の和として p(n) を正確に表したいところですね。


時は下って現代。
日経サイエンス2011年6月号に、次のような記事が載っていました。

オノと別の共同研究者は（中略）任意の数 n に対して分割数 p(n) を計算する公式を初めて導き出した。
これは数論研究者が何世紀もの間なしえなかった偉業だ。


オノさんは日本人！日本人が貢献してる！すごい！
きゃー！！


とは言え。
この記事には突っ込みどころがあります。
まず、任意の数 n っていうのは、任意の自然数という意味だと分かりますが、数といったら色んな種類があるので、あまり良い表現とは言えません。
そして、それよりも何よりも、「公式を初めて導き出した」というのは非常に語弊があります。
先述の通り、G. H. Hardy と Ramanujan と Hans Rademacher が、既に公式を導いています。
あれあれー。おかしいなー。どういうことかなー。
インターネットで調べたところ、オノさんの論文のアブストラクトが見つかりました。
http://www.aimath.org/news/partition/brunier-ono.pdf
これによると、p(n) を
「有限個の代数的数で表した」
とあります。
おー。何とっ！
有限個、というところがポイントですね。ここが正に、先人達がなしえなかった偉業なわけです。
（…日経サイエンスさん、そこのところをちゃんと書いてくれないと。）
さらに付け加えるならば、代数的数、というのもポイントですね。
代数的数というのは、整数係数の方程式の解となりうる実数のことですから、その正体がはっきりしています。
つまり、正体がはっきりしている数の有限個の和として p(n) を表しちゃったってことで、これはもう、二重にすごいことなのであります！


いやー、良かった良かった！


…さて、分割数の公式を求める旅は、これで終了なのでしょうか。
もう誰も、研究しようとはしないのでしょうか。
いえ、まだ課題が残っています。


この記事の冒頭で紹介した表の中の公式は、どれも有限個の有理数の和として表されています。
できることならば、分割数の公式も、何らかの理論の元にそのようにしたいところです。
それができて、ようやく、本当の解決と言えるのではないでしょうか。
もしかしたら、やたらめったら長くて複雑な式ではなく、表中の他のものと同程度の複雑さを持った簡明なものが存在するかもしれません。


分割数の公式を求める旅は、まだ始まったばかりだと言えそうです。


ちなみに、分割数を有限個の有理数を使って表す公式は、既に存在します。
私が作りました。てへっ。
昨日に公開した、これです。
背景には理論も何もないので、全く何の役にも立たない代物ですが。
式の導出方法については以前にも少し書いたのですが、そのうちに、ちゃんと書きたいと思います。


続く。