分割数

分割数

数論において、自然数 $n$ をいくつかの自然数の和として表現する方法の総数を分割数と呼び、$p(n)$ と記します。ただし、和の項の順序は区別しません。例えば、$n=4$ の場合、分割は $4$, $3+1$, $2+2$, $2+1+1$, $1+1+1+1$ の5通りですから、$p(4)=5$ となります。便宜上、$p(0)=1$ と定め、負の整数 $n<0$ に対しては $p(n)=0$ とします。

分割数の値は $n$ が増加するにつれて非常に速く増加します。例えば、

$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 \times 10^{31}$）

といった巨大な値になります。2020年2月現在、知られている中でこの形式で得られる最大の素数は $p(1289844341)$ であり、これは十進法で4万桁にも及ぶ数値です。

分割数の計算

分割数を計算する方法はいくつか知られています。

再帰的な方法:

$n$ を $k$ 以上の自然数で分割する方法の数を $p(k, n)$ という補助関数で考えると、分割数の列の一般項 $p(n)$ は $p(1, n)$ にあたります。$p(k, n)$ は、最小の成分が $k$ である場合（その数は $p(k, n-k)$）と、最小の成分が $k$ より大きい場合（その数は $p(k+1, n)$）に分けて考えることで、次の再帰的な定義が得られます。

$$p(k,n):=\left\{{\begin{array}{ll}0&(k>n)\\1&(k=n)\\p(k+1,n)+p(k,n-k)&(k
これにより、$p(n)$ を順次計算していくことが可能です。

母関数による方法:

数学者オイラーは、分割数 $p(n)$ の母関数が次の無限積で与えられることを示しました。

$$\sum_{n=0}^{\infty}p(n)x^{n}=\prod_{k=1}^{\infty}{\dfrac{1}{1-x^{k}}}$$

この右辺を形式的に展開すると、$(1+x+x^2+...)(1+x^2+x^4+...)(1+x^3+x^6+...)...$ となり、$x^n$ の係数は、$n$ を $1$ の項、 $2$ の項、 $3$ の項などの和で表現する方法の総数、すなわち $n$ の分割の総数に一致します。この母関数を用いると、オイラーの五角数定理と組み合わせて、分割数の漸化式を得ることができます。

$$p(k) = p(k-1) + p(k-2) - p(k-5) - p(k-7) + p(k-12) + p(k-15) - \cdots$$

ここで、五角数 ½m(3m − 1) の形をした指数に対応する $p$ の項が加算・減算され、$p(0)=1$、負の引数に対しては $p=0$ とします。

合同算術

インドの天才数学者ラマヌジャンは、分割数に関する驚くべき合同式を発見しました。特に、

$p(5k+4)$ は常に $5$ の倍数である ($p(5k+4) \equiv 0 \pmod{5}$)
$p(7k+5)$ は常に $7$ の倍数である ($p(7k+5) \equiv 0 \pmod{7}$)
$p(11k+6)$ は常に $11$ の倍数である ($p(11k+6) \equiv 0 \pmod{11}$)

といった性質を見出しました。これらの素数 5, 7, 11 は連続していますが、13に対して同様の簡単な形の合同式は存在しないことが後に示されています。その後、アトキンや小野賢人といった数学者たちによって、より複雑な形の合同式や、任意の素数を法とする合同式の存在が証明されるなど、この分野の研究は大きく発展しました。

分割数の公式

分割数の正確な値や漸近的な振る舞いを記述するいくつかの重要な公式があります。

漸近公式:

$n$ が非常に大きい場合の $p(n)$ の近似値は、ハーディとラマヌジャン（後にウスペンスキーも独立に発見）によって与えられた次の漸近公式でよく記述されます。

$$p(n)\sim{\frac{1}{4n{\sqrt{3}}}}e^{\pi{\sqrt{\frac{2n}{3}}}}\quad{\mbox{ as }}n\to\infty.$$

この公式は、$n$ が大きいほど真の値に近い値を与えます。例えば $p(1000)$ の値と比較しても、非常に良い近似であることが確認されています。

厳密な公式:

1937年、ラーデマッハーはハーディとラマヌジャンの研究を発展させ、$p(n)$ を正確に計算できる収束級数表示を与えました。この公式はデデキント和や変形ベッセル関数などを含む複雑な形をしています。
また、2011年にはブルーニエと小野によって、任意の自然数 $n$ に対する $p(n)$ の値を決定する有限で代数的な公式が発表されています。

* 行列式表示:

分割数 $p(n)$ は、無限次元の行列（テープリッツ行列と呼ばれる形式）を $n \times n$ で切り取った行列式として表現できることも知られています。この公式は、オイラーの五角数定理に由来する母関数の関係式と関連しています。ラマヌジャンの合同式に対応する特定の形の分割数（例えば $p(5k-1)$）についても、より小さなサイズの行列式による公式が存在します。

分割数は、組合せ論の基本的な対象であるだけでなく、解析数論における深い理論や、モジュラー形式などの分野とも密接に関連しており、現在も活発な研究対象となっています。

もう一度検索