TETRA’s MATH

カタラン数の母関数と一般項

 カタラン数の母関数の閉じた式は次のような形になることがわかりました。

  

 この式をべき級数展開したいという単純な希望があったとする()と、まずやりたくなるのはx=0を代入することですが、分母が0になってしまうのでできません。そこで、両辺に2xをかけて分母をはらってみます。

  

 この形にx=0を代入すると、左辺は0、右辺は+ならば2で、−ならば0です。だから−なのだ……と結論するのは乱暴だとは思いますが、少なくとも+で考えるのは無理があります。(ミルカさんは「不毛」という言葉を使っていました。なるほど、不毛といえばいいのか)

 というわけで、カタラン数の母関数の閉じた式を−のほうで考えていくことにします。

  

 このままで扱うのは大変なので、ルートの部分をひとつの関数として捉え、その関数をべき級数展開したときの係数の数列を<Kn>とします。

  

 つまり、K(x)=√(1−4x)とすると、カタラン数の母関数の閉じた式は次のように表せることになります。

  

 分母をはらって、

  

 具体的に級数の形で書いてみると、



 左辺の2xをC(x)のそれぞれの項にかけて、右辺のかっこをはずすと



 左辺と右辺で係数比較をします。



   数の項   0=1−K0
   xの項    2C0=−K1
   x^2の項   2C1=−K2
   x^3の項   2C2=−K3
       ・
       ・
       ・

 なるほど〜〜 

 ということは、CnはKnで表せるのだ!

  

 したがって、Knを求めれば、それをもとにCnも求まることがわかりました。

 となると、あとは√(1−4x)をべき級数展開して、係数Knをnで表せばよいことになります。べき級数展開といえばテイラー展開()。√(1−4x)=(1−4x)^(1/2)なので、微分はそれほど大変そうではありませんが、ある程度の目的意識をもたないと一般項まではたどりつけないなぁという感触があります。

 ではまず、K(x)を微分していきます。

  

 ピンクの−2については、あとで Cn=−1/2Kn+1に代入したときに−1/2を消すために、残しておきます。

 緑の部分はx=0を代入したときに1になります。

 となると、青い下線部分をどうするか、というのが考えどころになりそうです。これがうまいことまとまるからほんとに不思議。

  

 テイラー展開()したときの係数の分母にはn!があるので、Kn+1はどうなるかというと、

  

 これを係数比較で求めた()Cn=−1/2Kn+1という関係式に代入すると、

  

 というわけで、ミルカさんの求めた一般項()と一致しました。

 うーん、話ができすぎているっ

 こうなってほしいという想いのあまり、どこかで計算のズルをしていないだろうか私…



〔2018年3月25日追記〕

 分けて書いていた記事をひとつにまとめ、整理しました。
読書記録(ガ1) | permalink

カタラン数の一般項を求める場面の見所

 結城浩『数学ガール』においては、母関数の閉じた式を「僕」がつくり、それがミルカさんの手によって一般項へとつながっていきます。だけど、ミルカさん自身は別の方法ですでに一般項を求めていました。漸化式からもっていくという方針を途中で変更し、最短経路の問題に帰着させた結果、次のようなシンプルな式を得たのです。

   

 かっこの中の縦に並んだ2nとnの意味は、「2n個のものからn個のものを選ぶ組み合わせの数」つまり 2nCn と同じなのですが、何しろいまは数列の名前にカタラン数の頭文字のCを採用しており、これにコンビネーションのCが混ざると紛らわしくてしょうがないので、かっこの表記方法をとることにします。

 なお、最短経路に対応させる考え方は、「カタラン数」を扱っているWebページの多くに載っているのではないかと思います。面白い話ではありますが、ここでは詳しい説明は割愛して、先に進みます。

 さて、一般項を求めるだけならば、母関数を経由せずに最短経路に帰着させて求めたほうが、考え方もわかりやすいし、見た目もすっきりしています。でも、母関数から苦心して一般項を求めると、最短経路に対応させるのとは違う感動があります。

 私が面白いと思ったのは、最短経路に帰着させて解いたときの組み合わせの階乗の計算と、「母関数の閉じた式→一般項」のプロセスで出てくる微分の計算(次数が階段のように降りていくこと)がつながるところです。

 微分って連続量を扱う作業の代表のような印象があるけれど、次数が階段のように降りていくというのはあらためて考えると不思議です。

 なお、『数学ガール』では第6章で「下降冪階乗」というものが出てきていて、これを使うと何かと便利なのですが、TETRA'S MATH では下降冪階乗の表記を使わずに突っ切ります。

(つづく)
読書記録(ガ1) | permalink

