Discrete Mathematics: Elementary and Beyond（離散数学：初歩とその先へ）

引用

Lovász, L., Pelikán, J., & Vesztergombi, K. (2003). Discrete Mathematics: Elementary and Beyond. Springer (Undergraduate Texts in Mathematics).

章の要約

本書は約290ページに15の短い章を収め、最後に演習の解答からなる長い章が続く。序文によれば、本書は離散数学を深く網羅しようとはしていない。主に組合せ論とグラフ理論から選んだ結果と方法を論じ、初等整数論、確率、組合せ幾何を少し加えている。節の題はしばしば親しみやすいもの（「パーティー」「プレゼントを配る」「攻撃を受ける惑星」）になっている。

第1章：数えてみよう！

本書はパーティー（誰が誰と握手するか、席順は何通りあるか）から始まり、そこから基本的な数え上げの道具を組み立てる。集合、部分集合の個数とその近似的な大きさ、列、順列、順序つき部分集合、決まった大きさの部分集合を扱う。

第2章：組合せ論の道具

帰納法、数の比較と見積もり、包除原理、鳩の巣原理。章は「双子のパラドックスとおなじみの対数」で終わる。

第3章：二項係数とパスカルの三角形

二項定理と、プレゼントやお金の配り方、アナグラムの作り方といった数え上げの問題から、パスカルの三角形へ進む。その恒等式を調べた後、係数のふるまいを「鳥の目」と「鷲の目」から眺める。

第4章：フィボナッチ数

フィボナッチのウサギの問題、恒等式の数々、そしてフィボナッチ数の明示的な公式。

第5章：組合せ論的確率

有限の標本空間上の事象と確率、実験の独立な反復、大数の法則、そして小数の法則と「非常に大きな数の法則」についての節。

第6章：整数、約数、素数

最も長い章で、整除性、素数とその歴史、素因数分解、素数全体の集合、フェルマーの「小」定理、ユークリッドの互除法、合同式を扱う。さらに「奇妙な数」、整数論と組合せ論の結びつき、素数判定へと続く。

第7章：グラフ

次数の偶奇、道・閉路・連結性、オイラー路とハミルトン閉路。

第8章：木

木の定義のしかた、育て方、数え方、保存のしかた、そしてラベルのない木の個数。

第9章：最適なものを見つける

グラフ上の二つの最適化問題、すなわち最良の木を見つける問題と巡回セールスマン問題。

第10章：グラフのマッチング

ダンスの問題ともう一つのマッチングの問題から、マッチングについての主定理へ進み、完全マッチングを見つける方法が続く。

第11章：幾何における組合せ論

対角線の交点の数え上げ、領域の数え上げ、凸多角形についての結果。

第12章：オイラーの公式

「攻撃を受ける惑星」から平面グラフと多面体に関するオイラーの公式を導入する。

第13章：地図とグラフの彩色

2色による領域とグラフの彩色、多色によるグラフの彩色、地図の彩色と四色定理。

第14章：有限幾何、符号、ラテン方陣、その他の美しい生き物たち

小さな風変わりな世界、有限アフィン平面と有限射影平面、ブロックデザイン、シュタイナー系、ラテン方陣、符号。

第15章：計算量と暗号をのぞく

「アーサー王宮廷のコネティカットの授業」から出発して古典暗号を論じる。続いてチェスの最後の一手を封じる方法、パスワードを知らずに検証する方法、大きな素数の見つけ方、公開鍵暗号へと進む。

第16章：演習の解答

本文中の演習の解答で、30ページを超える。

主要概念

第1〜4章：数え上げ

• 部分集合と順列の数え上げ：二項係数と階乗の背後にある基本的な数。
• 包除原理と鳩の巣原理：数え上げと存在証明のための二つの一般的な道具。
• パスカルの三角形：二項係数の配置。その恒等式と大きな規模でのふるまい。
• フィボナッチ数：多くの恒等式と明示的な閉じた公式をもつ漸化式。

第5〜6章：確率と整数論

• 大数の法則：独立な実験を繰り返したときの平均のふるまい。
• 素因数分解の一意性：すべての整数は本質的にただ一通りに素数の積として表される。
• ユークリッドの互除法と合同式：最大公約数の計算と、m を法とする算術。
• フェルマーの小定理と素数判定：合同式と素数の見分け方の結びつき。

第7〜13章：グラフ

