母関数                                   戻る

 私が「母関数」というものに初めて出会ったのは、高1の順列・組合せの計算のときだった
と思う。母関数は生成関数とも言われる。

 例えば、大小2個のさいころを投げて、目の和が8になる場合の数を求める場合、

  (大,小)=(2,6)、(3,5)、(4,4)、(5,3)、(6,2) の5通り

とすれば、特段問題はないが、次のように求めてもいいということを理解するには多少時間
を要した。

 2個のサイコロを投げるとき、目の和が8となる場合の数は、多項式

    (x+x2+x3+x4+x5+x62

を展開したときの、x8 の係数を調べればよい。これが母関数との出会いである。

 実際に、 (x+x2+x3+x4+x5+x62

     =x2+2x3+3x4+4x5+5x6+6x7+5x8+4x9+3x10+2x11+x12

 よって、求める場合の数は、5通りである。

 高1のときは、左右対称な係数を覚えるだけで、それ以上の進展はなかったように思う。

 しかし、「目の積」の問題で、n 個のサイコロを投げるとき、目の積が2・3・5 となる場

合の数が、(1+x+x2+y+xy+z)を展開したときの、x・y・z の係数に等しいというこ
とや、そのページでの at さんによる母関数の豊かな応用を目にすると、もう少し母関数のこ
とをまとめておく必要性を痛感した。

 母関数は、18世紀頃、ド・モアブルやスターリング、オイラーたちによって考案されたという。

例 2項定理 (1+x)3=1+3x+3x2+x3 における x の係数 3k からも分かるように
  x の係数は、異なる3個の文字から k 個取る場合の数に等しい。

 異なる3個の文字 a、b、c から文字を選ぶ場合、各文字について

   その文字を選ぶ場合 と その文字を選ばない場合

の2つの場合がある。

 そこで、各 a、b、c について、選ぶ場合は x 、選ばない場合は 1 として、文字 a には、多
項式 1+ax、文字 b には、多項式 1+bx、文字 c には、多項式 1+cx を対応させて考
える。

 換言すれば、文字 a を高々1度とる組合せを表す多項式が、1+ax ということである。

 よって、文字 a を高々2度とる組合せを表す多項式は、1+ax+a22 となる。

 このとき、

 (1+ax)(1+bx)(1+cx)=1+(a+b+c)x+(ab+bc+ca)x2+abcx3

となる。上式で、1、x、x2、x3 の係数を見ると、

 1:異なる3個の文字 a、b、c のどれも選ばない場合は、1通り

 x:異なる3個の文字 a、b、c から1個の文字を選ぶ場合は、 a、b、c の3通り

 x2:異なる3個の文字 a、b、c から2個の文字を選ぶ場合は、 ab、bc、ca の3通り

 x3:異なる3個の文字 a、b、c から3個の文字を選ぶ場合は、 abc の1通り

 異なる3個の文字 a、b、c からいくつかの文字を選ぶ場合の数の計算だけだったら、

a=b=c=1として、

 (1+x)(1+x)(1+x)=1+(1+1+1)x+(1+1+1)x2+1x3

すなわち、 (1+x)3=1+3x+3x2+x3 であったわけである。

 したがって、異なる3個の文字 a、b、c から文字を選ぶ場合の母関数は、

    (1+x)3=1+3x+3x2+x3

である。

 一般に、数列{a}に対して、形式的なべき級数

   a0+a1x+a22+a33+・・・+a+・・・

を、その数列の通常型母関数という。

例 3個の文字 a、a、b から文字を選ぶ場合の母関数は、

   (1+x+x2)(1+x)=1+2x+2x2+x3 である。

  これは、(1+ax+a22)(1+bx) と考えれば明らかだろう。

例 4個の文字 a、a、b、b から文字を選ぶ場合の母関数は、

   (1+x+x2)(1+x+x2)=1+2x+3x2+2x3+x4 である。

  これは、(1+ax+a22)(1+bx+b22) と考えれば明らかだろう。

 一般に、次が成り立つ。

 n 個のうち、m1、m2、・・・、m 個が同じものであるとき、n 個のものから重複を許
して r 個とる組合せの数は、次の多項式の x の係数に等しい。


 (1+x+x2+・・・+x1)(1+x+x2+・・・+x2)・・・(1+x+x2+・・・+x

 ただし、n=m1+m2+・・・+m とする。


例 5個の文字 a、a、a、b、b から重複を許して3個とる組合せの数を求めよ。

 求める場合の数は、 aaa、aab、abb の3通りである。

 この計算を母関数の考えを用いて行ってみよう。

 (1+x+x2+x3)(1+x+x2)=・・・+x3+・・・+x3+・・・+x3+・・・

より、x3 の係数は、1+1+1=3 なので、求める場合の数は、3通りである。

(証明) n 個のうち、

     a が m1個 、b が m2個 、・・・、c が m 個 (n=m1+m2+・・・+m

とする。このとき、k個の多項式

    1+ax+a22+・・・+a11

    1+bx+b22+・・・+b22

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

    1+cx+c22+・・・+c

の積を考え展開したとき、

  x の係数 : a、b、・・・、c の和

  x2 の係数 : a、b、・・・、c から重複を許して2個ずつの積

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

  x の係数 : a、b、・・・、c から重複を許して r 個ずつの積

である。 (証終)

 上記では、組合せの数が母関数から得られることを見たが、順列の数も母関数から得ら
れる。

 (1+ax)(1+bx)(1+cx)=1+(a+b+c)x+(ab+bc+ca)x2+abcx3

において、

 異なる3個の文字 a、b、c のどれも選ばない場合は、1通り

 異なる3個の文字 a、b、c から1個とる順列の数は、 a、b、c の3通り

 異なる3個の文字 a、b、c から2個とる順列の数は、

   ab、ba、bc、cb、ca、ac の6通り

  そこで、 ab+ba=2ab、 bc+cb=2bc、 ca+ac=2ca と考えれば、

  x2 の項は、(ab+bc+ca)x2=2(ab+bc+ca)x2/2! とも変形できる。

 異なる3個の文字 a、b、c から3個とる順列の数は、

  abc、acb、bac、bca、cab、cba の6通り

  そこで、 abc+acb+bac+bca+cab+cba=6abc と考えれば、

  x3 の項は、abcx3=6abcx3/3! とも変形できる。

 すなわち、

    (1+ax)(1+bx)(1+cx)

   =1+(a+b+c)x+(ab+bc+ca)x2+abcx3

   =1+(a+b+c)x/1!+2(ab+bc+ca)x2/2!+6abcx3/3!

と考えることができる。ここで、 a=b=c=1 とすると、

  (1+x)3=1+3x/1!+6x2/2!+6x3/3!

となり、xr/r!の係数が、異なる3個のものより r 個とる順列の数に等しい。

一般に、

  (1+x)

 =01x+22+・・・++・・・+

 =01x/1!+22/2!+・・・+/r!+・・・+/n!


が成り立つ。

 一般に、数列{a}に対して、形式的なべき級数

   a0+a1x/1!+a22/2!+a33/3!+・・・+a/n!+・・・

を、その数列の指数型母関数という。

例 4個の文字 a、a、b、b から文字をいくつか選んで並べる場合の母関数は、

   (1+ax/1!+a22/2!)(1+bx/1!+b22/2!)

 =1+(a+b)x/1!+(a2/2!+ab/1!1!+b2/2!)x2

                   +(ab2/1!2!+a2b/1!2!)x3+(a22/2!2!)x4

 =1+(a+b)x/1!+(a2+2ab+b2)x2/2!+(3ab2+3a2b)x3/3!+6a224/4!

 である。

 このとき、例えば、4個の文字 a、a、b、b から3個とって並べる順列の数は、

   aab、aba、baa、abb、bab、bba の6通り

であるが、母関数のx3/3!の係数 3ab2+3a2b から

   aab+aba+baa+abb+bab+bba の6項

を意味するので、求める場合の数は、6通りであることが分かる。

 一般に、次が成り立つ。

 n 個のうち、m1、m2、・・・、m 個が同じものであるとき、n 個のものから r 個とる
順列の数は、次の多項式の x の係数に r!を掛けたものに等しい。

 

 ただし、n=m1+m2+・・・+m で、0≦r≦n とする。


例 5個の文字 a、a、a、b、b から3個とる順列の数を求めよ。

  a 3個のとき、 1通り
  a 2個、b 1個のとき、 3通り
  a 1個、b 2個のとき、 3通り   以上から、求める場合の数は、 1+3+3=7(通り)

 この計算を母関数の考えを用いて行ってみよう。

 (1+x+x2/2+x3/6)(1+x+x2/2)=・・・+x3/2+・・・+x3/2+・・・+x3/6+・・・

より、x3 の係数は、 1/2+1/2+1/6=7/6 なので、3!=6 を掛けて、

 求める場合の数は、 (7/6)×6=7(通り)

(証明) n 個のうち、

     a が m1個 、b が m2個 、・・・、c が m 個 (n=m1+m2+・・・+m

とする。このとき、k個の多項式

    1+ax+a22/2!+・・・+a11/m1

    1+bx+b22/2!+・・・+b22/m2

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

    1+cx+c22/2!+・・・+c/m

の積を考え展開したとき、

    (a11/r1!)(b22/r2!)・・・(c/r!)

  ={1/(r1!r2!・・・r!)}a12・・・c (r=r1+r2+・・・+r

は、r個のうち、a を r1 個、b を r2 個、・・・、c を r 個とった1つの組合せに対応している。

 このときの係数 1/(r1!r2!・・・r!) (r=r1+r2+・・・+r) の和に r!を掛けたも

のが求める場合の数を与える。 (証終)

 母関数というと馴染みがないように感じるが、パスカルの三角形を考えているとき、母関
数の概念を無意識に使っていたことに気づかされる。

また、パスカルの三角形を縦方向に見ると、母関数 (1−x)-n を与えているという事実は
面白い。

 F(x)=(1−x)-n とおくと、 F(0)=1 で、

   F’(x)=n(1−x)-n-1 より、 F’(0)=n

   F”(x)=n(n+1)(1−x)-n-2 より、 F”(0)=n(n+1)

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

   F(k)(x)=n(n+1)・・・(n+k−1)(1−x)-n-k より、

      F(k)(0)=n(n+1)・・・(n+k−1)

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

 以上から、(1−x)-n を x=0 のまわりでマクローリン展開すると、

 (1−x)-n=1+nx+{n(n+1)/2}x2+・・・+{n(n+1)・・・(n+k−1)/k!}x+・・・

  因みに、パスカルの三角形から

   (1−x)-11・x+・x2+・・・+・x+・・・

   (1−x)-2・x+・x2+・・・+(k+1)・x+・・・

   (1−x)-3・x+・x2+・・・+{(k+1)(k+2)/2}・x+・・・

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

 となり、マクローリン展開の結果と一致する。

(コメント) この関係は面白いですね!ある意味で、裏技です...。


 さらに、F(x)=(1−x)-n として、

   G(x)=F1(x)+x22(x)+x43(x)+x64(x)+x85(x)+・・・

とおくと、フィボナッチ数列の母関数になることが知られている。

 実際に、 G(x)=1+x+x2+x3+x4+x5+・・・
               +x2+2x3+3x4+4x5+・・・・
                       +x4+3x5+・・・・
                               ・・・・・・
           =1+x+2x2+3x3+5x4+8x5+・・・

     から、フィボナッチ数列 1,1,2,3,5,8,・・・ が得られる。

 ここで、G(x)は初項が (1−x)-1 で公比 x2(1−x)-1 の無限等比級数であるので、

   G(x)=(1−x)-1/{1−x2(1−x)-1}=1/(1−x−x2

となる。ただし、収束条件は、 −1<x2(1−x)-1<1 すなわち、|2x+1|<
(形式的なべき級数なので、収束条件を考えても意味がないかな?)


 フィボナッチ数列 {a}は、漸化式

    a0=1、a1=1、an+2=an+1+a (n=0、1、2、・・・)

により定義される。漸化式の解法にも母関数の考えは用いられる。

 フィボナッチ数列{a}に対して、形式的なべき級数

    F(x)=a0+a1x+a22+a33+・・・+a+・・・

を考える。このとき、

  −xF(x)= −a0x−a12−a23−a34−・・・・−an+1−・・・

  −x2F(x)=    −a02−a13−a24−a35−・・・・−an+2−・・・

より、 (1−x−x2)F(x)=1 なので、 F(x)=1/(1−x−x2

  これは上記で得られた母関数 G(x) と一致している。


 ここで、1−x−x2=0 即ち x2+x−1=0 の2つの解を α、β(α>β) とすると、

    α=(−1+)/2 、β=(−1−)/2  より、 α−β=

 さらに、 1/α=(1+)/2 、 1/β=(1−)/2

 このとき、 F(x)={1/(α−x)−1/(β−x)}/(α−β)

           ={1/{α(1−x/α)}−1/{β(1−x/β)}/(α−β)

           ={(1/α)Σ(x/α)−(1/β)Σ(x/β))}/(α−β)

 x の係数に着目して、

   a={(1/α)(1/α)−(1/β)(1/β)}/(α−β)

     ={(1/α)n+1−(1/β)n+1}/(α−β)

     =[{(1+)/2}n+1−{(1−)/2}n+1]/  (n=0、1、2、・・・)

 これは、フィボナッチ数列の一般項で、「ビネの公式」と言われる。


 当HP読者のK.S.さんから上記の話題について、メールを頂いた。
                                     (平成23年11月11日付け)

 α=(1+)/2 、β=(1−)/2 とおくと、 α+β=1、αβ=−1 である。

 このとき、 x/(1−x−x2)=(1/){1/(1−αx)−1/(1−βx)}

                 =(1/){1+αx+α22+・・・+α+・・・

                           −1−βx−β22−・・・−β−・・・}

                 =(1/){(1−1)+(α−β)x+(α2−β2)x2+・・・}

 ここで、a=[{(1+)/2}n+1−{(1−)/2}n+1]/  (n=0、1、2、・・・)

なので、

   x/(1−x−x2)=(1/){a0x+a12+・・・+an+1+・・・}

という形のフィボナッチ数列の母関数が得られる。

(コメント) 上記の母関数の両辺を x で割ると、当初得られた母関数が得られる。どちらの
      導入がより易しいのだろう?


 母関数を利用した漸化式の解法を見ると、次の問題にも使いたくなるような...気分!

問 題  次の4項間漸化式を解け。

    a0=1、a1=0、、a2=−5、 an+3−4an+2+5an+1−2a=0 (n≧0)

(特性方程式を利用する解)  x3−4x2+5x−2=0 は因数分解されて、

    (x−1)2(x−2)=0 より、 解は x=1、2

  このとき、 x3−(α+β+γ)x2+(αβ+βγ+γα)x−αβγ=0 は、

       x3−(β+γ)x2+βγx=α{x2−(β+γ)x+βγ}

 と変形されるので、 

  α=1、β=1、γ=2 のとき、

      an+3−3an+2+2an+1=an+2−3an+1+2a=a2−3a1+2a0=−3

  α=2、β=1、γ=1 のとき、

      an+3−2an+2+an+1=2(an+2−2an+1+a

   ここで、 a2−2a1+a0=−4 なので、 an+2−2an+1+a=−4・2=−2n+2

 よって、連立方程式 an+2−3an+1+2a=−3 、an+2−2an+1+a=−2n+2 から、

    an+1−a=3−2n+2

 したがって、n≧1のとき、

    a=a0+Σ[k=0〜n-1](3−2k+2)=1+3n−4(2−1)=5+3n−2n+2

 この式は、n=0 のときも成り立つ。

  以上から、 a=5+3n−2n+2 (n≧0)  (終)

(母関数を利用する解)  数列{a}に対して、形式的なべき級数

     F(x)=a0+a1x+a22+a33+・・・+a+・・・

を考える。このとき、

 −4xF(x)= −4a0x−4a12−4a23−4a34−・・・−4an+1−・・・

 5x2F(x)=        5a02+5a13+5a24+・・・+5an+2+・・・

 −2x3F(x)=           −2a03−2a14−・・・−2an+3−・・・

より、   (1−4x+5x2−2x3)F(x)=1−4x  なので、

    F(x)=(1−4x)/(1−4x+5x2−2x3)=(1−4x)/{(1−x)2(1−2x)}

 部分分数に分解して、

   F(x)=2/(1−x)+3/(1−x)2−4/(1−2x)

      =2Σx+3(Σx2−4Σ(2x)

      =2Σx+3Σ(n+1)x−4Σ2

 x の係数に着目して、

   a=2+3(n+1)−4・2=5+3n−2n+2  (終)

(コメント) (特性方程式を利用する解)では非常に技巧的な趣きがあるが、(母関数を利用
      する解)の方では、自然な流れというものを感じます。

 上記の解における手法を用いると、次の漸化式も容易に解けるだろう。

問 題  次の n+1 項間漸化式を解け。

    a0=1 、a=a0・an-1+a1・an-2+a2・an-3+・・・+an-1・a0  (n≧1)

(解) 数列{a}に対して、形式的なべき級数

     F(x)=a0+a1x+a22+a33+・・・+a+・・・

を考える。このとき、

   xF(x)2=   a02x+(a0・a1+a1・a0)x2+(a0・a2+a1・a1+a2・a0)x3+・・・

より、 F(x)−xF(x)2=1 すなわち、 xF(x)2−F(x)+1=0 となる。

 F(0)=1 なので、
              

 (解の公式で、複号のうち、「+」とすると、x→0 のとき、F(x)は発散してしまう!)

 2項級数より、
          

なので、F(x)の x の係数は、 −1/2n+1(−4)n+1/2 である。

 ここで、

 1/2n+1=(1/2)(−1/2)(−3/2)・・・(−(2n−1)/2)/(n+1)!

      =(−1)・1・3・5・・・・・(2n−1)/{2n+1・(n+1)!}

      =(−1)・1・2・3・・・・・・(2n−1)・2n/{22n+1・n!(n+1)!}

      =(−1)・(2n)!/{22n+1・n!(n+1)!}

      =(−1)2n/{22n+1・(n+1)}

なので、

 −1/2n+1(−4)n+1/2=−[(−1)2n/{22n+1・(n+1)}]・(−1)n+1・22n+1

                =2n/(n+1)

 したがって、 a2n/(n+1) となる。(→ 参考:「カタラン数」)

(コメント) この漸化式を、母関数を用いないで解くなんて想像できない!


(追記) 「母関数の有効利用」と題して、当HPがいつもお世話になっているHN「GAI」さん
    からの投稿です。(平成28年10月20日付け)

 ここ何日かの計算を行っていて、次のようなテーマを一気に解決できる母関数を作れるこ
とに気づきました。

 例えば、10個の奇素数の集合W={3,5,7,11,13,17,19,23,29,31}があるとき、

(1) Wから相異なるk個の積(k=1,2,3,・・・,10)の和s1[k]を知りたいなら

 F1(x)=(1+3*x)(1+5*x)(1+7*x)・・・・・(1+31*x) を展開して、

 F1(x) = 1 + 158*x + 10805*x^2 + 419800*x^3 + 10224018*x^4 + 162393924*x^5
     + 1695059330*x^6 + 11412878200*x^7 + 47114595181*x^8 + 106868339918*x^9
     + 100280245065*x^10

より、s1[k]=x^k の項の係数

(2) Wから同じものを含めたk個の積(3^k,7^(k-3)*17^2*23,などを含む。)の和s2[k]は

 F2(x)=1/((1-3*x)(1-5*x)(1-7*x)・・・・・(1-31*x)) を級数展開して、

 F2(x) = 1+ 158*x + 14159*x^2 + 949732*x^3 + 53174043*x^4 + 2630591814*x^5
     + 118986775397*x^6 + 5031681224656*x^7 + 202010077418806*x^8
     + 7785253969285508*x^9 + 290375919746318634*x^10
     + 10546897376137664232*x^11 + O(x^12)

より、s2[k]=x^k の項の係数


(3) Wの各要素のk乗の和S[k](=3^k+5^k+7^k+・・・・・+31^k)(k=1,2,3,・・・,10)を知りたいなら、

  F3[x]=(x-3)(x-5)(x-7)・・・・・(x-31) を準備して、
 (x^10*x*F3[x])を微分したものをF3[x]で割り、その商を求める。(kは最大で10までなので)

<これをPARIのソフトで実行したもの>

 gp>F3(x)=prod(k=2,11,x-prime(k))
 gp>divrem(deriv(x^10*x*F3(x)),F3(x))[1]を実行して

 = 21*x^10 + 158*x^9 + 3354*x^8 + 82142*x^7 + 2170794*x^6 + 60025118*x^5
  + 1708278714*x^4 + 49554665822*x^3 + 1456444007754*x^2 + 43202201145758*x
  + 1290073179869274

より、S[k]=x^(10-k)の項の係数(S[10]は定数項に対応する。)

(確かめ) gp>for(k=1,10,print("S[",k,"]=",sum(i=2,11,prime(i)^k)))
S[1]=158
S[2]=3354
S[3]=82142
S[4]=2170794
S[5]=60025118
S[6]=1708278714
S[7]=49554665822
S[8]=1456444007754
S[9]=43202201145758
S[10]=1290073179869274



    以下、工事中