【４】分割数の母関数

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

　たとえば，４を分割するには非増加数列で構成した５通りの方法，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となります．（分割を図形的に表す方法にヤング図形がある．ヤング図形は非増加な非負整数列を表現する印象的な方法である．）

　　p(0)=1,p(1)=1,p(2)=2,p(3)=3,p(4)=5,p(5)=7,p(6)=11,

　　p(7)=15,p(8)=22,p(9)=30,p(10)=41,p(11)=56,p(12)=77,･･･

ここで，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+･･･

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

　オイラーは，４平方和定理

　　「すべての正の整数は４個の整数の平方和で表される」

を証明するために，級数

　　g(x)=1+Σｘ^(n^2)=1+x+x^4+x^9+x^16+･･･

を考察しています．すると，τ(n)を４つの平方数の和に表す仕方の数として，その母関数は

　　g(x)^4=Στ(n)x^n

となります．（しかし，当時これを確認するのは困難で，１９世紀に入ってからヤコビが楕円関数を用いて解決しました．）

　オイラーのアイディアは，ｎの分割

　　ｎ＝ｎ1＋ｎ2＋・・・＋ｎk

がｎをｋ個の平方数の和への分割（ｎが平方和として何通りに書けるか）：

　　ｎ＝□1＋□2＋・・・＋□k

として表した場合の解と１対１に対応することより，

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

　　　　=Π(1-x^n)^(-1)

　ｘ^k1を第１因子(1+x+x^2+･･･)の一般項，ｘ^2k2を第２因子(1+x^2+x^4+･･･)の一般項，ｘ^3k3を第３因子(1+x^3+x^6+･･･)の一般項，・・・とすると，

　　ｎ＝ｋ1＋２ｋ2＋３ｋ3＋・・・

となって，ｘ^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+･･･

を得ています．

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

［補］分割数の漸近挙動

　σ(k)をｋの約数の和とすると，p(n)に対する漸化式

　　p(n)=1/nΣσ(k)p(n-k)

が得られます．

　また，σ(k)の漸近的振る舞い

　　1/n^2Σσ(k)〜π^2/12

を用いると，ｎが大きい場合の分割数の漸近挙動

　　p(n)〜exp(π√(2n/3))/4n√3

を得ることができます（ハーディーとラマヌジャン，１９１８年）．

　なお，分割を数え上げるとき，並べる順番は問題にしませんが，もし，順番を考慮すると答えは非常に簡単になります．自然数ｎをｋ分割する総数は

　　ｎ＝ｉ1＋ｉ2＋・・・＋ｉk

において，ｉj≧１より，ｎ−１カ所にｋ−１枚の仕切りをつけて分配する問題と等価になります．

　　(n-1)Ｃ(k-1)＝(n-1,k-1)

　したがって，

　　Σ(n-1,k-1)＝２^(n-1)

より２^(n-1)通りあります．このことより，ｎ＝３では４つの順序つき分割

　　3=1+1+1,3=1+2,3=2+1,3=3

が存在することがわかります．

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