4.母関数の応用~二項変換とその逆変換

前へ 戻る

 二項変換と逆変換

ここまで母関数を一般項の導出に利用する方法を扱ってきた。この頁では数列に対する「二項変換」という操作を取り上げてみる。二項変換の内容は英語圏の一般的な解釈に準拠する。

 
《 交代二項変換(alternating binomial transform)》

 

数列{an}に対して以下の操作により新たな数列{bn}を構成する方法を「交代二項変換」という。(2.1.0)bn=k=0n(1)knCkakこのとき、数列{an}の通常型母関数をf(x)とすれば、数列{bn}の通常型母関数F(x)(2.1.1)F(x)=11xf(x1x)で与えられる。また、数列{an}の指数型母関数をg(x)とすれば、数列{bn}の指数型母関数G(x)(2.1.2)G(x)=exg(x)で与えられる。

これに対して(1)kが無いものは「二項変換の逆変換」、若しくは「逆二項変換」(inverse binomial transform)などと呼ばれるが、書籍や文献によってはいずれの変換も単に二項変換としか書いていないものもあるので注意が必要である。

不要な混乱を避けるため、この頁では前者の変換を「交代二項変換」、後者の変換を「単純二項変換」と呼称することにする。

 
《 単純二項変換(simple binomial transform)》

 

数列{an}に対して以下の操作により新たな数列{bn}を構成する方法を「単純二項変換」という。(2.2.0)bn=k=0nnCkakこのとき、数列{an}の通常型母関数をf(x)とすれば、数列{bn}の通常型母関数F(x)(2.2.1)F(x)=11xf(x1x)で与えられる。また、数列{an}の指数型母関数をg(x)とすれば、数列{bn}の指数型母関数G(x)(2.2.2)G(x)=exg(x)で与えられる。

但し、ここで定義している呼称は一般的なものではないことに注意されたい。

 

 二項変換の合成と母関数

(難解に感じたら例題編まで読み飛ばしても構いません)

数学的な洞察眼が優れている人は、これを一見して以下の関係に気付けるかもしれない。交代二項変換に対して、次の関係が成り立つ。

(2.3.0)bn=k=0n(1)knCkakan=k=0n(1)knCkbk

これは母関数を考えれば直ちに了解されることだろう。例えば通常型母関数の場合だと、F(x)=11xf(x1x) であるから、

     11xF(x1x)=11x11+x1xf(x1x1+x1x)=11x+xf(x1x+x)(2.3.1)=f(x)

となり、母関数が元に戻っている。また指数型母関数の場合だと、G(x)=exg(x) であるから、

exG(x)=exexg((x))(2.3.3)=g(x)

となり、こちらでも母関数が元に戻っている。これは交代二項変換が「自己逆性」(self-inverse)を有する写像、即ち「対合」(involution)であることを意味している。式化すると以下のようになる。

an=k=0n(1)knCkj=0k(1)jkCjaj=j=0n(1)jajk=jn(1)knCkkCj=j=0n(1)jajk=jn(1)knCjnjCkj=j=0nnCjajk=jn(1)k+jnjCkj=j=0nnCjajk=0nj(1)knjCk=nCnan(2.3.4)=an

なお、ここで和の交代性、及びnCkkCj=nCjnjCkjという変換公式を利用している。


単純二項変換はこのような性質を有さないが、これも母関数により容易に了解される。しかし単純二項変換に交代二項変換を組み合わせると面白い性質が見えてくる。

母関数f(x)に単純二項変換を施すとF(x)=11xf(x1x)となる。これに更に交代二項変換を施してみると、

     11xF(x1x)=11x11+x1xf(x1x1+x1x)=11x+xf(x1x+x)(2.3.5)=f(x)

となる。これは式化すると以下のようになる。

(1)nan=k=0n(1)knCkj=0kkCjaj=j=0najk=jn(1)knCkkCj=j=0najk=jn(1)knCjnjCkj=j=0nnCjajk=jn(1)knjCkj=j=0nnCjajk=0nj(1)kjnjCk=nCnan(1)n(2.3.6)=(1)nan

ここで (1)n=(1)n として計算している。


逆に、f(x)に交代二項変換を施してから単純二項変換を施すと、次のようになる。

     11xF(x1x)=11x11x1xf(x1x1x1x)=11xxf(x1xx)(2.3.7)=112xf(x12x)

また、f(x)に単純二項変換を2回施すと、次のようになる。     11xF(x1x)=11x11x1xf(x1x1x1x)=11xxf(x1xx)(2.3.8)=112xf(x12x)

これらはそれぞれ以下のような母関数となっている(大きな括弧の中が被生成数列である)。

112xf(x12x)=n=0((1)n2nk=0nnCkak)xn

112xF(x12x)=n=0(12nk=0nnCkak)xn

 

 二項変換に関する例題

ここまで、交代二項変換、単純二項変換という2つの数学的操作を概観してきたが、いまいち内容が分かりにくいと思われるので、簡単な例題を幾つか解いてみよう。


 《例題1》

an=1 (n=0,1,2,) で定まる数列{an}に対して、交代二項変換を施してできる数列を{bn}、単純二項変換を施してできる数列を{bn}とする。数列{bn}及び{bn}求めよ。

 《解答例》

anの母関数f(x)f(x)=11x であるから、数列{bn}の母関数F(x)     F(x)=11xf(x1x)=11x11+x1x=1となる。故に数列{bn}b0=1bn=0 (n=1,2,3,)である。

