Analytic Combinatorics (2009) [pdf]
This book by Philippe Flajolet and Robert Sedgewick presents a comprehensive introduction to analytic combinatorics, a field that uses complex analysis to study combinatorial structures. It develops methods for the asymptotic analysis of combinatorial sequences, covering topics such as generating functions, symbolic methods, and singularity analysis, with applications to algorithms, data structures, and probability theory.
背景メモ
- 本書『Analytic Combinatorics』は、アルゴリズム分析と組合せ論の分野で著名な研究者 Philippe Flajolet（INRIA）と Robert Sedgewick（プリンストン大）による体系的な教科書（2009年刊）。特に Flajolet は2011年に没しており、本書が彼の主著の一つとして知られる。
- 組合せ構造（木、文字列、グラフなど）を母関数（generating functions）を用いて解析し、そこに複素解析（特異点解析）を組み合わせることで、対象の漸近的な挙動（要素数 n が大きいときの個数の増え方など）を精密に導出する方法論を提示している。
- このアプローチは「解析的组合せ論（analytic combinatorics）」と呼ばれ、アルゴリズムの平均実行時間解析や確率的組合せ構造の研究において強力な道具として広く使われている。具体的には、クイックソートや二分探索木、ハッシュ表、ランダムグラフなどの解析に応用されてきた。
- Sedgewick は『アルゴリズム精選』シリーズの著者としても著名で、同書は理論と実践の橋渡し役としても評価が高い。フリーのPDFが公開されており、公式サイトから誰でもダウンロード可能。