fortran66のブログ

fortran について書きます。

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

分割数に関する漸化式

整数の分割数 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)

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

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}
}

ここで、最後の式で k+j=n とすれば


{\displaystyle
\sum_{n=1}^\infty np(n)\,t^{n-1}=\sum_{n=1}^\infty\sum_{k=1}^n\sigma(k)p(n-k)\,t^{n-1}
}

が得られる。

辺々べきの等しい項を比べて、分割数に関する漸化式、


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

が得られる。