■n=Σ□(その39)

 ある整数nを3以下の自然数に分解する場合の数を計算することを考える.

 1をk1個,2をk2個,3をk3個,一般に,正の整数nに対して,

  n=k1+2k2+3k3   (k1≧0,k2≧0,k3≧0)

となる解(k1,k2,k3)の個数をanとします.

===================================

【1】分割数の母関数

 このとき,母関数は

  f(x)=Σanx^n=Σx^(k1+2k2+3k3)=Σx^k1Σx^2k2Σx^3k3

 =1/(1−x)・1/(1−x^2)・1/(1−x^3)

となります.

  (1−x)(1−x^2)(1−x^3)Σanx^n=1

ですから,各項の係数を比較すると漸化式

  an=an-1+an-2−an-4−an-5+an-6

を得ることができます.

  a0=1,a1=1,a2=2,a3=3,a4=4,a5=5,

  a6=7,a7=8,a8=10,a9=12,a10=14,a11=16,

  ・・・,a50=234,・・・

===================================

 この問題を一般化して

  n=k1+2k2+3k3+・・・   (k1≧0,k2≧0,k3≧0,・・・)の個数p(n)を考えます.n=5の場合,a5に

  1+4,5

が加わり,p(5)=7となります.

 このことから,分割数は以下の公式によって代数的に定義することができることがわかります.

  f(x)=Π(1-x^n)^(-1)={(1-x)(1-x^2)・・・(1-x^n)・・・}^(-1)

    =(1+x+x^2+・・・)(1+x^2+x^4+・・・)(1+x^3+x^6+・・・)(1+x^4+x^8+・・・)・・・

    =Σp(n)x^n=1+p(1)x+p(2)x^2+p(3)x^3+・・・

すなわち,f(x)は分割関数p(n)の母関数で,p(n)はx^nの係数になっています.

 x^k1を第1因子(1+x+x^2+・・・)の一般項,x^2k2を第2因子(1+x^2+x^4+・・・)の一般項,x^3k3を第3因子(1+x^3+x^6+・・・)の一般項,・・・とすると,

  n=k1+2k2+3k3+・・・

となって,x^nの項が整数nの分割に対応することになるのですが,オイラーはこのようにしてp(n)の母関数

  f(x)=Π(1-x^n)^(-1)={(1-x)(1-x^2)・・・(1-x^n)・・・}^(-1)

    =Σp(n)x^n=1+p(1)x+p(2)x^2+p(3)x^3+・・・

を得たというわけです.

===================================