自然数を1以上の自然数の和で表すことを考える。ただし、順序は問わない。 例えば、n=5について、 1個に分ける:5 の1通り 2個に分ける:1+4、2+3 の2通り 3個に分ける:1+1+3、1+2+2 の2通り 4個に分ける:1+1+1+2 の1通り 5個に分ける:1+1+1+1+1 の1通り より、5の分割数は7となる。 自然数nの分割数を p(n) で表す。 また、上のように、自然数nをr個に分けた時の分け方の個数を、p(n,r) で表す。 上より明らかに、 p(n) =r Σ i=1 p(n,i) である。 p(n,r) には、以下の関係式が成り立つ。 p(n,1)=1 p(n,n)=1 p(n,r)=p(n-r,r)+p(n-1,r-1) ただし、n<rのとき、p(n,r)=0と定義する。 これらの関係式より、任意のnについて p(n) を計算することができる。 この関係式をEx