また、数列{bn}の母関数F(x)     F(x)=11xf(x1x)=11x11x1x=112xとなる。故に数列{bn}bn=2n (n=0,1,2,)である。


これらの結果が正しいことを示そう。証明には二項係数の母関数(1+x)nを用いる。

bn=k=0n(1)knCk1 であるから、an=1 (n=0,1,2,) のとき数列{bn}(1+x)nx=1 を代入して得られる。よって bn={1   (n=0)0   (n1) となるから母関数により正しく求められていることが分かる。

また、bn=k=0nnCk1 であるから、an=1 (n=0,1,2,) のとき数列{bn}(1+x)nx=1 を代入して得られる。よって bn=(1+1)n=2n (n=0,1,2,) となるから、こちらも母関数により正しく求められている。

 


 《例題2》

an=n (n=0,1,2,) で定まる数列{an}に対して、交代二項変換を施してできる数列を{bn}、単純二項変換を施してできる数列を{bn}とする。数列{bn}及び{bn}求めよ。

 《解答例》

anの母関数f(x)f(x)=x(1x)2 であるから、数列{bn}の母関数F(x)     F(x)=11xf(x1x)=11xx1x(1+x1x)2=x(1x+x)2=xとなる。故に数列{bn}b0=0b1=1bn=0 (n=2,3,4,)である。

また、数列{bn}の母関数F(x)     F(x)=11xf(x1x)=11xx1x(1x1x)2=x(12x)2となる。故に数列{bn}は第2節の(1.9)式を用いてbn=nC12n1=n2n1 (n=0,1,2,)である。

(1.9)式とは次の公式である。1(1x)m+1=n=0n+mCmxn

これらの結果が正しいことを示すための準備として、以下の関係式を理解しよう。(1+x)n=1+nC1x+nC2x2+nC3x3+     ++nCn2xn2+nCn1xn1+nCnxn=k=0nnCkxkより、     ddx(1+x)n=n(1+x)n1=nC1+2nC2x+3nC3x2+     ++(n2)nCn2xn3+(n1)nCn1xn2+nnCnxn1=k=1nknCkxk1となるから、上記の青字部分について両辺にxを乗じて、nx(1+x)n1=k=0nknCkxkを得る(この左辺が数列{knCk}の母関数である)。

さて、いま bn=k=0n(1)knCkk であるから、an=n (n=0,1,2,) のとき数列{bn}nx(1+x)n1x=1 を代入して得られる。よって b0=0b1=1bn=0 (n=2,3,4,) となり、正しく求められている。

また、bn=k=0nnCkk であるから、an=n (n=0,1,2,) のとき数列{bn}nx(1+x)n1x=1 を代入して得られる。よって bn=n1(1+1)n1=n2n1 (n=0,1,2,) となり、こちらも正しく求められている。

 

 練習課題

以下、学習のための練習課題として幾つかの問題を提示しておこう。


《練習課題1》

Sn=nC0+3nC1+5nCk++(2n+1)nCn(n+1)2n に等しいことを母関数から確かめよ。

» 解き方はこちら

 《解答例》

Snは数列 an=2n+1 に単純二項変換を施すと得られる。数列 an=2n+1 の母関数f(x)f(x)=2x(1x)2+11x=x+1(1x)2であるからSnの母関数F(x)     F(x)=11xf(x1x)=11xx1x+1(1x1x)2=1(12x)2となる。故に数列{Sn}Sn=n+1C12n=(n+1)2n (n=0,1,2,)である。(※n次の係数の計算には(1.9)式を用いた)

» 閉じる

 


《練習課題2》

n番目のモンモール数anの単純二項変換が階乗数n!になることを母関数から確かめよ。なお、モンモール数の指数型母関数g(x)g(x)=ex1xで与えられる。

» 解き方はこちら

 《解答例》

exg(x)=exex1x=11xである。階乗数n!の指数型母関数h(x)h(x)=11x であるから、exg(x)=h(x) となり確かにn番目のモンモール数anの単純二項変換が階乗数n!になっている。

(参考:第2回「#旧帝戦数学部門」を解いてみた

» 閉じる

 


《練習課題3》

An=k=0nnCk2nの式で表せ。

» 解き方はこちら

 《解答例》

二項係数nCkの母関数f(x)f(x)=(1+x)nである。これに対して単純二項変換を施すと、

     11x(1+x1x)n=1(1x)n+1=k=0n+kCkxk   ((1.9))

となる。よってxnの係数は 2nCn となるから、An=k=0nnCk2=2nCnである。

» 閉じる

 


《練習課題4》

Sn=02nC0+12nC1+22nC2++n2nCnn(n+1)2n2 に等しいことを母関数から確かめよ。

» 解き方はこちら

 《解答例》

平方数k2の母関数f(x)f(x)=x(1+x)(1x)3である。これに対して単純二項変換を施すと、

     11x11x(1+x1x)(1x1x)3=x(12x)3=xn=0n+2C22nxn   ((1.9))=n=0n+2C22nxn+1

となる。故にxnの係数はn+1C22n1=n(n+1)22n1=n(n+1)2n2となるから、Sn=n(n+1)2n2である。

» 閉じる

 


《発展例題》

Bn=k=0n(1)knCk2 (n=0,1,2,)nの式で表せ。

» 答えはこちら

Bn={(1)m2mCm(for n=2m)0(for n=2m+1)

但しm0以上の整数とする。

» 閉じる

 


前へ 戻る