分割数

提供: miniwiki
2017/11/21/ (火) 14:44時点における133.86.108.32 (トーク)による版
(差分) ← 古い版 | 最新版 (差分) | 新しい版 → (差分)
移動先:案内検索

数論における分割数(ぶんかつすう、: partition functionp(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.4×10{{#invoke:Gapnum|main|31}}.

テンプレート:As of、知られている中でこの形で得られる最大の素数は、Bernardo Boncompagni が発見した[1] p(40100918) で、これは十進で 7047 桁の数値である。

補助函数

分割函数をより扱いやすくする方法のひとつは、補助的な函数 p(k, n) を考えることである。これは少なくとも k 以上の自然数を用いて n を分割する方法の数を数えたもので、各 k に対して分割数を数えれば、次のいずれかの場合を見ればいいことになる。

  1. 最小の成分がちょうど k である。
  2. 最小の成分が k より真に大きい。

前者に当たる分割の総数は p(k, nk) である。これをみるには、整数 nk を少なくとも k よりもサイズの大きい整数への分割を全て一覧したものを考えて、その一覧の各分割に "+ k" することを考えればよい。

このことは、補助的な函数を使って分割数のある種の漸化式を定義することに利用できる。つまり

[math]1+\sum_{k=1}^{\lfloor \frac{1}{2}n \rfloor} p(k,n-k) = p(n),[/math]

が成立する。ここで、[math]\lfloor n\rfloor[/math]床函数である。

後者に当たる分割の総数は p(k +1, n) である。これは各成分が k 以上の分割から、ちょうど k になる成分を含むようなものを除いた結果は、すべての成分が k + 1 以上になっていなければならないことからわかる。

さて、上記の二条件は互いに排他的であるから、n の分割の総数というのは、それぞれの場合をあわせた p(k + 1, n) + p(k, nk) となっていることがわかる。したがって、再帰的に、補助的な函数を

  • k > n のとき: p(k, n) = 0
  • k = n のとき: p(k, n) = 1
  • それ以外: p(k, n) = p(k+1, n) + p(k, nk)

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

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) にあたる。

いくつかの値については以下のとおり。

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) の母函数は、次の式で与えられる。

[math]\sum_{n=0}^\infty p(n)x^n = \prod_{k=1}^\infty \left(\frac {1}{1-x^k} \right).[/math]

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

(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) + ...,

を得る。ここで各数 iai 個ずつ現れる。これはまさに n の分割の定義そのものであるから、この無限積が求める母函数を与えることが確認できる。もっと一般に、整数 n の適当な集合 A に属する整数への分割数の母函数も、上記の式の項の kA の弦となっているものにとることで得られる。この結果はオイラーによる。

オイラーによるこのような分割数の母函数の定式化は 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 で終わる整数に対する分割数に関して合同式

[math]p(5k+4)\equiv 0 \pmod 5[/math]

が成立することを発見したといわれる。例えば、整数 4 の分割数は 5 であり、整数 9 の分割数は 30、整数 14 の分割数は 135 といった具合である。ラマヌジャンはまた 7 および 11 に関する合同式

[math]\begin{align} p(7k + 5) &\equiv 0 \pmod 7\\ p(11k+ 6) &\equiv 0 \pmod{11} \end{align}[/math]

も発見している。さて、5, 7, 11 は連続する素数になっているので、次の素数 13 に対する同様の合同式 p(13k + a) ≡ 0 (mod 13) が適当な a のもと成立しそうなものだが、実際にはそうはなっていない。さらにいえば、p(bk + a) ≡ 0 (mod b) の形の合同式は 5, 7, 11 以外のどの素数 b に対しても成立しないことが示せる[2]

1960年代にイリノイ大学シカゴ校アトキンは、同様のいくつかの小さな素数を法とする合同式を発見している。例えば

[math]p(11^3 \cdot 13 \cdot k + 237)\equiv 0 \pmod {13}[/math]

のようなものが含まれる。2000年には、ウィスコンシン大学マディソン校小野(Ken Ono)は任意の素数を法とする同様の合同式の存在を示した。さらに数年後、小野はイリノイ大学のスコット・アールグレンとともに、6 と互いに素なすべての整数を法とする分割数の合同式が存在することを証明している[3]

  • 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) の漸近表示は、

[math]p(n) \sim \frac{1}{4n\sqrt{3}} e^{\pi \sqrt{\frac{2n}{3}}} \mbox { as } n\to \infty.[/math]

で与えられる。この漸近公式は、ハーディラマヌジャンによって1918年に初めて見出され、また、それとは独立にウスペンスキーが1920年に発見している。例えば p(1000) を考えると、漸近公式からだいたい 2.4402 × 1031 となることがわかるが、これは真の値とくらべても十分近い値である(真の値よりは 1.415% ほど大きい)。

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

[math]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) [/math]

を得ている。ただし

