■コマ大数学科167講(補習):経路問題

「たけしのコマ大数学科」の前回の講義「北大に挑戦」は、北海道大学の入試問題が取り上げられたが、ガスコン爺なりに経路問題を補習しておこう。

碁盤の目状の道路があって、S地点からG地点までの経路数を考える。初期状態では、「北→東」と「東→北」の2通りの経路がある。キーボードの方向キーで動かすと、最短経路(後戻りはダメ)の数は、直前の交差点に達するまでの経路数(青い数字)を足し合わせたものだということがわかる。

で、今回の「補習」の目的は、「経路問題」に隠された数の不思議である^^;

4年ほど前に、現在の「たけしのコマ大学数学科」が始まった。たまたま、爺は番組に興味を抱いたのは、「数学」が楽しそうだったから。爺自身は、数学の落ちこぼれであり、なんとなく数学に対して自信がなかった。そんなわけで毎回「コマ大数学科」を受講して、このブログの記事を書いてきた。

そこで、このブログを始めた頃の記事を振り返りつつ、もう一度、自分自身の理解を確かめる意味で、復習してみようと思う。

パスカルの三角形

最短の経路数を各格子点(碁盤目状の道路の交差点)に書き込み、回転させ、スタート地点を三角形の頂点に持ってくれば、パスカルの三角形になる。これは、冒頭のFlashで確認したように、直前の格子点までの経路数を足し合わせるというのがパスカルの三角形のルールだからだ。

経路問題(1)

パスカルの三角形の偶奇を塗り分けると「シェルピンスキーのギャスケット」になることは、過去記事で紹介済み。爺は、結城浩さんの「プログラマの数学」という本で初めて知ったのだが、本当に驚いた。アンリ・ミショー(Henri Michaux:1899~1984年)というフランスの詩人が「手術台上のミシンとコウモリ傘の出会いのように美しい」と書いたが、ミシンとコウモリ傘の出会いが美しいかどうかは爺にはわからないが、パスカルの三角形とシェルピンスキーのギャスケットの出会いは美しい^^;

ここでは、別の視点で、ピラミッド状のパスカルの三角形の階層を上から順番に番号を振り、階層に現れる数を足し合わせてみよう。

(n=0):1=2^0
(n=1):1+1=2=2^1
(n=2):1+2+1=4=2^2
(n=3):1+3+3+1=8=2^3
(n=4):1+4+6+4+1=16=2^4

足し合わせた数が「2」の累乗(階層数が乗数)になっている。これを経路数を求めたときと同じく、組み合わせ数(Combination)で書いてみる。Sは(Sum:総和)の意味ととらえてほしい。

経路問題(2)

経路問題(3)

Σ(Sigma)は、添え字の「k=0→n」を順次、式に代入したときの総和の意味(kは、整数)。たいぶスッキリした数式になるが、言わんとしていることは同じ。

フィボナッチ数列

碁盤目状の経路図からフィボナッチ数列を見つけるには、ちょっとした工夫が必要だ。ここでは説明のため、図の右上をスタート地点、左下をゴール地点とした。

この「0,1,1,2,3,5,8,13……」という数の並びをフィボナッチ数列と言うんだけれど、「たけしのコマネチ大数学科」の第1回のテーマが「フィボナッチ数列」だった。「階段を上るとき、1段上るか、2段上るか、2通りの方法があるとして、15段の階段を2つの方法を組み合わせて上ると何通りになるか」という問題だ。

冒頭のFlashで、注目する格子点の経路数は、その格子点に至る直前の2通りの格子点までの経路数を足し合わせたものになることがわかった。フィボナッチ数列も、直前の2つの数を足し合わせると、その数がわかる。これを数式で表すと……。

経路問題(4)

F0とF1の値が定まれば、F2の値が定まり、F1+F2でF3の値が定まる……このような式を「漸化式」と呼ぶ。まるで「芋蔓式」のように、1つ芋が見つかると、芋蔓をたどって次の芋が見つかるような^^; 酔っ払い爺の勝手な思い込みだが、この芋蔓がどこに繋がっているのか、芋蔓自体を記述したのが「母関数」(生成関数:generating functionとも呼ぶ)。フィボナッチ数列の漸化式から母関数、そして、一般項を求める過程は、結城浩さんの「数学ガール」の中で、詳しく、そして丁寧に順を追って説明されている。

経路問題(5)

※引用元:「数学ガール」結城浩/著

