オイラーの分割恒等式

数論、組合せ論におけるオイラーの分割恒等式（オイラーのぶんかつこうとうしき）は、自然数（正の整数）を「互いに異なる自然数に分割する方法の個数」(distinct partition; 異分割) と「奇数の自然数に分割する方法の個数」(odd partotion; 奇分割) が等しいことを示す恒等式である。^[1]

分割の例

例えば、自然数 8 を互いに異なる自然数に分割する方法

8 = 1+2+5

8 = 1+3+4

8 = 1+7

8 = 2+6

8 = 3+5

8 = 8

と奇数の自然数に分割する方法

8 = 1+1+1+1+1+1+1+1

8 = 1+1+1+1+1+3

8 = 1+1+1+5

8 = 1+1+3+3

8 = 1+7

8 = 3+5

の個数は等しく 6 である。

自然数 n をこのように分割する方法の個数を Q(n) で表すと、

Q(1) = 1, Q(2) = 1, Q(3) = 2, Q(4) = 2, Q(5) = 3, Q(6) = 4, Q(7) = 5, Q(8) = 6, Q(9) = 8, Q(10) = 10, … （オンライン整数列大辞典の数列 A9）

などと続く。

母関数による表現

オイラーは2種類の分割の方法の個数が等しいことを、母関数を用いて示した。自然数 n を互いに異なる自然数に分割する方法の数を P_d(n) とすると

1+\sum _{n=1}^{\infty }P_{d}(n)x^{n}=\prod _{m=1}^{\infty }\left(1+x^{m}\right)

である。また、自然数 n を奇数の自然数に分割する方法の数を P_o(n) とすると

1+\sum _{n=1}^{\infty }P_{o}(n)x^{n}=\prod _{m=1}^{\infty }\left(1+\sum _{k=1}^{\infty }x^{k(2m-1)}\right)=\prod _{m=1}^{\infty }{\frac {1}{1-x^{2m-1}}}

である。従って、オイラーの分割恒等式は

\prod _{m=1}^{\infty }\left(1+x^{m}\right)=\prod _{m=1}^{\infty }{\frac {1}{1-x^{2m-1}}}

と書き表される。

証明

母関数で書き表したものの左辺を変形すると右辺が得られる。

{\begin{aligned}\prod _{m=1}^{\infty }\left(1+x^{m}\right)&=\prod _{m=1}^{\infty }{\frac {\left(1+x^{m}\right)\left(1-x^{m}\right)}{1-x^{m}}}\\&=\prod _{m=1}^{\infty }{\frac {1-x^{2m}}{1-x^{m}}}\\&={\frac {1-x^{2\cdot 1}}{1-x^{1}}}\cdot {\frac {1-x^{2\cdot 2}}{1-x^{2}}}\cdot {\frac {1-x^{2\cdot 3}}{1-x^{3}}}\cdot {\frac {1-x^{2\cdot 4}}{1-x^{4}}}\cdot ...\\&=\prod _{m=1}^{\infty }{\frac {1-x^{2m}}{\left(1-x^{2m-1}\right)\left(1-x^{2m}\right)}}\\&=\prod _{m=1}^{\infty }{\frac {1}{1-x^{2m-1}}}\\\end{aligned}}

初等的な説明

例として 8 を分割することを考える。ここで P を「異なる数による分割」に現れる一つの偶数をその半分の二つの整数の和にする変換、U を「奇数のみの分割」に現れる同じ二つの整数を一つの偶数にする変換とすると

1+(2)+5{\xrightarrow {\quad P\quad }}1+[1+1]+5{\xrightarrow {\quad U\quad }}1+2+5

1+3+(4){\xrightarrow {\quad P\quad }}1+[(2)+(2)]+3{\xrightarrow {\quad P\quad }}1+[1+1]+[1+1]+3{\xrightarrow {\quad U\quad }}1+((2)+(2))+3{\xrightarrow {\quad U\quad }}1+3+4

1+7{\xrightarrow {\quad I\quad }}1+7

(2)+(6){\xrightarrow {\quad P\quad }}[1+1]+[3+3]{\xrightarrow {\quad U\quad }}2+6

3+5{\xrightarrow {\quad I\quad }}3+5

(8){\xrightarrow {P}}[(4)+(4)]{\xrightarrow {P}}[(2)+(2)]+[(2)+(2)]{\xrightarrow {P}}[1+1]+[1+1]+[1+1]+[1+1]{\xrightarrow {U}}(2+2)+(2+2){\xrightarrow {U}}(4+4){\xrightarrow {U}}8

このように「異なる数による分割」の方法と「奇数のみの分割」の方法との間に1対1対応がつけられる。これはPとUが互いに逆の変換であることから導かれる。したがってそれらの方法の個数は互いに等しい。ただし上記の 1+7 や 3+5 のような「異なる数による分割」と「奇数のみの分割」の両方に属するような方法は自分自身に対応づけることとする。その場合は恒等写像 I で表した。

注

^ 整数の分割の母関数と組合せ論定理 2.4. (PDF)

参考文献

Andrews, George E.; Eriksson, Kimmo (2004), Integer Partitions (2nd ed.), Cambridge University Press, ISBN 0-521-60090-1
- ジョージ・アンドリュース、キムモ・エリクソン『整数の分割』佐藤文広訳、数学書房(出版) 白揚社(発売)、2006年5月。ISBN 978-4-8269-3103-8。 - 注記：原著第2版の翻訳。
Hardy, G. H.; Wright, E. M. (2008) [1938], Heath-Brown, D. R.; Silverman, J. H.; Wiles, Andrew, eds., An Introduction to the Theory of Numbers (6th ed.), Oxford: Oxford University Press, ISBN 978-0-19-921985-8
- G.H.ハーディ、E.M.ライト「第19章　分割」『数論入門』 II、示野信一・矢神毅訳、丸善出版〈シュプリンガー数学クラシックス9〉、2012年4月。ISBN 978-4-621-06247-0。 - 注記：原著第5版の翻訳。

外部リンク

Weisstein, Eric W. "Partition Function Q". mathworld.wolfram.com (英語).
Alexander D. Healy, Partition Identities
アンドリュ－ス, エリクソン『整数の分割』書評 (PDF)

[1] 整数の分割の母関数と組合せ論定理 2.4. (PDF)

[1]