2014/01/25

【読書メモ】 離散数学「数え上げ理論」

僕は電機メーカの在籍時に、業務自動化システムの拡販営業に携わった時期が比較的長く、大まかな論理データモデルやLCMP・TCMPレベルでのシステム構成なども描いてきたわけだが、それらの経緯において(簡単な)漸化式や確率論なども適宜習得した次第であった。 
更に立ち返れば、高校時代の数学においても、集合や確率だけはちゃんと勉強したので、それらの素養については並レベルの理系学生よりは有るつもり。
(一応断っておくが、温度湿度や重量体積などハードウェア技術はあまり分からない、というのもそういう縁があまり無かったため。もちろん発電システムの基本的構成くらいは分かるけどね。)

とはいえ ─ 以前にここに「数学が嫌い」な所以についてのやや砕けたコラムを載せたこともある。
そこでは、人間のごく直観的な(或いは漸化的な)思念と、それらが凝縮され閉じられた特定の公式と、この「両者の橋渡し」が現代では軽視され過ぎているのではないか、という不満について書いてみた。
さてその「両者の橋渡し」について、単純明瞭にかつ段階的に明示した解説書はどこかに無いものか、数学全般についての分厚いテキストでなくてもよい、僕でも分かる程度の集合論や確率論等について書かれていればよい、と、時おり書店で探していたのだが…

あった!これだ!この本は解り易い、と中をバッと開いてほんの3ページほど読み進めただけで従来の不満がどんどん氷解していく…たちまち納得して昨年末に購入したのが本書。
『離散数学「数え上げ理論」』 - 講談社BLUE BACKS刊、野崎昭弘・著。

2008年初版のようだが、数学基礎についての解説書ゆえ時節はほとんど問われないだろう。
なんといっても本書はほぼ一貫して、諸要素の「対応」の基本観念を足元に据えており、きっと誰もがおのれのペースで歩調乱さず追随出来ようそこから事象の発生数や再配分の可能性の検証まで、思考の遠足が始まっていく。
むろん、本書は後半以降がなかなか難しく、最後まで精緻に読み切るのはキツイ、数学通でない僕などはなおさらついていけない ─ しかし本書は問題設定が絶妙に巧く、普遍的かつ拡張的な問題(むしろ論題か)をたたき台に据えつつ論理展開がなされるところ、実に誠実な構成だ。
因みに、これは偶然だが、著者の野崎氏が1970年代に著された傑作「詭弁論理学」が僕の実家に有って、まだ学生だった頃(?)の僕がかなり以前に拝読した折にも、平易にして発展的な論旨にまこと感心させられたものであった。

よって、本書につき以下に【読書メモ】としてまとめおく。
尤も、本書は着想方法において学ぶところ大きかった反面、具体的な数式引用や転記はいちいち面倒かつ軽微な誤記すらも許容されないので、今回の【読書メモは】僕なりのごくごく簡素な再解釈と所感に絞り、以下に記すことする。



・本書はまず導入部にて、順列や組み合わせの初歩的な問題、ここでは「友人へプレゼントを配る方法」の計数についての模索から始まる。
或る実在と別の実在の関係付けとその計数はいわば人間の基本的な能力であるそうで、暫らくは中学高校の数学で学ぶ順列・組み合わせのおさらいが続く、が、そこのところ欠伸を我慢しつつ一歩一歩ゆっくり読み進めていけば…。

なんと、有名な論理パズルの問題、つまり「トーナメント戦の最小試合数(引き分けナシ)を計数する方法」も導いてくれる ─ つまり、「試合数」と「負けたチームの数」が1:1で対応しているので、チーム数の総計さえ分かれば試合数もすぐ分かるというもの。
さらに、あみだくじにおける例で、或るグループAと別のグループBの要素が互いに 1:1 で漏れなく対応している場合、「逆対応」が成立する由であることを明示している。

================

・さて次の例題は、本書購入を思い立ったきっかけの一つでもある。
『同じ箱入りチョコレート6つを、4人の友人に配る。全ての箱を配るものとし、1人に何箱渡してもよい、また一つも貰えない友人がいてもよい。この場合に箱の配り方は何通りあるか?』

なーんだ、こんなの高校の数学の初歩じゃないか、バカにすんな俺は数学の偏差値が70以上だったんだぞ…と咄嗟に声を挙げたくなる学生も多いだろう。
なるほど学校で数学をちゃんと勉強した子なら、「配られる箱の実数が無い」という情報とは別に、「数える対象ではない│という暫定記号」をも併せて用いれば、すべての対応を過不足無く計数出来る…とすぐ思い出す。
たとえばAさんに1箱、Bさんには無し、Cさんには3箱、Dさんに2箱なら、
●│無│●●●│●● と記せばよい、だから答は6+3つまり全体で9個のうちにおける3個の│の組み合わせ 9C3=84通りだ、と。

