分割数

数論における分割数（ぶんかつすう、英: partition function）p(n) は自然数 n の分割（n をその順番の違いを除いて自然数の和として表す方法）の総数を表す数論的函数である。ただし、規約として p(0) = 1 および負の整数 n < 0 に対して p(n) = 0 と定める。

分割数のリスト

分割数の列について、50番目までの値は オンライン整数列大辞典の数列 A000041 を参照。

n	0	1	2	3	4	5	6	7	8	9	10
p(n)	1	1	2	3	5	7	11	15	22	30	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.4×10³¹.

2020年 (2020-Feb)現在、知られている中でこの形で得られる最大の素数は、p(1289844341) で、これは十進法で 40000桁の数値である。

補助函数

分割函数の値を帰納的に求める方法の一つとして、n を k 以上の自然数で分割する場合の数 p(k, n) を補助的な函数として考えるのがある。k を固定したとき、p(k, n) を次の2つで場合分けする。

1. 最小の成分が k である。
2. 最小の成分が k より大きい。

1. の場合の数は p(k, n − k) である。何故なら、整数 n − k を k 以上の整数で分割した場合全体は、それぞれの場合に "+k" とすると、n の、最小の成分が k の分割と1対1に対応するからである。

この補助函数により、分割数の列の一般項を立式できる：

$1+\textstyle \sum \limits _{k=1}^{\lfloor {\frac {1}{2}}n\rfloor }p(k,n-k)=p(n),$

ここで $\lfloor n\rfloor$ は床函数である。

2. の場合の数は p(k + 1, n) である。これは、最小の成分が k + 1 以上であることから明らかである。

上記の 2つの場合は排反であるから、n の分割の総数は

p(n) = p(k + 1, n) + p(k, n − k)

となる。したがって、補助函数 p(k, n) を再帰的に次の式で定義する：

$p(k,n):=\left\{{\begin{array}{ll}0&(k>n)\\1&(k=n)\\p(k+1,n)+p(k,n-k)&(k<n)\end{array}}\right.$

この函数は少し複雑な挙動を見せる傾向にある。

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(k, n) の一覧表は以下の通り。

p(k, n)		k
		1	2	3	4	5	6	7	8	9	10
n	1	1	0	0	0	0	0	0	0	0	0
	2	2	1	0	0	0	0	0	0	0	0
	3	3	1	1	0	0	0	0	0	0	0
	4	5	2	1	1	0	0	0	0	0	0
	5	7	2	1	1	1	0	0	0	0	0
	6	11	4	2	1	1	1	0	0	0	0
	7	15	4	2	1	1	1	1	0	0	0
	8	22	7	3	2	1	1	1	1	0	0
	9	30	8	4	2	1	1	1	1	1	0
	10	42	12	5	3	2	1	1	1	1	1

分割数の母函数

分割数 p(n) の母関数は、次の式で与えられる。

$\textstyle \sum \limits _{n=0}^{\infty }p(n)x^{n}=\prod \limits _{k=1}^{\infty }{\dfrac {1}{1-x^{k}}}.$

右辺の各項を幾何級数として展開すれば、これは

(1 + x + x² + x³ + …)(1 + x² + x⁴ + x⁶ + …)(1 + x³ + x⁶ + x⁹ + …) …,

と書くことができるが、ここから積をとって xⁿ の項となるものを拾い出せば

n = a₁ + 2a₂ + 3a₃ + … = (1 + 1 + … + 1) + (2 + 2 + … + 2) + (3 + 3 + … + 3) + …,

を得る。ここで各数 i は a_i 個ずつ現れる。これはまさに 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{aligned}p(7k+5)&\equiv 0{\pmod {7}}\\p(11k+6)&\equiv 0{\pmod {11}}\end{aligned}}$

も発見している。さて、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 × 10³¹ となることが分かるが、これは真の値とくらべても十分近い値である（真の値よりは 1.415% ほど大きい）。

1937年にラーデマッハーはハーディとラマヌジャンの結果に基づいて次の発散級数表示：

$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\leq 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 の五角数分割とする。ここに各 q_m = m(3m − 1)/2 は一般五角数（GPN, 数列 A001318）で q_M は 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{aligned}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{aligned}}$

および

$\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{aligned}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{aligned}}$

となる。

行列式公式

各自然数 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 で止めた正方行列の行列式である。この行列の零でない成分は、一般五角数 q_m 番目の行の先頭から斜め (diagonal) に配置され（主対角線の1つ上側の成分 (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})_{\infty }^{5}}{(x)_{\infty }^{6}}},\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{aligned}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{aligned}}$

