数学において、整数分割 (integer partition) は、整数を自然数（正の整数）の和で表したものであるWolfram。同じ自然数を重ねて使ってもよいが、並べる順序のみを違えたものは同じ分割と見なされる。例えば、整数5の分割は以下7個である。

5=5

5=4+1

5=3+2

5=3+1+1

5=2+2+1

5=2+1+1+1

5=1+1+1+1+1

数学的には、増加することのない (non-increasing) 有限個の自然数の列$\backslash lambda=\backslash \{\backslash lambda\_i\backslash \}\_\{i=1\}^\{\backslash ell\}$が分割を表現すると考えて、$|\backslash lambda|=\backslash sum\{\backslash lambda\_i\}$を分割の重さ(weight)という。整数$n$の分割は重さ$n$を持つ分割であるHealy。慣例により、全ての分割の集合を$\backslash mathcal\{P\}$で表す。整数$n$の分割が成す集合$\backslash mathcal\{P\}(n)=\backslash \{\backslash lambda(n)\backslash \}$は

$\backslash mathcal\{P\}(n)=\backslash \{\backslash lambda\backslash in\backslash mathcal\{P\}:|\backslash lambda|=n\backslash \}$

である。

制限された分割

制限された分割、例えば、

• 奇数のみを使う分割 $\backslash mathcal\{O\}=\backslash \{\backslash lambda\backslash in\backslash mathcal\{P\}:2\backslash nmid\backslash lambda\_i\backslash \}$
• 同じ数を重ねて使わない分割 $\backslash mathcal\{Q\}=\backslash \{\backslash lambda\backslash in\backslash mathcal\{P\}:\backslash lambda\_i>\backslash lambda\_\{i+1\}\backslash \}$
• 同じ数を重ねて使わず、且つ、偶数個の数への分割 $\backslash mathcal\{Q\}^0=\backslash \{\backslash lambda\backslash in\backslash mathcal\{P\}:2\backslash mid\backslash ell,\backslash lambda\_i>\backslash lambda\_\{i+1\}\backslash \}$
• 同じ数を重ねて使わず、且つ、奇数個の数への分割 $\backslash mathcal\{Q\}^1=\backslash \{\backslash lambda\backslash in\backslash mathcal\{P\}:2\backslash nmid\backslash ell,\backslash lambda\_i>\backslash lambda\_\{i+1\}\backslash \}$

なども古くから研究されている。

分割恒等式

分割数について多くの定理が知られている。例えば、オイラーの分割恒等式は

$|\backslash mathcal\{O\}(n)|=|\backslash mathcal\{Q\}(n)|$

を主張し、オイラーの五角数定理は

を主張する。

分割関数

分割関数 (partition function) は整数$n$の分割の個数を与える関数である。

$p(n)=|\backslash mathcal\{P\}\_(n)|$

便宜上、$p(0)=1,p(-n)=0\backslash ;(n\backslash in\backslash mathbb\{N\})$と定義することが多い。

分割関数の母関数

分割関数の母関数は、

$\backslash begin\{align\}1+\backslash sum\_\{n=1\}^\{\backslash infty\}p(n)q^n$

&=\prod_{m=1}^{\infty}\left(1+\sum_{n=1}^{\infty}q^{nm}\right)\\ &=\prod_{m=1}^{\infty}\frac{1}{1-q^m} \end{align} である。例えば、$q^5$の項を抜き出すと

$\backslash begin\{align\}p(5)q^5$

&=q^{5\cdot1}+q^{1\cdot2}q^{3\cdot1}+q^{2\cdot2}q^{1\cdot1}+q^{1\cdot3}q^{1\cdot2}+q^{1\cdot3}q^{2\cdot1}+q^{1\cdot4}q^{1\cdot1}+q^{1\cdot5}\\ &=q^{1+1+1+1+1}+q^{2+1+1+1}+q^{2+2+1}+q^{3+2}+q^{3+1+1}+q^{4+1}+q^{5}\\ &=7q^5\\ \end{align}

であり、$p(5)=7$である。

分割関数の漸化式

分割関数の母関数は、オイラーの五角数定理により、

$\backslash begin\{align\}1+\backslash sum\_\{n=1\}^\{\backslash infty\}p(n)q^n$

&=\frac{1}{\displaystyle\sum_{k=\infty}^{\infty}(-1)^kq^{(3k^2-k)/2}}\\ &=\frac{1}{1+\displaystyle\sum_{k=1}^{\infty}(-1)^kq^{(3k^2-k)/2}+\displaystyle\sum_{k=1}^{\infty}(-1)^kq^{(3k^2+k)/2}}\\ \end{align} となる。従って、

$\backslash left(1+\backslash sum\_\{n=1\}^\{\backslash infty\}p(n)q^n\backslash right)\backslash left(1+\backslash sum\_\{k=1\}^\{\backslash infty\}(-1)^kq^\{(3k^2-k)/2\}+\backslash displaystyle\backslash sum\_\{k=1\}^\{\backslash infty\}(-1)^kq^\{(3k^2+k)/2\}\backslash right)=1$

であるが、$q^n$の係数を比べて

$\backslash begin\{align\}$

&p(n)+\sum_{k\ge1}(-1)^kp\left(n-\frac{3k^2-k}{2}\right)+\sum_{k\ge1}(-1)^kp\left(n-\frac{3k^2+k}{2}\right)\\ &p(n)=\sum_{k\ge1}(-1)^{k+1}p\left(n-\frac{3k^2-k}{2}\right)+\sum_{k\ge1}(-1)^{k+1}p\left(n-\frac{3k^2+k}{2}\right)\\ \end{align} となる。但し、$p(0)=1,p(-n)=0\backslash ;(n\backslash in\backslash mathbb\{N\})$とする。例えば、

$p(13)=p(12)+p(11)-p(8)-p(6)+p(1)=77+56-22-11+1=101$

である。

関連記事

• オイラーの分割恒等式
• オイラーの五角数定理

出典