通常生成関数と指数生成関数

通常生成関数はラベルなしの数え上げのための数列を符号化し、指数生成関数はラベル付き構造を扱う。どちらも組み合わせ的構成を代数に変換する。

Definition

数列の通常生成関数は、その数列を係数とするべき級数である。指数生成関数は、各係数を階乗で割ったものであり、ラベル付きオブジェクトの数え上げに適した形式である。

Scope

このトピックでは、2種類の主要な生成関数、形式的べき級数の枠組み、および組み合わせ的構成（非交和、積、列、集合、サイクル）を級数上の操作に直接マッピングする記号的方法を紹介する。また、通常生成関数と指数生成関数を区別する積の公式についても解説する。

Core questions

• 通常生成関数と指数生成関数はいつ使い分けるべきか？
• 組み合わせ的演算は、級数上の代数的演算にどのように対応するのか？
• 指数生成関数の乗算がラベル付きマージを数え上げるのはなぜか？
• 記号的方法は、数え上げ公式の導出をどのように自動化するのか？

Key concepts

• 通常生成関数
• 指数生成関数
• 形式的べき級数
• 畳み込みと積の法則
• 記号的方法
• ラベル付き構造とラベルなし構造

Key theories

記号的方法

フラジョレとセジウィックの記号的方法は、オブジェクトのクラスに対する組み合わせ的構成を、それらの生成関数に対する操作に変換する体系的な辞書を提供し、構造記述から数え上げ公式を読み取ることができるようにする。

生成関数の積の法則

2つの通常生成関数の積は、合計サイズによって順序付けられたペアを列挙する一方、指数生成関数の積はラベル付きマージを列挙する。この区別がどちらの形式を使用するかを決定する。

Clinical relevance

記号的方法は、データ構造とアルゴリズムの列挙と平均ケース解析を自動化し、指数生成関数は、計算機科学で生じるラベル付き木、順列、集合の分割を数え上げるための自然なツールである。

History

組み合わせ的構成と生成関数操作との間の体系的な対応関係は、オイラーとポリアによって予見され、フラジョレとセジウィックによって形式的な記号的方法へと発展させられた。

Key figures

• Philippe Flajolet
• Robert Sedgewick
• Richard P. Stanley

Seminal works

• flajolet2009
• stanley2011

Frequently asked questions

指数生成関数はいつ好まれるのか？

ラベル付き木や順列のように、数え上げられるオブジェクトが識別可能なラベルを持つ場合、指数生成関数の階乗による重み付けにより、その積が正しく数え上げを行う。

生成関数における変数は意味を持つのか？

形式的な設定では、それはサイズを示すプレースホルダーである。解析的手法が適用される場合にのみ、数値を持つ複素変数として扱われる。