離散数学「数え上げ理論」 (ブルーバックス)

身近な数え上げから、徐々に
高度な場合分けへと進んでいきます。

きっと簡単に書いてあるのだと
思うのですが、途中からついて
いけなくなってしまいました。

ある程度知識のある人が読むと
面白い本だと思います。

一般向けの数学書は、「あまり数学の知識のない読者にも分かること」と「かなり数学的訓練をうけた読者にも面白いこと」という相反する2つの要請を満たさなければならない。これはなかなか難しいことだが、本書はそれに成功している。日常的な話題から出発して、かなり高級な結果まで読者を親切に導く。

2種類の文字a,bをn個ずつ用意し1列に並べる。左端から任意の途中までのｂの個数がそこまでのaの個数を超えないという条件を満たす順列の数をカタラン数という。それが凸n+2角形の3角形分割の方法の数に等しいというのは、面白い。

表題にあるように、本書は「数え上げ理論」の紹介だが、最後の章「Nクイーン問題と群論」は少し毛色が違うようだ。せっかく母関数の話を紹介したのだから、話題とした分割数（自然数nを自然数の和に書く方法の数）やカタラン数の母関数を取り上げた方がまとまりがよかったのではないか。また、グラフ理論における数え上げの問題も、関連する話題として興味があると思う。

なお、数え上げ理論をより詳しく勉強したい方には、スタンレイ著「数え上げ組み合わせ論」（日本評論社）を薦めたい。

数え上げ理論とは、古典的整数論、現代的な組合せ論とともに２０世紀以降重要性が見直された離散数学を支える三本の柱の一つ。可能性があるすべての場合を漏れなく、かつ重複なく数え上げるための道具・理論、すなわち分割数、フィボナッチ数、カタラン数（何と活躍する数であることか！）、包除原理、差分方程式、母関数の理論、そしてチェスのＮクィーン問題と群論初歩までをカバーする。様々なおみやげの配り方は何通りか？という問題が導入口で、順列、組合せ、階乗、等比級数の和の知識があれば、後は具体例（そこには腕力で数え上げるエレファントな手段も用いられる）→抽象化の反復を通じて、上記の重要な概念を自然に体得できる。一対一対応を考えるにはあみだくじが、差分方程式を考えるには賭けの確率が例示される、といった具合だ。ｎ個の同じものを、いくつかの同じ袋に分けるとき、（ア）すべてを奇数個ずつに分ける仕方の数と（イ）どの２つも異なる数に分ける仕方の数とは、いつでも一致するというオイラーの定理が、オイラーが証明に使った無限級数に頼ることなく、よりシンプルに証明できるのには感激した。母関数は自然数の和の求め方を例にとって説明されるが、幾何学の透明性、代数学の一般性、解析学のパンチ力が対比され、それぞれの特徴を掴むことができる。このように、著者の目的とする「抽象化の力」「考える力」が読み進むうちにみがかれるのに大いに満足した。久々に手にとった数式が豊富に登場する数学の本であったが、これほど愉快・爽快な読後感を持てる本は滅多にないと思う。

離散数学とはコンピュータの０と１のような飛び飛びの量を現しています。数え上げ理論は
その中の大きな柱であります。

まず数え上げ理論には確率、順列、組み合わせを使い、その方法として分割数や
フィボナッチ数、カタラン数があります。

次にこれらをもっと莫大な数や数列をまとめ上げた場合にはどういった方法を
使えばいいのか？
これらが包除原理、差分方程式、母関数の理論です。
これさえあれば全ての公式が統一的な形でまとめて出てきてしまう優れものです。

実際本書を読んでいくとゲーム形式、パズル形式になっていて、数学を学ぶというよりも
ゲームを遊んでいる感覚に近い！
道順を数えるからカタラン数、フィボナッチ数など具体例を挙げながら、著者と一緒に
クイズを解く感覚です。
そして最期のクイーン問題は元々チェスのクイーンの動き方からいくつ置いたら、
お互いのクイーンの利き筋にブツカラナクテ済むかというまさにゲームそのものです。

ブルーバックスの数学本というよりもゲーム攻略本の感覚で読んで解いて遊んで
欲しいものです。

【主要目次】<第一部 数え上げ問題：分割数、フィボナッチ数、カタラン数> 第1章　並べ方を数える、第2章　選び方を数える、第3章　道順を数える、第4章　分割の仕方を数える、第5章　増えてゆくものを数える、<第二部 数え上げ理論の三種の神器：包除原理、差分方程式、母関数の理論> 第6章　プレゼント交換と包除原理、第7章　賭博と差分方程式、第8章　自然数の和と母関数、第9章　Nクイーン問題と群論

「順列・組合せ」と聞くだけで敬遠される方は多いかと思います。nPrだのnCrだのn!だのと記号がやたら出てくるし、「区別する・しない」や「重複を許す・許さない」など付加条件がやたら面倒だし、それらのケースに対応する公式も色々あって厄介です。それらの公式を丸暗記しても応用問題になると途端に手も足もでないという方も少なくないでしょう。本書では「公式を導くための基本的な考え方」から懇切丁寧に具体的に説明しているので、腰を据えてジックリ読めば必ず理解できます。はじめから優雅な解法(elegantな解法)で解けない場合でも、問題を簡単化してとにかく数え上げる鈍重な解法("elephant"な解法)で答を求め、そこから一般的傾向を把握してelegantな解法へと読者を自然に導く著者の姿勢に頭が下がります。こうして読み進めていると非常に高度な話題まで理解できるようになっています。挿絵も微笑ましく、和みます。(^-^)
高校生は(第二部の一部を除き)本書を理解できると大学受験に役立つでしょう。Googleの入社試験に出そうな問題もあります(笑)。一部の話題(母関数・フィボナッチ数・カタラン数・分割数など)は「数学ガール」でも扱われていますので相補的に読めば理解が深まるでしょう。(分割数の"閉じた公式"(Hans Rademacher(1937))については「数学ガール」エピローグをご参照)