• オイラー路とハミルトン閉路：すべての辺を一度ずつ通ることと、すべての頂点を一度ずつ訪れることの違い。
• 木：閉路をもたない連結グラフ。その数え方と保存のしかた。
• グラフ上の最適化：ネットワークにおける最良の木の選択と、巡回セールスマン問題。
• 完全マッチング：グラフの頂点を辺に沿って二つずつ組にできるのはどのような場合か。
• 平面グラフとオイラーの公式：頂点、辺、面の関係。
• グラフと地図の彩色：2彩色可能性と四色定理。

第14〜15章：デザイン、符号、暗号

• 有限射影平面とブロックデザイン：釣り合いのとれた接続関係をもつ有限の構造。
• ラテン方陣と符号：組合せ的な配置と誤り訂正符号。
• 公開鍵暗号：古典暗号と計算量の考え方の後に扱われる、整数論に基づく暗号。

批判的分析

長所

• 意図的に取捨選択している。 序文は、離散数学を深く網羅することを本書の目的とせず、そもそもそれは定義が曖昧で不可能な課題だと述べる。その代わりに選んだ結果を丁寧に展開しているので、各話題には動機づけと証明のための余裕がある。
• 証明と問題解決が中心にある。 著者たちは可能なかぎり証明を与え、証明が難しすぎる場合は、それが技術的で本書の範囲を超えると明言する。読者には、本文中の問いに答え、各章末の問題を「パズルを解くように」解くことが強く勧められている。
• 数学がつながり、生きていることを示す。 序文は、結果が以前の結果の上に築かれること、差し迫った未解決問題があること、考え方の美しさが重要であることを示したいと述べる。目次はパスカルの三角形やフィボナッチ数から、有限幾何、符号、計算量、公開鍵暗号にまで及ぶ。
• 解答がついている。 分量のある解答の章が独学を支える。

短所

• 離散数学の授業全体をカバーするものではない。 論理、形式的な集合論、関係、フィボナッチ数以外の漸化式の解法、母関数は章や節の見出しに現れない。それらを求める授業には、より網羅的な教科書が必要である。
• 独立した主題としてのアルゴリズムは手薄。 アルゴリズムはユークリッドの互除法、全域木、マッチング、素数判定といった話題の中に現れるが、アルゴリズム解析の体系的な扱いはない。
• 短い章がある。 いくつかの章（幾何における組合せ論、オイラーの公式）は10ページ前後で、話題を深く展開するというより導入にとどまる。

コースにおける位置づけ

このコースのリストの中で、Lovász、Pelikán、Vesztergombi の本は問題を中心にした、数学者による入門である。Oscar Levin の無料の Discrete Mathematics: An Open Introduction と Susanna Epp の Discrete Mathematics with Applications は、論理や証明技法を含む標準的な最初の授業内容をより体系的に扱う。Kenneth Rosen の Discrete Mathematics and Its Applications は包括的な参考書で、ほとんどあらゆる方向で本書より広い。それらの本で標準的な授業を受ける学生は、本書の対応する章を読むことで、数え上げ、整数論、グラフについて、よりパズル主導で深い扱いに触れられる。

さらに進んだ学習には、Graham、Knuth、Patashnik の Concrete Mathematics が和、漸化式、母関数を本書の第4章をはるかに超えて展開する。van Lint と Wilson の A Course in Combinatorics は、第10〜14章の主題であるデザイン、符号、ラテン方陣、グラフ理論を研究の水準まで進める。第14章はその本へのよい予告編になる。

本書の使い方

出版社は本書を、数学とは何かを感じ取りたい数学・計算機科学の学部生に向けたものとしている。序文は、大学の数学をまだ微積分しか学んでいない読者に語りかけている。微積分は必要なく、必要なのは中等教育の数学と問題に取り組む意欲だけである。帰納法は第2章で導入される。

• 中心： 数え上げの第1〜3章、整数論の第6章、グラフと木の第7〜8章が骨格をなす。
• 関心に応じて選ぶ： 確率なら第5章、最適化とマッチングなら第9〜10章、幾何・平面性・彩色なら第11〜13章、デザインと符号なら第14章、計算量と暗号なら第15章。第15章は第6章の整数論を用いる。
• 読みながら問いに取り組む。 序文は問題解決を不可欠なものとしている。先へ読み進める前に本文の各問いを試み、第16章を確かめる前に章末問題を解く。
• 体系的な教科書と組み合わせる。 授業で論理、関係、漸化式が試験されるなら体系的な教科書を併用し、本書は扱う話題についての深さと動機づけのために使う。