分割数
自然数$ nをいくつかの自然数の和で表す場合の数を$ nの分割数という。
$ P(n,k)を自然数$ nを$ k個以下の$ 0以上の整数の和で表す場合の数とすると、$ nの分割数は$ P(n,n)と表せる。
ここで$ P(n,k)を構成する整数列$ a_0,a_1,...,a_kを考える。すると次のような場合分けができる。
(1) 数列$ aの最小値が$ 0
(2) 数列$ aの最小値が$ 1以上
(1)のとき、0を1つ取り除くとこれは$ P(n,k-1)と一致。
(2)のとき、すべての$ a_iについてそれぞれ1ずつ減少させるとこれは$ P(n-k,k)と一致。
以上より
$ P(n,k) = P(n,k-1) + P(n-k,k)
という漸化式が得られる。これはDPによって$ O(nk)で求められる。 また、$ P(n,k)は$ nを$ k以下の自然数の和で表す場合の数と一致する。これは整数列を昇順に並べてヒストグラム状にしたものを高さ1ごとに横方向に分割すれば幅は$ k以下であるため一対一の対応がとれることから確認できる。(ヤング図形を参照)