と表すことができる。これらの行列の最初の列はそれぞれ A000731 および A010836 であり、最終列は次の展開

${\begin{aligned}(x)_{\infty }^{4}(x^{7})_{\infty }^{3}+7x(x^{7})_{\infty }^{7}&=1+3x+2x^{2}+8x^{3}+\cdots ;\\&\\63(x)_{\infty }^{24}(x^{5})_{\infty }^{6}+5^{3}\cdot 52x(x)_{\infty }^{18}(x^{5})_{\infty }^{12}&+5^{5}\cdot 63x^{2}(x)_{\infty }^{12}(x^{5})_{\infty }^{18}\\+~5^{8}\cdot 6x^{3}(x)_{\infty }^{6}(x^{5})_{\infty }^{24}&+5^{10}\cdot x^{4}(x^{5})_{\infty }^{30}\\&=63+4988x+95751x^{2}+766014x^{3}+\cdots \end{aligned}}$

から得られる。例えば 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}$

で与えられる。ただし、c₀ = −1, c₁ = 2, c₂ = 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 で、最終列は 2q_m + 1 行目の成分が (−1)^m でそれ以外の成分は零である。

関連項目

• 自然数の分割
• エバンスのサンプリング公式 (Ewens's sampling formula)
• ファア・ディ・ブルーノの公式 (Faà di Bruno's formula)
• spt函数 (Smallest-parts function)

参考文献

• George E. Andrews, The Theory of Partitions (1976), Cambridge University Press. ISBN 0-521-63766-X .
• Tom M. Apostol, Modular functions and Dirichlet Series in Number Theory (1990), Springer-Verlag, New York. ISBN 0-387-97127-0 (See chapter 5 for a modern pedagogical intro to Rademacher's formula).
• Sautoy, Marcus Du. The Music of the Primes. New York: Perennial-HarperCollins, 2003.
• D. H. Lehmer, On the remainder and convergence of the series for the partition function Trans. Amer. Math. Soc. 46(1939) pp 362–373. (Provides the main formula (no derivatives), remainder, and older form for A_k(n).)
• Gupta, Gwyther, Miller, Roy. Soc. Math. Tables, vol 4, Tables of partitions, (1962) (Has text, nearly complete bibliography, but they (and Abramowitz) missed the Selberg formula for A_k(n), which is in Whiteman.)
• Ian G. Macdonald, Symmetric functions and Hall polynomials, Oxford University Press, 1979, ISBN 0-19-853530-9 (See section I.1)
• Ken Ono, Distribution of the partition function modulo m, Annals of Mathematics 151 (2000) pp.293–307. (This paper proves congruences modulo every prime greater than 3)
• Richard P. Stanley, Enumerative Combinatorics, Volumes 1 and 2. Cambridge University Press, 1999 ISBN 0-521-56069-1
• A. L. Whiteman, A sum connected with the series for the partition function, Pacific Journal of Math. 6:1 (1956) 159–176. (Provides the Selberg formula. The older form is the finite Fourier expansion of Selberg.)
• Hans Rademacher, Collected Papers of Hans Rademacher, (1974) MIT Press; v II, p 100–107, 108–122, 460–475.
• Miklós Bóna (2002). A Walk Through Combinatorics: An Introduction to Enumeration and Graph Theory. World Scientific Publishing. ISBN 981-02-4900-4  (qn elementary introduction to the topic of integer partition, including a discussion of Ferrers graphs)
• George E. Andrews, Kimmo Eriksson (2004). Integer Partitions. Cambridge University Press. ISBN 0-521-60090-1 
• 'A Disappearing Number', devised piece by Complicite, mention Ramanujan's work on the Partition Function, 2007

外部リンク

• 『分割数の意味と性質・ヤング図形の活躍』 - 高校数学の美しい物語
• Partition and composition calculator
• First 4096 values of the partition function
• An algorithm to compute the partition function
• Weisstein, Eric W. "Partition Function P". mathworld.wolfram.com (英語).
• Counting with partitions with reference tables to the On-Line Encyclopedia of Integer Sequences
• Integer::Partition Perl module from CPAN
• Amanda Folsom, Zachary A. Kent, and Ken Ono, l-adic properties of the partition function. In press.
• Jan Hendrik Bruinier and Ken Ono, An algebraic formula for the partition function. In press.
• 保型形式の2進的性質について - archive.today（2011年1月1日アーカイブ分） 田口雄一郎(九大数理) 整数論セミナー