分割数
数論における分割数(ぶんかつすう、partition function) p(n) は自然数 n の分割(n をその順番の違いを除いて自然数の和として表す方法)の総数を表す数論的函数である。ただし、規約として p(0) = 1 および負の整数に対して p(n) = 0 と定める。
分割数の値について、いくつかは A000041 を参照。
p(1) = 1
p(2) = 2
p(3) = 3
p(4) = 5
p(5) = 7
p(6) = 11
p(7) = 15
p(8) = 22
p(9) = 30
p(10) = 42
p(100) = 190,569,292
p(200) = 3,972,999,029,388
p(1000) = 24,061,467,864,032,622,473,692,149,727,991 ≈ 2.431.
2011、知られている中でこの形で得られる最大の素数は、Bernardo Boncompagni が発見した p(40100918) で、これは十進で 7047 桁の数値である。
分割函数をより扱いやすくする方法のひとつは、補助的な函数 p(k, n) を考えることである。これは少なくとも k 以上の自然数を用いて n を分割する方法の数を数えたもので、各 k に対して分割数を数えれば、次のいずれかの場合を見ればいいことになる。
最小の成分がちょうど k である。
最小の成分が k より真に大きい。
前者に当たる分割の総数は p(k, n − k) である。これをみるには、整数 n − k を少なくとも k よりもサイズの大きい整数への分割を全て一覧したものを考えて、その一覧の各分割に "+ k" することを考えればよい。
このことは、補助的な函数を使って分割数のある種の漸化式を定義することに利用できる。つまり
1+\sum_{k=1}^{\lfloor \frac{1}{2}n \rfloor} p(k,n-k) = p(n),
が成立する。ここで、\lfloor n\rfloor は床函数である。
後者に当たる分割の総数は p(k +1, n) である。これは各成分が k 以上の分割から、ちょうど k になる成分を含むようなものを除いた結果は、すべての成分が k + 1 以上になっていなければならないことからわかる。
さて、上記の二条件は互いに排他的であるから、n の分割の総数というのは、それぞれの場合をあわせた p(k + 1, n) + p(k, n − k) となっていることがわかる。したがって、再帰的に、補助的な函数を
k > n のとき: p(k, n) = 0
k = n のとき: p(k, n) = 1
それ以外: p(k, n) = p(k+1, n) + p(k, n − k)
と定める。この函数は少し複雑な挙動を見せる傾向にある。
p(1, 4) = 5
p(2, 8) = 7
p(3, 12) = 9
p(4, 16) = 11
p(5, 20) = 13
p(6, 24) = 16
もともとの分割数 p(n) はちょうど p(1, n) にあたる。
いくつかの値については以下のとおり。
分割数 p(n) の母函数は、次の式で与えられる。
\sum_{n=0}^\infty p(n)x^n = \prod_{k=1}^\infty \left(\frac {1}{1-x^k} \right).
右辺の各項を幾何級数として展開すれば、これは
(1 + x + x2 + x3 + ...)(1 + x2 + x4 + x6 + ...)(1 + x3 + x6 + x9 + ...) ....
と書くことができるが、ここから積をとって xn の項となるものを拾い出せば
n = a1 + 2a2 + 3a3 + ... = (1 + 1 + ... + 1) + (2 + 2 + ... + 2) + (3 + 3 + ... + 3) + ...,
を得る。ここで各数 i は ai 個ずつ現れる。これはまさに n の分割の定義そのものであるから、この無限積が求める母函数を与えることが確認できる。もっと一般に、整数 n の適当な集合 A に属する整数への分割数の母函数も、上記の式の項の k を A の元となっているものにとることで得られる。この結果はオイラーによる。
オイラーによるこのような分割数の母函数の定式化は q-ポッホハマー記号の特別な場合であり、また多くのモジュラー形式の積の定式化(特にデテキント・イータ函数の)と近い関係にある。また、この母函数表示をオイラーの五角数定理と合わせれば、次のような漸化式
p(k) = p(k − 1) + p(k − 2) − p(k − 5) − p(k − 7) + p(k − 12) + p(k − 15) − p(k − 22) − ...
を得る。ここで p(0) = 1 および負の整数 k に対して p(k) = 0 とし、和は ½n(3n − 1) の形(ただし n は正または負の整数全体を走る)の一般五角数全体にわたってとるものとする(順に n = 1, −1, 2, −2, 3, −3, 4, −4 ..., とすると、値として 1, 2, 5, 7, 12, 15, 22, 26, 35, 40, 51, ... が得られる)。和における符号は交互に +, +, −, −, +, +, ... と続く。
ラマヌジャンは 4 または 9 で終わる整数に対する分割数に関して合同式
p(5k+4)\equiv 0 \pmod 5
が成立することを発見した。例えば、整数 4 の分割数は 5 であり、整数 9 の分割数は 30、整数 14 の分割数は 135 といった具合である。ラマヌジャンはまた 7 および 11 に関する合同式
\begin{align}
p(7k + 5) &\equiv 0 \pmod 7\\
p(11k+ 6) &\equiv 0 \pmod{11}
\end{align}
も発見している。さて、5, 7, 11 は連続する素数になっているので、次の素数 13 に対する同様の合同式 p(13k + a) ≡ 0 (mod 13) が適当な a のもと成立しそうなものだが、実際にはそうはなっていない。さらにいえば、p(bk + a) ≡ 0 (mod b) の形の合同式は 5, 7, 11 以外のどの素数 b に対しても成立しないことが示せる。
1960年代にイリノイ大学シカゴ校のアトキンは、同様のいくつかの小さな素数を法とする合同式を発見している。例えば
p(11^3 \cdot 13 \cdot k + 237)\equiv 0 \pmod {13}
のようなものが含まれる。2000年には、ウィスコンシン大学マディソン校の小野(Ken Ono)は任意の素数を法とする同様の合同式の存在を示した。さらに数年後、小野はイリノイ大学のスコット・アールグレンとともに、6 と互いに素なすべての整数を法とする分割数の合同式が存在することを証明している。
A.ブライチャー:「ラマヌジャンの予言」、日経サイエンス、2014年9月号、頁67-72.
Amanda Folsom, Zachary A. Kent and Ken Ono:"l-Adic Properties of the Partition Function", Advances in Mathematics, v.229, No.3, pp.1586-1609 (Feb. 15, 2012).
Ken Ono and Larry Rolen:"Ramanujan's Mock Theta Functions", Proc. National Academy of Sci. USA, v.110, No.15, pp.5765-5768(Apr. 9, 2013). url="www.ncbi.nlm.nih.gov/pmc/articles/PMC3625272".
分割数 p(n) の漸近表示は、
p(n) \sim \frac{1}{4n\sqrt{3} e^{\pi \sqrt{\frac{2n}{3}} \mbox { as } n\to \infty.
で与えられる。この漸近公式は、ハーディとラマヌジャンによって1918年に初めて見出され、また、それとは独立にウスペンスキーが1920年に発見している。例えば p(1000) を考えると、漸近公式からだいたい 2.4402 × 1031 となることがわかるが、これは真の値とくらべても十分近い値である(真の値よりは 1.415% ほど大きい)。
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) = \sum_{0\le m< k\atop (m,k)=1}e^{\pi i\left[s(m,k)-\frac{1}{k} 2nm \right]}
とおいた。この式の微分の箇所はもう少し簡単な形に直せる。ここで、記号 (m, n) = 1 は m の値として n と互いに素であるものだけを考えることを意味する。また函数 s(m, k) はデデキント和である。ラーデマッハーの公式の証明はフォード円、ファレイ数列、モジュラー対称性およびデデキント・イータ函数などを主に使ってなされる。
2011年1月、小野とダルムシュタット工科大学のジャン・ヘンドリック・ブルーニエは、任意の自然数 n に対する p(n) を決定する有限で代数的な公式を得たと発表した。
分割数は n の「五角数分割」上の和として表すことができる。
n = k_1 + 2k_2 + 5k_5 + \cdots = \sum_m q_m k_{q_m}
を n の五角数分割とする。ここに各 qm = m(3m − 1)/2 は一般五角数(GPN, 数列 A001318)で qM は n を超えない最大の GPN である。故に
p(n)  =   \sum_{k_1 =0}^{n}  \sum_{k_2 =0}^{\lfloor n/2 \rfloor } \sum_{k_5 =0}^{\lfloor n/5 \rfloor }
\cdots \sum_{k_{q_{M} =0}^{\lfloor n/q_M \rfloor }  (-1)^A
\left( \begin{array}{c} K \\ k_1, k_2, k_5,  \ldots ,k_{q_M} \end{array} \right)
\delta_{n,  \sum q_m k_{q_{m}},
を得る。ここで
\begin{align}
K & = k_1 + k_2 + k_5 + k_7 + \cdots, \\
A & = k_5 + k_7 + k_{22} +k_{26} + \cdots
=\sum_{m= \pm 2, \pm 4, \ldots} k_{q_{m},
\end{align}
\left( \begin{array}{c} K \\ k_1, \ldots , k_n \end{array} \right)
\equiv \frac{ K!}{k_1! \cdots k_n!} ~ \delta_{K,k_1+ \cdots + k_n}
は多項係数である。p(n) に対する和の項の数は数列 A095699 で与えられる。例えば 8 = 7+1 = 5+2+1 = 5+1+1+1 = 2+2+2+2 = ... だから
\begin{align} p(8) &= -  \left( \begin{array}{c} 2 \\ 1,0,0,1 \end{array} \right) -  \left( \begin{array}{c} 3 \\ 1,1,1,0 \end{array} \right)
-  \left( \begin{array}{c} 4 \\ 3,0,1,0 \end{array} \right) + \left( \begin{array}{c} 4 \\ 0,4,0,0 \end{array} \right)  \\ & ~~~
+ \left( \begin{array}{c} 5 \\ 2,3,0,0 \end{array} \right)  +
\left( \begin{array}{c} 6 \\ 4,2,0,0 \end{array} \right)
+  \left( \begin{array}{c} 7 \\ 6,1,0,0 \end{array} \right) +
\left( \begin{array}{c} 8 \\ 8,0,0,0 \end{array} \right) \\
&= -2 - 6 - 4 + 1 + 10 + 15 + 7 + 1 = 22\end{align}
となる。
各自然数 n に対して p(n) は次の式で求められる。
\begin{matrix} {\rm GPN's} \\0\\1\\2\\~\\~\\5\\~\\7\\~\\~\\ \vdots\\~\\~ \end{matrix} ~~~
p(n) = \begin{vmatrix}
~~1 & -1~&   ~& ~  & ~ &~&~&~ \\
~~1 & ~1 & -1~& ~ \\
~~0 & ~1 & ~1 & -1~& ~ \\
~~0 & ~0 & ~1 & ~1 &-1~ & ~ \\
-1 & ~0 & ~0 & ~1 & ~1 &-1~ & ~  \\
~~0 & -1~& ~0 & ~0 & ~1 & ~1 & -1~& ~ \\
-1 & ~0 & -1~& ~0 & ~0 & ~1 & ~1 & -1~&~ \\
~~0 & -1~& ~0 & -1~& ~0 & ~0 & ~1 & ~1 & -1~&~ \\
~~0 & ~0 & -1~& ~0 & -1~& ~0 & ~0 & ~1 & ~1 & ~ \\
~~\vdots & ~  & ~  & ~  & ~  & ~  &  ~ & ~  & ~ & \ddots\\
\end{vmatrix} _{ n \times n} .
つまり、p(n) は上記無限次元テープリッツ行列を n × n で止めた正方行列の行列式である。この行列の零でない成分は、一般五角数 qm 番目の行の先頭から斜め (diagonal) に配置され(主対角線のひとつ上側の成分 (superdiagonel) は仮想的に 0 番目の行からと考える)、その値が (−1)m+1 となっている。この行列式公式は、次の行列の間の関係式
\begin{pmatrix}
~p(0) & ~ \\
~p(1) & p(0) &~ \\
~p(2) & p(1) & p(0) & ~ \\
~p(3) & p(2) & p(1) & p(0) & ~ \\
~p(4) & p(3) & p(2) & p(1) & p(0) & ~ \\
~p(5) & p(4) & p(3) & p(2) & p(1) & p(0) & ~ \\
~ \vdots & ~ & ~ & ~ & ~ & ~ &  \ddots
\end{pmatrix} = \begin{pmatrix}
~1 & ~ \\
-1 & ~1 &~ \\
-1 & -1 & ~1 & ~ \\
~0 & -1 & -1  & ~1 & ~ \\
~0 & ~0 & -1 & -1 &~1 & ~ \\
~1 &~0 & ~0 & -1 & -1 &~1 & ~ \\
~\vdots & ~ & ~ & ~ & ~ &  ~ &  \ddots
\end{pmatrix}^{-1}
に同値なのだが、この関係式自体は単に上述の母函数の間の関係式(と五角数定理)を行列の形にまとめたものである。
\sum_{k=0}^{\infty} p(5k+4)x^k = 5\,\frac{(x^5)^5_{\infty}{(x)^6_{\infty} ,\quad (x)_{\infty} \equiv \prod_{m=1}^{\infty}(1-x^m)
を使えば、分割数 p(5k − 1) はより小さな k-次行列の行列式
p(5k-1) = 5 \cdot\begin{vmatrix}
~1 & ~  & ~  & ~  & ~ & ~ & ~&~1~\\
-6 & ~1 & ~  & ~  & ~ & ~ & ~&~0~\\
~9 & -6 & ~1 & ~  & ~ & ~ & ~&~0~\\
~10& ~9 & -6 & ~1 & ~ & ~ & ~&~0~\\
-30& ~10& ~9 & -6 &~1 & ~ & ~&~0~\\
~0 & -30& ~10& ~9 & -6& ~1& ~&-5~\\
~11&  ~0& -30& ~10& ~9& -6& ~&~0~\\
~ \vdots& ~&~&~&~&~&~\ddots &  ~\vdots~ \end{vmatrix}_{k \times k}
として表すことができる。第一列の成分のなす数列は A000729 であり、最終列の(最初の 1 から)五つ毎に現れる非零成分のなす数列 (1, −5, 5, 10, −15, −6, …) は、数列 A000728 になっている(最終列はそれ以外の成分は全て零である)。例えば
p(29) = 5 \cdot\begin{vmatrix}
~1 & ~  & ~ & ~ & ~ & ~1~\\
-6 & ~1 & ~ & ~ & ~ & ~0~\\
~9 & -6 & ~1& ~ & ~ & ~0~\\
~10& ~9 & -6& ~1& ~ & ~0~\\
-30& ~10& ~9& -6& ~1& ~0~\\
0 & -30&~10& ~9& -6& -5~
\end{vmatrix}= 4565.
同様のやり方で、残り二つのラマヌジャンの公式を使えば、分割数 p(7k − 2) および p(25k − 1) も k-次の行列式
\begin{align}
p(7k-2) &= 7 \cdot\begin{vmatrix}
~1& ~  & ~ & ~& 1~\\
-8& ~1 & ~ & ~& 3~\\
~20& -8 & ~1& ~& 2~\\
~0 & ~20& -8& ~& 8~\\
~\vdots & ~& ~&\ddots &\vdots~
\end{vmatrix}_{k\times k},\\
p(25k-1) & = 25 \cdot\begin{vmatrix}
~1& ~ &~& ~& 63~\\
-31& ~1& ~ &~& 4988~\\
~434 & -31& ~1& ~ & 95751~\\
-3565 &~434 & -31& ~ & 766014~\\
~ \vdots & ~&~& \ddots & \vdots~
\end{vmatrix}_{k\times k}
\end{align}
と表すことができる。これらの行列の最初の列はそれぞれ A000731 および A010836 であり、最終列は次の展開
\begin{align}
(x)^4_{\infty} (x^7)^3_{\infty} +7x(x^7)^7_{\infty} &= 1 +3x+2x^2+8x^3 + \cdots ;\\& \\
63(x)^{24}_{\infty}(x^5)^{6}_{\infty} + 5^3 \cdot 52x(x)^{18}_{\infty}(x^5)^{12}_{\infty}
&+ 5^5 \cdot 63x^2(x)^{12}_{\infty}(x^5)^{18}_{\infty} \\
+~ 5^{8} \cdot 6x^3(x)^{6}_{\infty}(x^5)^{24}_{\infty} &+ 5^{10} \cdot x^4 (x^5)^{30}_{\infty} \\
& =  63+4988x +95751x^2 +766014x^3 + \cdots
\end{align}
から得られる。例えば p(149) は
p(149) = 25 \cdot \begin{vmatrix}
~1 & ~   & ~ &~&~& ~63~\\
-31 & ~1 & ~ &~&~& ~4988~\\
~434 & -31 & ~1 &~&~& ~95751~\\
-3565 & ~434 & -31&~1&~& ~766014~\\
~18445 & -3565 & ~434& -31&~1&  ~3323665~\\
-57505 &  ~18445 &-3565& ~434& -31 &~ 8359848~\\
\end{vmatrix}=  37027355200
で計算できる。また、分割数の第 n-部分和は行列式
\sum_{k=0}^n p(k) = \begin{vmatrix}
~2 & -1 & ~ \\
~0 & ~2 & -1 & ~ \\
-1 & ~0 & ~2 & -1 & ~\\
~0 & -1 & ~0 & ~2 & -1 & ~ \\
-1 & ~0 & -1 & ~0 & ~2 & -1 & ~ \\
~1 & -1 & ~0 & -1 & ~0 & ~2 & -1 & ~ \\
~\vdots &~&~&~&~&~& \ddots & \ddots & ~\\
c_{n-1} & c_{n-2} & ~& \cdots &~&~&~&~ 2 & -1 &~\\
c_n & c_{n-1} &~& \cdots &~& ~&~& ~0 &~2&~
\end{vmatrix}_{n \times n}
で与えられる。ただし、c0 = −1, c1 = 2, c2 = 0 かつ k > 2 に対しては
c_k = \begin{cases}
(-1)^{m+1}& \text{if } k = q_m ,\\
(-1)^m & \text{if } k=q_m+1, \\
0 & \text{otherwise.}
\end{cases}
とする。相異なる整数成分への分割の分割数を q(n) と書けば(これは分割の項に述べるように奇数成分への分割の分割数とも等しく)、
q(n) = \begin{vmatrix}
~1& ~ & ~ & ~ & ~ & ~ & ~ &~&~1~\\
-1& ~1& ~ & ~ & ~ & ~ & ~ &~&~0~\\
-1& -1& ~1& ~ & ~ & ~ & ~ &~&-1~\\
~0& -1& -1& ~1& ~ & ~ & ~ &~&~0~\\
~0& ~0& -1& -1& ~1& ~ & ~ &~&-1~\\
~1& ~0& ~0& -1& -1& ~1& ~ &~&~0~\\
~0& ~1& ~0& ~0& -1& -1& ~1&~&~0~\\
~1& ~0& ~1& ~0& ~0& -1& -1&~&~0~\\
~ \vdots &~&~&~&~&~& ~& \ddots & ~\vdots~
\end{vmatrix}_{(n+1) \times (n+1)}
が成り立つ。第一列は数列 A010815 で、最終列は 2qm + 1 行目の成分が (−1)m でそれ以外の成分は零である。