第 III 部 数え上げ

数え上げは簡単に思える: \(1\), \(2\), \(3\), \(4\), \(\ldots\) と数えることぐらい誰でもできる。しかし、この直接的なアプローチは構造を持たない少量の物事 ── 例えば手足の指の本数 ── を数えるときにしか使えない。理論付いた数学を使えば、構造を持つ膨大な物事を数えられるようになる。例えば:

意外なことに、この二つの値は \(1820\) に等しい (しかし明らかに偶然ではない)。

数え上げが情報科学で重要な理由はいくつかある:

最初の第 14 章では、\(\sum_{i=0}^{n} x^{i}\) や \(\prod_{i=0}^{n} i\) といった頻繁に登場する総和と総乗を閉形式の式に変形するための規則と方法をいくつか学ぶ。また、\(\sim\), \(O\), \(\Theta\) などの漸近記法も紹介する。これらの記法はプログラムの実行時間といった量が入力のサイズに応じてどのように変化するかを表現するときによく利用される。

第 15 章では、集合の濃度を計算するための最も基礎的な規則を学ぶ。これらの規則は実際には定理であるものの、本書では (積分と同じように) 証明ではなく実際的なスキルとして問題を解くのに使う方法に重点を置いて解説する。

数え上げは厄介であり、人は絶え間なく間違いを犯す。そのため数え上げの学習では、自分あるいは他人の議論を正しく検証する方法を学ぶことが非常に重要となる。異なる方法で数え上げた結果を比較することで検証が可能な場合もある ── 両者が一致しなければ間違っている。しかし、最も初歩的な数え上げの議論は、注目しているオブジェクト全体の集合から簡単に数え上げられる集合への全単射を示すアプローチを使う場合が多い。第 15 章では、そういった全単射を明示的に定義する ── そして実際に全単射だと示す ── 手法が数え上げの議論を検証する有用なアプローチであることを説明する。この章の内容は単純かつ強力であり、将来のキャリアで実用可能な素晴らしいツールを提供する。

最後の第 16 章では母関数を説明する。母関数を使うと、式の簡単な代数的変形を使って様々な数え上げ問題を解くことができる。

広告