フィボナッチ数列の一般項を求める式に「1/√5」のように無理数が含まれているのに、nに自然数を代入すると、ちゃんと自然数の値が求まるのも不思議な感じがする。また、式の中に「(1+√5)/2」という、黄金比「1:(1+√5)/2」が含まれているのも、神秘的だ。

どーゆーことかと言うと、フィボナッチ数列のFnをひとつ前のF(n-1)で割る。たとえば、F4の「3」を直前の「2」で割ると、「1.5」、5÷3=1.666…、8÷5=1.6、13÷8=1.625……F16(987)÷F15(610)≒1.618と限りなく、黄金比「1.618033989」に近づいていく。

カタラン数

経路問題(6)

カタラン数は、経路問題に「通行止め」が設定されているときに現れる数。通行止めは、碁盤目状の道路の交差点が「東」「北」とも、同じ数としたとき、スタート地点とゴール地点を結んだ対角線をまたいで進んではならないというルール。この対角線上の格子点に現れる「1,1,2,5,14…」という数がカタラン数になる。

コマネチ大学数学科29講:カタラン数」は、「10人が円座になって握手するとき、手が交差しないように握手するには何通りあるでしょうか?」という問題だった。

ところが、当時の爺はどーにも理解できず、さらに「補習」の記事で説明を試みている。今、読み直してみると、爺がどこでつまずいたか、どこが理解できなかったかがわかる。

爺は「競馬」をやったことがないけれど、順列は「馬番連勝単式」で、1着の馬番、2着の馬番を当てなければならない。たとえば1着が「3」で2着が「6」ならば、(3-6)は当たり馬券で、(6-3)は外れ馬券だ。組み合わせは「馬番連勝複式」で、1着、2着の順は問わず、2つの馬番を当てればよい。(3-6)を買えば、6番の馬が1着で、3番の馬が2着でもよい。これは理解できる。

経路問題(7)

爺が問題を咀嚼しても飲み込めなかったとゆーか、すとんと腑に落ちなかったのは、問題の「手が交差しないような握手」という条件が、カタラン数の条件である正方形の格子点を描いたとき、対角線を超えないような経路数と、どのような関係にあるのか……ということ。だから、過去記事でも、その点に触れていない。触れたくても、わからなかったのだ。

これが「アハ!」と瞬間的にわかったのは「数学オリンピック:つり銭問題」を考えたときだ。「一泊500円のホテルがあり、そこに500円玉を持った、n人の人と1000円札しか持っていない、n人の合計2n人の客を泊らせたい。ホテルの受付は受付開始時には、つり銭を準備していないとする。つり銭が不足しないような客の来かたは全部で何通りあるか」という問題。

コマネチ大学数学科65講:順列組み合わせ」でも、同様の問題を取り上げている。中村亨センセは折れ線グラフで説明してくれている。

この問題では、経路図の対角線を超えた半分が除外されることが直感的にわかる。なぜなら、つり銭がなければ、1000円札のお客を受け入れることができないからだ。上図の通行止め「×」は、釣り銭切れと考えることができる。

すると、カタラン数が現れる対角線上の格子点に至る最短経路は(図のようにスタート地点を左下、ゴールを右上とすると)、必ず、東→北(右→上)というペアで構成される。ペアにならず、どこかに北→東という経路が存在することは、握手の問題で言うと手が交差することになるし、つり銭問題で言えば、つり銭がない状態になる。

経路問題(8)

爺が「カタラン・ワカラン」と悩んでいたとき、結城浩さんからコメントをいただき、当時ウェブ上に公開されていた「ミルカさんとコンボリュ―ション」を読んだ。のちに「数学ガール」として出版されるのだが、「数学ガール」では、もっとスマートに、わかりやすく説明されている。

経路問題(9)

「数学ガール」では、計算の順番を変える括弧の付け方が何通りあるかという問題に置き換えている。括弧は「開く括弧"("」と「閉じる括弧")"」が対(ペア)になっており、順番を逆にすることはできない。

東を"("、北を")"とすれば、「東北東北」は「()()」になるし、「東東北北」は「(())」になる。「北東北東」は「)()(」のようになり、ダメということ。

経路問題(10)

※引用元:「数学ガール」結城浩/著

※コマネチ大学数学科の「過去問題」はこちらから。
コマ大数学科:2008年度全講義リスト
コマネチ大学数学科:2007年度全講義リスト
コマネチ大学数学科:2006年度全講義リスト