むろんそれでよいが ─ しかし僕はこの区切りの│について丁寧に読み返していて、咄嗟に思い当たっことがある。
かつて僕が販売担当していた或る自動計数機においては、「存在情報そのものを無視する」と仮定した所謂ダミーカードを敢えて計数させ、それで寧ろ計数ミスを無くして全体の整合性を図っていたもの、これはきっと今でも採用されているロジックであろうが ─ つまりはこのダミーカードの智慧を本書であらためて実感した次第であった。
つくづく、数学は解放パターンの暗記「のみ」では実感出来ぬもの。

===============

・分割数の概説は、とりわけ面白かった。
この箇所、僕なりの汎用表現では纏めらそうもないのでちょっとだけ具体的に引用。

m個の同じ品物をn個の同じ袋に分ける、ただし空袋は許さない、その「組み合わせ」の方法を p(m,n)  と記す。
では p(8,4) の場合に、全部で組み合わせは何通りあるか。
とりあえず、まずは4個の品物を4個の袋に入れる場合、これつまり p(4,4) で 1+1+1+1 となり、組み合わせはこれ一つのみ、となる。
それに加えて」、「残りの4個の品物」の配分組み合わせについて考えると ─ p(4,4) はつまり上と同じく組み合わせ1つ、p(4,3) では3+2+2+1 しかないので組み合わせ一つ、ただし p(4,2) では 4+2+2+1 および 3+3+3+1 と組み合わせは二つ有り、しかし p(4,1) では 5+1+1+1 で組み合わせ一つ、…組み合わせは全部で5通り。
あらためて p(8,4) の組み合わせ数をまとめると、とりあえず最初に袋に入れた p(4,4) は除き、「残り4個の品物と4袋の組み合わせ数」の合計となるので、これをひっくるめた式は p(8,4) = p( (8-4), 4) + p( (8-4), 3) + p( (8-4), 2) + p( (8-4), 1) となる。
だがここで、p( (8-4), 3) は更に計算すすめて p( ( (8-4) -3), 3) + p( ( (8-4) -3) ,2) + p( ( (8-4) -3), 1 )と分けていくことが出来、同様に p( (8-4), 2) は
p( ( (8-4) -2), 2) + p( ( (8-4) -2), 1) へと分けられる。

こうして、m個の同じものを幾つかに分ける組み合わせ方法を突き詰め、それを最大mまで漸化式で表すと p(m) = p(m,1) + p(m,2) + p(m,3)p(m,m) となる。
この p(m) を分割数と称すが、完結的に閉じた方式はないという。

なお本書では上に続けて、特定条件付きの分割数について論旨展開、その過程でオイラーの定理が紹介されているが、ここではこれを整数の分割を突き詰めた証明例を紹介している。
(或る数の奇数ずつへの分割数と、異なる数への分割数、それらが漏れなく対応しているとして)。

=================

・フィボナッチの数について。
本書では複利計算の引用例から入り、フィボナッチ数の増加例としてよく知られた自然界での発現例のほか、階段の登り方(何通りありうるか)や、タイルの埋め方の問題などが例示されている。

が、それより面白いのはカタラン数の紹介。
パスカルの三角形に則った道順計数の図において、→の進路選択数を↓の進路選択数が絶対に超えないように設定し、その特定の道順記法がカタラン数であるとまず説明している。
このカタラン数の応用紹介例として抜群に面白いのが、「文章における文節の合成可能な場合数」についての概説。
或る文章の文節ひとつずつ、n角形におけるn-1の辺にまず対応させ、そのn角形を三角形に分割する方法数こそが、もとの文章の文節合成の場合数にきっちり対応していることを示す。

================

…以上まで昨年末にほとんど一気に読み抜いて、そこでさすがにバテた。
そこで本書はしばらく寝かせておき、昨日からあらためて続きを読もうとした、が、集合論と包除原理、さらに差分方程式、母関数、チェスのクイーンの配置問題となると、もう僕には未知の素養、領域だ。
よもや学生じゃあるまいし ─ 未知で未体験の論理をスイスイ捕捉し吸収するバカ正直な謙虚さも減衰してきたようなので、とりあえずこのへんで。


以上