カタラン数の母関数

 カタラン数の第(n+1)項の形がわかりました。





 次は、カタラン数の母関数を考えます。



 ,留κ佞鬚澆討澆襪函▲タラン数の積で構成されていることがわかります。そこで、カタラン数の積をつくるべく、△領省佞2乗してみます。




 この計算によって、x^nの係数がどうなるのかを考えたいのですが、例としてx^5の係数に注目すると……



 x^5の係数はC6と同じになってくれます。ありがとう〜〜



 同様に、x^4の係数はC5と同じになってくれるし、x^6の係数はC7と同じになってくれます。つまり、x^nの係数はCn+1になります。

 さらに、数の項はC0×C0=1×1=1なので、は次のように書き換えることができます。




 Cの添え字とxの次数が1つずつずれているので、い領省佞xをかけてそろえると……




 ァ櫚,魴彁擦垢襪函帖



 ΔC(x)についての2次方程式とみなせば、解の公式によりC(x)がxの式で表されます。



って、なんだかあたりまえのように書いてきましたが、どうしてこんなにきれいにまとまるのだろう!? 

(つづく)
読書記録(ガ1) | permalink

カタラン数の漸化式

 さて、カタラン数のイメージがつかめたところで、今度はカタラン数のそれぞれの項の間にどんな関係があるかを考えます。

 たとえば、最大の数値が8の9個のねんど玉があったとします。

   

 これを隣り合う2個ずつをくっつけていって、最終的に1個のねんど玉にするわけですが、最後に1個にまとまる直前に、2つのねんど玉ができているはずです。たとえば、青のねんど玉にする一歩手前で、0〜4の黄色のねんど玉と5〜8の緑のねんど玉ができていたとします。

   

 上の図では、黄色のねんど玉がどのようなプロセスでできたかはわからないけれど、そのプロセスは0〜4の5個のねんど玉を1つにまとめるプロセスの中に含まれています。なので、黄色のねんど玉ができるまでのくっつけ方はC4通りあるはずです。同様に、5〜8の緑のねんど玉ができるまでのプロセスはC3通り。なので、最後で(5個)と(4個)のねんどをくっつけるようなくっつけ方は、全部で(C4×C3)通りとなります。

 これとは別のくっつけ方を考えてみます。

   

 今度は、最終的に(3個)と(6個)になるようなくっつけ方です。黄色の(3個)になるまでC2通り、緑の(6個)になるまでC5通りなので、全部で(C2×C5)通りとなります。Cnのnの値がねんど玉の個数より1小さくなっていることに注意しながら考えていきます。

 すべての場合の数をまとめると

 (1個)と(8個)になる場合 → C0×C7 通り
 (2個)と(7個)になる場合 → C1×C6 通り
 (3個)と(6個)になる場合 → C2×C5 通り
 (4個)と(5個)になる場合 → C3×C4 通り
 (5個)と(4個)になる場合 → C4×C3 通り
 (6個)と(3個)になる場合 → C5×C2 通り
 (7個)と(2個)になる場合 → C6×C1 通り
 (8個)と(1個)になる場合 → C7×C0 通り

よって、



が成り立ちます。右辺をみてみると、すべてのCCにおいて、○+●=7=8−1 が成り立っています。

 なお、「隣り合うねんど玉2個をくっつけて最終的に1個にする」という考え方だと、C0…つまり最初からねんど玉1個の場合をどう考えればよいのか?という疑問が残りますが、上の式ではC0=1と考えることになるので、C0=1と考えていいことにします(なぜこう考えてよいのか、考えてよいのかどうか厳密な意味はわかりませんが、とりあえずここではそういうことにします)。

 というわけで、カタラン数の漸化式が求まりました。

   

 いきなりシグマですみません。例のごとく何かと雑なことになっていますが、結城浩『数学ガール』では丁寧かつきちんと記述されています。

(つづく)
読書記録(ガ1) | permalink

カタラン数のねんど玉

 フィボナッチ数からはなれて、今度はカタラン数です。

 結城浩『数学ガール』の「第7章 コンボリューション」では、カタラン数が扱われています。(ほぼ同じ内容を、Web上でも読むことができます。>ミルカさんとコンボリューション

 この第7章は、他の章に比べて冒頭部分がちょっとわかりにくいかな…という印象をもちました。「僕」もつっこんでいるように、村木先生の問題の出し方がすっきりしていないのです。でも、あとのことを考えると、適切な問題設定かもしれません。

 カタラン数の問題の出し方にはいろいろなものがあるようですが、『数学ガール』ではかっこのつけかたの問題として出てきます。たとえば 

 0+1+2+3=(0+(1+(2+3)))
         =(0+((1+2)+3))
         =((0+1)+(2+3))
         =((0+(1+2))+3)
         =(((0+1)+2)+3))
           3なら5通り(C3=5)。

