分割数の定義と母関数

分割数の定義と母関数
ある自然数を自然数に分割する組み合わせの個数を分割数(partition function)という。
分割数を\(P\left(n\right)\)として、\(P\left(0\right)=1\)とすると、

\[ \sum_{k=0}^{\infty}P\left(k\right)z^{k}=\prod_{k=1}^{\infty}\frac{1}{1-z^{k}} \]

が成り立つ。

分割数は

\[ P\left(k\right)=\sum_{k_{1}=0}^{\infty}\sum_{k_{2}=0}^{\infty}\cdots\delta_{k,1k_{1}+2k_{2}+\cdots} \]

であるので、

\begin{align*} \sum_{k=0}^{\infty}P\left(k\right)z^{k} & =\sum_{k=0}^{\infty}\sum_{k_{1}=0}^{\infty}\sum_{k_{2}=0}^{\infty}\cdots\delta_{k,1k_{1}+2k_{2}+\cdots}z^{k}\\ & =\sum_{k=0}^{\infty}\sum_{k_{1}=0}^{\infty}\sum_{k_{2}=0}^{\infty}\cdots\delta_{k,1k_{1}+2k_{2}+\cdots}z^{1k_{1}+2k_{2}+\cdots}\\ & =\sum_{k_{1}=0}^{\infty}\sum_{k_{2}=0}^{\infty}\cdots z^{1k_{1}+2k_{2}+\cdots}\\ & =\sum_{k_{1}=0}^{\infty}z^{k_{1}}\sum_{k_{2}=0}^{\infty}z^{2k_{2}}\cdots\\ & =\left(\frac{1}{1-z}\right)\left(\frac{1}{1-z^{2}}\right)\cdots\\ & =\prod_{k=1}^{\infty}\frac{1}{1-z^{k}} \end{align*}

となる。

具体例

\(P\left(1\right)\)は\(\left(1\right)\)の1通り。
\(P\left(2\right)\)は\(\left(2\right),\left(1,1\right)\)の2通り。
\(P\left(3\right)\)は\(\left(3\right),\left(2,1\right),\left(1,1,1\right)\)の3通り。
\(P\left(4\right)\)は\(\left(4\right),\left(3,1\right),\left(2,2\right),\left(2,1,1\right),\left(1,1,1,1\right)\)の5通り。
\(P\left(5\right)\)は\(\left(5\right),\left(4,1\right),\left(3,2\right),\left(3,1,1\right),\left(2,2,1\right),\left(2,1,1,1\right),\left(1,1,1,1,1\right)\)の7通り。

分割数一覧

\[ \begin{array}{|c|c|} \hline n & P\left(n\right)\\ \hline 0 & 1\\ \hline 1 & 1\\ \hline 2 & 2\\ \hline 3 & 3\\ \hline 4 & 5\\ \hline 5 & 7\\ \hline 6 & 11\\ \hline 7 & 15\\ \hline 8 & 22\\ \hline 9 & 30\\ \hline 10 & 42\\ \hline 11 & 56\\ \hline 12 & 77\\ \hline 13 & 101\\ \hline 14 & 135\\ \hline 15 & 176\\ \hline 16 & 231\\ \hline 17 & 297\\ \hline 18 & 385\\ \hline 19 & 490\\ \hline 20 & 627\\ \hline 21 & 792\\ \hline 22 & 1,002\\ \hline 23 & 1,255\\ \hline 24 & 1,575\\ \hline 25 & 1,958\\ \hline 26 & 2,436\\ \hline 27 & 3,010\\ \hline 28 & 3,718\\ \hline 29 & 4,565\\ \hline 30 & 5,604 \\\hline \end{array} \]

ページ情報

タイトル

分割数の定義と母関数

URL

https://www.nomuramath.com/ucjcnbvq/

SNSボタン