オイラーの分割恒等式
提供: miniwiki
数論、組合せ論におけるオイラーの分割恒等式(オイラーのぶんかつこうとうしき)は、自然数(正の整数)を「互いに異なる自然数に分割する方法の個数」(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 を互いに異なる自然数に分割する方法の数を Pd(n) とすると
- [math]\sum_{n=1}^{\infty}P_d(n)x^n=\prod_{m=1}^{\infty}\left(1+x^m\right)[/math]
である。また、自然数 n を奇数の自然数に分割する方法の数を Po(n) とすると
- [math]\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}}[/math]
である。従って、オイラーの分割恒等式は
- [math]\prod_{m=1}^{\infty}\left(1+x^m\right)=\prod_{m=1}^{\infty}\frac{1}{1-x^{2m-1}}[/math]
と書き表される。
証明
母関数で書き表したものの左辺を変形すると右辺が得られる。
- [math]\begin{align}\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{align}[/math]
初等的な説明
例として 8 を分割することを考える。ここで P を「異なる数による分割」に現れる一つの偶数をその半分の二つの整数の和にする変換、U を「奇数のみの分割」に現れる同じ二つの整数を一つの偶数にする変換とすると
- [math]1+(2)+5 \xrightarrow{\quad P \quad} 1+[1+1]+5 \xrightarrow{\quad U \quad} 1+2+5[/math]
- [math]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[/math]
- [math]1+7 \xrightarrow{\quad I \quad} 1+7[/math]
- [math](2)+(6) \xrightarrow{\quad P \quad} [1+1]+[3+3] \xrightarrow{\quad U \quad} 2+6[/math]
- [math]3+5 \xrightarrow{\quad I \quad} 3+5[/math]
- [math](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[/math]
このように「異なる数による分割」の方法と「奇数のみの分割」の方法との間に1対1対応がつけられる。これはPとUが互いに逆の変換であることから導かれる。したがってそれらの方法の個数は互いに等しい。ただし上記の 1+7 や 3+5 のような「異なる数による分割」と「奇数のみの分割」の両方に属するような方法は自分自身に対応づけることとする。その場合は恒等写像 I で表した。
注
参考文献
- Andrews, George E.; Eriksson, Kimmo (2004), Integer Partitions (2nd ed.), Cambridge University Press, ISBN 0-521-60090-1
- 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
関連項目
外部リンク
- Weisstein, Eric W. “Partition Function Q”. MathWorld(英語). Template:Cite webの呼び出しエラー:引数 accessdate は必須です。
- Alexander D. Healy, Partition Identities
- アンドリュ-ス, エリクソン『整数の分割』書評 (PDF)