というふうに。私はかっこをつけることを「ねんど玉をくっつける」イメージで考えました。

   

 0、1、2、3、4と書かれたねんど玉があるとします。まず0と1をくっつけて赤いねんど玉にします。次に、赤と2をくっつけて黄色のねんど玉にします。さらに、3と4をくっつけて緑のねんど玉にしたあと、最後に黄色と緑のねんど玉をあわせて青いねんど玉にします。

   

 別のくっつけかたを考えてみます。最初に1と2をくっつけて赤いねんど玉にします。次に、3と4をくっつけて黄色のねんど玉にします。さらに、赤と黄色をくっつけて緑のねんど玉にしたあと、最後に0と緑のねんど玉をくっつけて青いねんど玉にします。

   

 この場合、3と4の黄色のねんど玉を最初につくる方法もありますが、できあがった形が同じであれば1通りとして考えます。

 というようなねんど玉のくっつけかた(かっこのつけかた)が何通りあるかというと、5個のねんど玉(最大の数字が4)の場合は14通りとなります。(C4=14)

(つづく)
読書記録(ガ1) | permalink

テイラー展開と微分

 いま私には、ある関数f(x)をべき級数の形で表したい、というシンプルな希望があります。それはつまり、



のa0、a1、a2、a3、a4、a5、…を求めたい、と言い換えることができます。

 そこで、まずはこの式にx=0を代入してみます。そうすると、xが関わる式は全部消えるので、f(0)=a0であることがわかります。



 なるほど、xがついていない定数項はx=0を代入したときに右辺に残ってくれる。そこで今度は、f(x)を微分してa1のxをなくし、x=0を代入してa1だけを残してみます。



 同じように作業を続けていくと……



 したがって、f(x)は次のように表せることがわかります。




 以上のことを私は結城浩『数学ガール』で納得したのですが、実はほぼ同じ説明が数学靴龍飢塀顱陛豕書籍/平成11年発行)のp.85に載っていることに最近気がつきました。微分の章末で「発展・展望 導関数と多項式」というふうに付け加えられています。

 なお、上記の計算はテイラー展開でa=0とした場合なので、より正確にはマクローリン展開とよぶべきものなのかもしれません。

 教科書ではテイラー展開という言葉は出されておらず、「xについてのn次の整式f(x)をx−aについての整式……(略)……の形に書き直すことを考えよう」というふうに話が始まり、eの近似値を求める問題で終わっています。

 納得したいまだから、「ほぼ同じ内容」と思えるんだろうな。

(つづく)

読書記録(ガ1) | permalink

フィボナッチ数列の母関数のグラフ

 母関数は母・関数なのだ、ということに気づいた私は、関数ならばグラフを描いてみようじゃないかと思いたち、GRAPESを開きました。まずは、母関数の閉じた式でグラフを描いてみました(黄色)。



 次に、一般項を求めるために変形した 1/(1−kx)構成のグラフを重ねてみます(黒)。黄色い線は残したまま描いてみると・・・



 ちゃんと重なってよかった。

 重なることがわかったので、黒を消して黄色を残したあと、無限級数で表した母関数を、x^10の項で切った式をつくり、グラフを描いてみました(赤い点線)。



 やはり「ある部分だけ」重なるようです。x>0の部分はyの値が大きすぎてどこまで寄り添っているのかわからないけれど、x<0の部分はあるところから急にはずれていくようです。近づいてみると・・・



 項の数を変えてみます。緑の点線は x^5 の項まで、青の点線は x^20 の項まで。



 項の次数が増えると、寄り添う範囲が少しずつ広がっていきます。

 これに、|(1+√5)x/2|<1 から導いたxの範囲をグレーの線で表すと、次のようになりました。なお、|(1−√5)x/2|<1 から導けるxの範囲も記入してあるのですが、左右にはずれているので、画面には出ていません。 



(つづく)

読書記録(ガ1) | permalink

やや力づくの一般項導出を経て気づいたこと

 結城浩『数学ガール』第4章では、「僕」とミルカさんが4つの新しい文字を取り入れることでフィボナッチ数列の一般項をスマートに求めてくれました。

 一方、母関数の閉じた式の分母に黄金比を感じ取ってしまった私は、新しい文字を導入することなく、強引に一般項を求めてしまいたいという思いにかられました。

 というわけで、基本方針は同じ・・・

    1/(1−kx)で構成された式を導き出す

・・・にして、文字の導入なしで一般項捻出を試みます。

 まずは、分母をx^2+x−1の形にして、x^2+x−1=0を解き、その解をもとに因数分解します。次に、分母のかっこの中をそれぞれ1−kxの形にするために、操作を続けます。



 最後に分子がすっきりとxになって「ありがとう〜」と言いたい気分。

 次に、分母が積の形になっているので、これを 1/(1-kx) の形にもっていくために、試しに次の計算をしてみます。



 これまた最後で分子が√5xになってくれて、ありがとう〜〜という感じです。

 よって、次のことがいえます。



 あとは、「僕」とミルカさんと同様にして、



