二元の分割数の母関数

何日か悩んで、やっと二元の分割数の母関数が分かった。そもそも分割数も母関数もよく分かっておらず、骨が折れた。数学的素養のある人には難しくないのかもしれないが・・・

   ( 1 + b      + b^2    + … )
 * ( 1 + b^2    + b^4    + … )
 * ( 1 + b^3    + b^6    + … )
   … 
 * ( 1 +    w   +    w^2 + … )
 * ( 1 +   bw   + b^2w^2 + … )
 * ( 1 + b^2w   + b^4w^2 + … )
 * ( 1 + b^3w   + b^6w^2 + … )
   … 
 * ( 1 +    w^2 +    w^4 + … )
 * ( 1 +   bw^2 + b^2w^4 + … )
 * ( 1 + b^2w^2 + b^4w^4 + … )
 * ( 1 + b^3w^2 + b^6w^4 + … )
   … 
 * ( 1 +    w^3 +    w^6 + … )
 * ( 1 +   bw^3 + b^2w^6 + … )
 * ( 1 + b^2w^3 + b^4w^6 + … )
 * ( 1 + b^3w^3 + b^6w^6 + … )
   … 
   … 

この多項式を計算して、bⁿw^m の係数を調べれば、n 個の 黒玉(b) と m 個の 白玉(w) を分割するパターン数が得られる。

項の数が無限だから計算できないように思えるかもしれないが（自分も母関数をいろいろ調べるまではそうだった）、必要な部分は限られているので、元の式と計算途中の式から、範囲外の項は除外していけば計算できる。

試しに黒玉、白玉、ともに 3個までに限定して手計算してみると、以下のようになる。

	1	b	b2	b3	w	bw	b2w	b3w	w2	bw2	b2w2	b3w2	w3	bw3	b2w3	b3w3
1+b+b2+b3	1	1	1	1
1+b2	1	1	2	2
1+b3	1	1	2	3
1+w+w2+w3	1	1	2	3	1	1	2	3	1	1	2	3	1	1	2	3
1+bw+b2w2+b3w3	1	1	2	3	1	2	3	5	1	2	4	6	1	2	4	7
1+b2w	1	1	2	3	1	2	4	6	1	2	5	8	1	2	5	9
1+b3w	1	1	2	3	1	2	4	7	1	2	5	9	1	2	5	10
1+w2	1	1	2	3	1	2	4	7	2	3	7	12	2	4	9	17
1+bw2	1	1	2	3	1	2	4	7	2	4	8	14	2	5	11	21
1+b2w2	1	1	2	3	1	2	4	7	2	4	9	15	2	5	12	23
1+b3w2	1	1	2	3	1	2	4	7	2	4	9	16	2	5	12	24
1+w3	1	1	2	3	1	2	4	7	2	4	9	16	3	6	14	27
1+bw3	1	1	2	3	1	2	4	7	2	4	9	16	3	7	15	29
1+b2w3	1	1	2	3	1	2	4	7	2	4	9	16	3	7	16	30
1+b3w3	1	1	2	3	1	2	4	7	2	4	9	16	3	7	16	31

例えば、黒玉3個、白玉1個は b³wの係数で7パターン、黒玉2個白玉2個ならb²w²の係数で9パターン、黒玉3個白玉3個ならb³w³の係数で31パターンとなり、手作業で調べた結果と一致する。

ここまで分かれば、任意の個数の黒玉白玉について、分割パターンの数を求めるプログラムを書くのはそう難しくない。Project Euler の Problem 181 がこれで解ける。