Concrete Mathematics: A Foundation for Computer Science（コンピュータの数学）

引用

Graham, R. L., Knuth, D. E., & Patashnik, O. (1994). Concrete Mathematics: A Foundation for Computer Science (2nd ed.). Addison-Wesley.

章の要約

本書は9つの章からなり、その後に全演習問題の解答、参考文献、演習の出典、索引が続く。序文はこの分野を、連続数学と離散数学の融合、すなわち一連の技法を用いて数式を制御された形で操作することだと述べている。重点は存在定理や組合せ論的な推論ではなく、計算の技法にある。文体はくだけており、余白には学生のコメント（「落書き」）や過去の数学者の引用が載っている。

第1章：Recurrent Problems（漸化式の問題）

ハノイの塔、平面上の直線、ヨセフスの問題の3つの問題から始まる。いずれも漸化式を導き、それを解く。

第2章：Sums（和）

Σ記法、和と漸化式の関係、和の変形、多重和、和を求める一般的な方法を扱う。有限・無限の微積分と無限和の節で章が終わる。

第3章：Integer Functions（整数関数）

床関数と天井関数とその応用、床・天井を含む漸化式、二項演算「mod」、床・天井を含む和を扱う。

第4章：Number Theory（数論）

整除性、素数、階乗の因数、互いに素であること、合同関係としての「mod」、独立な剰余、さらなる応用、関数φとμ。

第5章：Binomial Coefficients（二項係数）

最も長い章。基本的な恒等式と練習、技巧、母関数から始め、超幾何関数とその変換、部分超幾何和へ進む。最後は第2版の新内容である5.8節「機械的な和の計算」で、序文はこれをDoron Zeilbergerの着想によるものとしている。

第6章：Special Numbers（特殊な数）

Stirling数、Euler数、調和数と調和和、Bernoulli数、Fibonacci数、連分数多項式（continuant）。

第7章：Generating Functions（母関数）

ドミノとつり銭の問題で始まり、基本的な操作、漸化式の解法、特殊な母関数、畳み込み、指数型母関数、Dirichlet母関数を扱う。

第8章：Discrete Probability（離散確率）

定義、平均と分散、確率母関数、コイン投げの問題、ハッシュ法。

第9章：Asymptotics（漸近解析）

増大度の階層、O記法とその操作、2つの漸近的な技法、Eulerの和公式、そして章末の「最終的な和」の節。

主要概念

第1〜3章：漸化式、和、整数関数

• 漸化式と閉じた形：前の値によって表される問題と、再帰を含まない式を求めるという目標。
• 有限解析：離散関数のための差分と和の計算で、微分と積分に対応する。
• 床関数と天井関数：第3章で性質が展開され、本書全体で使われる整数値関数。

第4〜6章：数論、二項係数、特殊な数

• 二項係数の恒等式：第5章の多数の恒等式。超幾何関数が統一的な言語になる。
• 機械的な和の計算：5.8節の、和の恒等式を判定し証明するアルゴリズム的な方法。
• Stirling数・調和数・Bernoulli数：和や漸近解析に繰り返し現れる特殊な数列。

第7〜9章：母関数、確率、漸近解析

• 母関数：数列を符号化するべき級数で、漸化式を解いたり数え上げたりするのに使う。
• 確率母関数：同じ道具を確率変数に用いたもの。
• O記法：誤差項を評価する記法と、第9章の操作規則。

批判的分析

長所

• 目的も方法も明確。 序文は、微積分を学ぶ学生が連続的な演算に習熟するように、離散的な演算に習熟することを目標とし、本書は終始、計算技法に徹している。
• 演習が中心にある。 序文は500題以上の演習を6種類（ウォームアップ、基本、宿題、試験、ボーナス、研究）に分けて挙げ、出版社は研究問題を除くすべてに完全な解答があると述べているので、独習にも使える。Allen StengerのMAA Reviews（2010年）の書評は、有用な結果、特に演習に満ちた価値ある参考書だとしている。
• 歴史と出典。 著者は着想の源をたどり、付録で演習の出典を明記し、Leibniz、Euler、Gaussの引用を余白に織り込んでいる。
• 読みやすい文体。 くだけた調子と学生の落書きは、内容を消化しやすくするための意図的な選択だと序文が説明している。

短所

• 範囲は意図的に狭い。 序文は、扱う話題が学部の離散数学の一般的な内容と異なると述べている。論理、グラフ理論、証明技法は章に含まれない。
• 計算の要求が高い。 長い式変形を手で行うことが期待され、ボーナス問題や研究問題は、講義を受ける平均的な学生が扱える範囲を超えている。
• 第2版の変更は限定的。 第2版は5.8節の追加と訂正を行った。本文自体は1980〜90年代のものであり、著者は後の刷のための正誤表を維持している。そこにはBernoulli数の定義に関わる訂正も含まれる。

コースにおける位置づけ

このコースのリストの中で、Concrete Mathematics は計算技法に最も力を注いだ本である。Levin の公開教科書は数学的推論に初めて触れる学生向け、Epp の教科書は計算機科学の離散構造とともに推論と議論の書き方を教え、Rosen の教科書は論理、証明、数え上げ、グラフを扱う幅広い講義用テキスト、Lovász、Pelikán、Vesztergombi の薄い本はパズルと簡単な数え上げから始める問題主導の入門書である。どれも、Graham、Knuth、Patashnik を読みやすくする土台になる。

van Lint と Wilson の A Course in Combinatorics は大学院レベルの総合的な教科書で、多数の短い章でグラフ理論、デザイン、符号、有限幾何を扱う。Graham、Knuth、Patashnik は、そうした構造ではなく和、漸化式、母関数、漸近解析に集中する点で、これを補う。

本書の使い方

序文によれば、本書はスタンフォード大学の講義から生まれ、受講者は3、4年生と、その多くが大学院生であり、著者は2年生にも届けたいと考えた。説明や演習で微積分がよく使われるため、微積分に慣れていることが前提となる。

• 中核： まず第1章と第2章、次に第3章、時間が許す限り第5章と第7章。母関数（第7章）は、本書で最も繰り返し使える道具である。
• 計算機科学向け： 第8章と第9章。ハッシュ法、確率、アルゴリズムの解析に使うO記法を扱う。
• 選択： 数論に慣れているなら第4章は軽く読んでよい。第5章の超幾何の節（5.5〜5.8）は2回目に回してよい。

初読では各章のウォームアップ問題を試し、真剣に取り組んでから解答を見て、宿題問題を本当の試金石とすること。序文は最初の二つの習慣を明確に勧めている。