■分割数の漸近挙動(その118)

 「分割数」とは与えられた整数にどれだけ多くの分割があるのか(4=1+1+1+1,4=3+1)という整数の分割理論のことです.整数の分割では,3=2+1と3=1+2のように足し算の順序が違うものは同じと見なすことにします.

 たとえば,4を分割するには非増加数列で構成した5通りの方法,4=3+1=2+2=2+1+1=1+1+1+1がありますから,p(4)=5.同様にして,5=4+1=3+2=3+1+1=2+2+1=2+1+1+1=1+1+1+1+1よりp(5)=7となります.(分割を図形的に表す方法にヤング図形がある.ヤング図形は非増加な非負整数列を表現する印象的な方法である.)

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

【1】分割数の母関数

 たとえば,正の整数nに対して,

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

となる解(k1,k2,k3)の個数をanとします.n=5の場合,

  1+1+1+1+1 → (5,0,0)

  1+1+1+2  → (3,1,0)

  1+1+3   → (2,0,1)

  1+2+2   → (1,2,0)

  2+3    → (0,1,1)

ですから,a5=5となります.

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

 このとき,母関数は

  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

を得ることができます.

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

 この問題を一般化して

  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+・・・

を得たというわけです.

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