[math]A_k(n) = \sum_{0\le m\lt k\atop (m,k)=1}e^{\pi i\left[s(m,k)-\frac{1}{k} 2nm \right]}[/math]

とおいた。この式の微分の箇所はもう少し簡単な形に直せる[4]。ここで、記号 (m, n) = 1 は m の値として n互いに素であるものだけを考えることを意味する。また函数 s(mk) はデデキント和である。ラーデマッハーの公式の証明はフォード円ファレイ数列モジュラー対称性およびデデキント・イータ函数などを主に使ってなされる。

2011年1月、小野とダルムシュタット工科大学のジャン・ヘンドリック・ブルーニエは、任意の自然数 n に対する p(n) を決定する有限で代数的な公式を得たと発表した[5][6]

分割数は n の「五角数分割」上の和として表すことができる。

[math] n = k_1 + 2k_2 + 5k_5 + \cdots = \sum_m q_m k_{q_m}[/math]

n の五角数分割とする。ここに各 qm = m(3m − 1)/2 は一般五角数(GPN, 数列 テンプレート:OEIS2C)で qMn を超えない最大の GPN である。故に[7]

[math] 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}}}, [/math]

を得る。ここで

[math] \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}[/math]

および

[math] \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} [/math]

多項係数である。p(n) に対する和の項の数は数列 テンプレート:OEIS2C で与えられる。例えば 8 = 7+1 = 5+2+1 = 5+1+1+1 = 2+2+2+2 = ... だから

[math]\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} [/math]

となる。

行列式公式

各自然数 n に対して p(n) は次の式で求められる。

[math]\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} .[/math]

つまり、p(n) は上記無限次元テープリッツ行列n × n で止めた正方行列の行列式である。この行列の零でない成分は、一般五角数 qm 番目の行の先頭から斜め (diagonal) に配置され(主対角線のひとつ上側の成分 (superdiagonel) は仮想的に 0 番目の行からと考える)、その値が (−1)m+1 となっている。この行列式公式は、次の行列の間の関係式

[math] \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} [/math]

に同値なのだが、この関係式自体は単に上述の母函数の間の関係式(と五角数定理)を行列の形にまとめたものである。

ラマヌジャンの公式[8]

[math] \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)[/math]

を使えば、分割数 p(5k − 1) はより小さな k-次行列の行列式

[math] 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} [/math]

として表すことができる。第一列の成分のなす数列は テンプレート:OEIS2C であり、最終列の(最初の 1 から)五つ毎に現れる非零成分のなす数列 (1, −5, 5, 10, −15, −6, …) は、数列 テンプレート:OEIS2C になっている(最終列はそれ以外の成分は全て零である)。例えば

[math] 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.[/math]

同様のやり方で、残り二つのラマヌジャンの公式を使えば、分割数 p(7k − 2) および p(25k − 1) も k-次の行列式

[math] \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} [/math]

と表すことができる。これらの行列の最初の列はそれぞれ テンプレート:OEIS2C および テンプレート:OEIS2C であり、最終列は次の展開

[math] \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} [/math]

から得られる。例えば p(149) は

[math] 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[/math]

で計算できる。また、分割数の第 n-部分和は行列式

[math] \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}[/math]

で与えられる。ただし、c0 = −1, c1 = 2, c2 = 0 かつ k > 2 に対しては

[math] 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}[/math]

とする。相異なる整数成分への分割の分割数を q(n) と書けば(これは分割の項に述べるように奇数成分への分割の分割数とも等しく)、

[math] 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)} [/math]

が成り立つ。第一列は数列 テンプレート:OEIS2C で、最終列は 2qm + 1 行目の成分が (−1)m でそれ以外の成分は零である。

関連項目

注意

  1. http://primes.utm.edu/top20/page.php?id=54
  2. S. Ahlgren and M. Boylan, Arithmetic properties of the partition function, Invent. Math. 153 (2003), no. 3, 487–502.
  3. Ono, Ken; Ahlgren, Scott (2001). “Congruence properties for the partition function”. Proceedings of the National Academy of Sciences 98 (23): 12,882–12,884. doi:10.1073/pnas.191488598. オリジナルの2011年6月7日時点によるアーカイブ。. https://web.archive.org/web/20110607123453/http://www.math.wisc.edu/~ono/reprints/061.pdf. 
  4. WolframAlpha”. . 2011閲覧.
  5. http://www.aimath.org/news/partition/
  6. Bruinier and Ono, "Algebraic formulas for the coefficients of half-integral weight harmonic weak Maass forms"
  7. J. Malenfant, "Finite, Closed-form Expressions for the Partition Function and for Euler, Bernoulli, and Stirling Numbers".
  8. Berndt and Ono, "Ramanujan's Unpublished Manuscript on the Partition and Tau Functions with Proofs and Commentary" アーカイブされたコピー”. 2011年9月27日時点のオリジナルよりアーカイブ。. 2011年3月20日閲覧.

参考文献

  • 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 Ak(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 Ak(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

外部リンク