の考え方を使えば一般項が求まるわけですが、すでに書いたように()、k>1なのにそれをしていいかどうか・・・という不安が残ります。

 どう考えたものか戸惑いながら、あれこれ考えました。そもそもなぜこの無限級数の話題が出たかと言うと、無限級数は、ある関数を、その定義域の一部について定義することがあることについて例を使って考えるためでした。

 となると、理解できていないのは母関数の意味なのかもしれない。そう考えたとき、ハタと気づいたこと。母関数は、母・関数ではないか。そうだ、関数だ。(1+√5)/2は確かに約1.618で1より大きいけれど、これはxの係数にすぎない。いま問題になっているのは、kx全体の定義域が−1より大きく1より小さいということではなかったか。(1+√5)/2にはxがついているのだ。馴染みのある黄金比の数値に目を(気持ちを)奪われて、肝心のxのことをすっかり忘れていました。

(つづく)

読書記録(ガ1) | permalink

一般項導出についての気になりごと

 というわけで、〔フィボナッチ数列の母関数〕→〔母関数の閉じた式〕→〔無限級数にもどす〕→〔一般項〕 という流れを見てきましたが、「僕」は一般項に感動したあと、こんなことを思います。

 僕は、ミルカさんの話を聞きながら、別のことが心配になってきた。無限級数の計算をするときには、和の順序を変えてはまずいんじゃなかったっけ。問題ないんだろうか。ミルカさん・・・・・・。
 一方、ミルカさんはといえば
「条件をきちんと言わなければまずいんだけどね。でも今回はいいのよ。母関数を使って見つけたことは内緒にしておいて、出てきた一般項を数学的帰納法で証明しちゃえばいいんだから」
とすました顔。

 この部分については、PDFファイル「ミルカさんとフィボナッチ数列」の「読者のみなさんへ」の中で、結城浩さんが次のような補足説明をされています。
ミルカさんはすました顔ではしょりましたが、『コンピュータの数学』によれば、0 割りや和の順序を変えることについても厳密に定式化できるそうです。

 ちなみに、上記PDFファイルと書籍『数学ガール』では同じ内容でも表現の仕方が微妙に違っていて(最後の一般項の形も少し違います)、『数学ガール』マニア(!?)にとってはその違いがなかなか興味深いのです。

 というのも、私はといえば0割や和の順序については無頓着でいて、それよりも気になったのは 1/(1−x) と 1/(1−rx) を同じように扱うことだったのですが、上記PDFファイルでは、書籍『数学ガール』で触れられていない1/(1−x)から1/(1−rx)への橋渡しの経過が書かれてあるのです。「僕」も「1/(1−x)または1/(1−rx)に近い形にできないだろうか・・・」というふうに考えています。

 見比べてみると、結果としては書籍『数学ガール』のほうがすっきりと的をしぼった記述になって読みやすいけれど、すっきりしている分、rxを扱うときに慎重になり、|x|<1という条件はrxになったときにどうなるのだろう?ということが気になってきます。

 なぜ気になり始めたかというと、「僕」やミルカさんのように新しい文字を取り入れず、力づくで一般項を導出できないだろうか?と計算しているときに、馴染みのある黄金比の数値が出てきて、(直接計算してみてもすぐわかることだけれど)これは短い部分を1としたときのx、つまり約1.618で1より大きいぞ・・・と思ったからなのです。が・・・

(つづく)
読書記録(ガ1) | permalink

フィボナッチ数列の母関数から一般項へ

 というわけで、フィボナッチ数列の母関数の閉じた式が求まりました。

     

 今度はこれをもう一度無限級数で表します。そうすれば、無限級数の係数の並びがもとの数列なのだから、数列の一般項を求めることができます。ちなみに私としては、こんなイメージをもちました。↓



 結城浩『数学ガール』ではどう考えてあるかというと、まず「僕」は無限級数のいちばんシンプルな形



 に近づけることができないか?と考えます。フィボナッチ数列の母関数の閉じた式において、分母はxについての2次式なので、r、sという文字を導入し、1−x−x^2=(1−rx)(1−sx)と因数分解できると仮定して計算を進めていくのですが、うまくいきません。

 そこでミルカさんが、分子にもR、Sという新しい文字を用いることをアドバイスします。こうしてr、s、R、Sという4つのパラメータを取り入れたのち、「僕」とミルカさんは次のような式を得ます。(なお、青い丸はこちらでつけたものです。)



 したがって、フィボナッチ数列の一般項は



となります。このあとr、sを求めて代入すれば、完成。




(つづく)

読書記録(ガ1) | permalink
  
  

<< | 2/3PAGES | >>
サイト内検索