第 16 章 母関数

母関数 (generating function) は離散数学における最も奇妙で最も有用な概念の一つである。一言で言えば、母関数は列に関する問題を代数に関する問題に変換する。代数的なツールは数多く知られているので、この変換によって問題に対する様々な異なるアプローチが可能になる。母関数を使うと多種多様な数え上げ問題を解くことができる。

組合せ数学でよく登場する母関数は「通常型 (ordinary)」「指数型 (exponential)」「Dirichletディリクレ 型 (Dirichlet)」といった種類に分けられる。また、制御理路や信号処理で用いられる Z 変換 (Z-transform) は通常型の母関数と密接な関係を持つ。しかし、母関数の有用性を示すには通常型を見れば十分なので、本章では通常型の母関数だけを扱う。そこで、これから「母関数」は「通常型の母関数」を意味すると定める。本章では母関数を使って特定の種類の数え上げ問題を解く方法、そして線形再帰関数 (linear-recursive function) を表す単純な式を見つける方法を見ながら、母関数という巨大な分野の基本的な考え方を紹介する。

目次