【メモ帳】分割数と約数和の漸化式

分割数に関する漸化式

整数の分割数 $p(n)$ と約数和関数 $\sigma(n)$ の関わる漸化式。

${\displaystyle p(n)={1\over n}\sum_{k=1}^n\sigma(k)p(n-k) }$

Symmetric Functions and Hall Polynomials (Oxford Classic Texts in the Physical Sciences: Oxford Mathematical Mongraphs)

作者: I. G. MacDonald,A. V. Zelevinsky
出版社/メーカー: Oxford Univ Pr
発売日: 2015/12/22
メディア: ペーパーバック
この商品を含むブログを見る

p.27 (1) 式

証明

整数 $n$ の約数の和を取る約数和関数 $\sigma(n)$ の母関数 $S(t)$ は以下のようになっている。

${\displaystyle S(t)= \sum_{k=1}^\infty\sigma(k)\,t^{k-1}=\sum_{k=1}^\infty{kt^{k-1}\over1-t^k} }$

これは、一番右の式の分母を級数に展開し、各次数ごとにまとめることで示せる。（TeX では書きにくいですが、表形式で項を並べると約数が出てくることがはっきりします。）

${\displaystyle \begin{align} S(t)&={1\over1-t}+{2t\over 1-t^2}+{3t^2\over 1-t^3}+{4t^3\over 1-t^4}+\cdots\\ &=(1+t+t^2+\cdots)+2t(1+t^2+t^4+\cdots)+3t^2(1+t^3+t^6+\cdots)+4t^3(1+t^4+t^8+\cdots)+\cdots\\ &=1+(1+2)t+(1+3)t^2+(1+2+4)t^3+(1+5)t^4+(1+2+3+6)t^5+(1+7)t^6+\cdots\\ &=\sigma(1)+\sigma(2)t+\sigma(3)t^2+\sigma(4)t^3+\sigma(5)t^4+\sigma(6)t^5+\sigma(7)t^6+\cdots\\ &=\sum_{k=1}^\infty\sigma(k)\,t^{k-1} \end{align} }$

また、一番右の表式は、

${\displaystyle \sum_{k=1}^\infty{kt^{k-1}\over1-t^k}=-\sum_{k=1}^\infty{d\over dt}\log(1-t^k)={d\over dt}\log(\prod_{k=1}^\infty{1\over1-t^k}) }$

とも表わせる。つまり、

${\displaystyle S(t)=\sum_{k=1}^\infty\sigma(k)t^{k-1}={d\over dt}\log(\prod_{k=1}^\infty{1\over1-t^k}) }$

の関係が得られた。

一方で Euler により分割数 $p(k)$ の母関数は以下のようにあらわされた。

${\displaystyle P(t)=\sum_{k=0}^\infty p(k) \,t^k=\prod_{k=1}^\infty {1\over1-t^k} }$

但し、ここで形式上 0 の分割数を $p(0)=1$ とした。

上で $S(t)$ について求めた関係から、

${\displaystyle S(t)={d\over dt}\log P(t)={P'(t)\over P(t)} }$

つまり、

${\displaystyle P'(t)=S(t)P(t) }$

が得られる。

この式に、級数表示の式を入れると、

${\displaystyle \sum_{n=1}^\infty np(n)\,t^{n-1}=\left(\sum_{k=1}^{\infty}\sigma(k)\,t^{k-1}\right)\left(\sum_{j=0}^{\infty}p(j)\,t^j\right)=\sum_{k=1}^\infty\sum_{j=0}^\infty\sigma(k)p(j)\,t^{k+j-1} }$