【２】制限のある分割

ある整数ｎを３以下の自然数に分解することを考えます．１をｋ1個，２をｋ2個，３をｋ3個，一般に，正の整数ｎに対して，

ｎ＝ｋ1＋２ｋ2＋３ｋ3　　　（ｋ1≧０，ｋ2≧０，ｋ3≧０）

となる解（ｋ1，ｋ2，ｋ3）の個数をａnとします．ｎ＝５の場合，

1+1+1+1+1　→　（５，０，０）

1+1+1+2　　→　（３，１，０）

　　1+1+3　　　→　（２，０，１）

　　1+2+2　　　→　（１，２，０）

　　2+3　　　　→　（０，１，１）

ですから，ａ5＝５となります．

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

　ｎ＝５０の場合，

５０＝ｋ1＋２ｋ2＋３ｋ3≧３ｋ3→　０≦ｋ3≦５０／３＜１７

ｋ3は０から１６までの整数ですから，これによって場合分けすると

（ｋ3，ｋ1＋２ｋ2）＝（１６，２）→ｋ2＝０，１（２通り）

（ｋ3，ｋ1＋２ｋ2）＝（１５，５）→ｋ2＝０，１，２（３通り）

（ｋ3，ｋ1＋２ｋ2）＝（１４，８）→ｋ2＝０，１，２，３，４（５通り）

・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・

（ｋ3，ｋ1＋２ｋ2）＝（２，４４）→ｋ2＝０，１，２，・・・，２２（２３通り）

（ｋ3，ｋ1＋２ｋ2）＝（１，４７）→ｋ2＝０，１，２，・・・，２３（２４通り）

（ｋ3，ｋ1＋２ｋ2）＝（１，５０）→ｋ2＝０，１，２，・・・，２５（２６通り）

ｋ3が偶数のときと奇数のときで場合分けした方が良さそうであるが，総計２３４通りになる．

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

　このとき，母関数は

　ｆ（ｘ）＝Σａnｘ^n＝Σｘ^(k1+2k2+3k3)＝Σｘ^k1Σｘ^2k2Σｘ^3k3

＝１／（１−ｘ）・１／（１−ｘ^2）・１／（１−ｘ^3）

となります．

　　（１−ｘ）（１−ｘ^2）（１−ｘ^3）Σａnｘ^n＝１

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

　　ａn＝ａn-1＋ａn-2−ａn-4−ａn-5＋ａn-6

を得ることができます．

ａ0＝１，ａ1＝１，ａ2＝２，ａ3＝３，ａ4＝４，ａ5＝５，

ａ6＝７，ａ7＝８，ａ8＝１０，ａ9＝１２，ａ10＝１４，ａ11＝１６，　・・・，ａ50＝２３４，・・・

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