母関数 II（指数型）― ラベル付き構造の数え上げ

指数型母関数（EGF）の定義と積がラベル付き合併に対応することを示し，スターリング数，ベル数，ケイリーの公式を導出する．

2026年2月27日

1 指数型母関数の定義

定義 1 (指数型母関数).

数列

(a_{n})_{n \geq 0}

に対して，形式的べき級数

\hat{A} (x) = n = 0 \sum \infty a_{n} \frac{x ^{n}}{n !}

を

(a_{n})

の指数型母関数（exponential generating function, EGF）という．

注意 2.

OGF が「非ラベル構造」の数え上げに適しているのに対し，EGF は「ラベル付き構造」の数え上げに適している．この違いは積の解釈に現れる．

例 3.

a_{n} = 1

（

n \geq 0

）の EGF は

\sum_{n \geq 0} x^{n} / n! = e^{x}

である．

a_{n} = n!

（順列の数）の EGF は

\sum_{n \geq 0} x^{n} = 1/ (1 - x)

である．

2 積とラベル付き合併

定理 4 (EGF の積の解釈).

数列

(a_{n})

，

(b_{n})

の EGF をそれぞれ

\hat{A} (x)

，

\hat{B} (x)

とする．積

\hat{C} (x) = \hat{A} (x) \hat{B} (x)

の係数

c_{n}

は

c_{n} = k = 0 \sum n (k n) a_{k} b_{n - k}

で与えられる．

証明.

\hat{A} (x) \hat{B} (x) = n = 0 \sum \infty (k = 0 \sum n \frac{a _{k}}{k !} \cdot \frac{b _{n - k}}{( n - k )!}) x^{n} = n = 0 \sum \infty \frac{1}{n !} (k = 0 \sum n (k n) a_{k} b_{n - k}) \frac{x ^{n}}{1}

であるが，

x^{n} / n!

でまとめれば

c_{n} = \sum_{k = 0}^{n} (k n) a_{k} b_{n - k}

． □

注意 5.

(k n)

の出現は，

n

個のラベルを2群に分割して一方に

a_{k}

通り，他方に

b_{n - k}

通りの構造を入れることに対応する．これが「ラベル付き合併」の意味である．

3 第一種スターリング数

定義 6 (第一種スターリング数).

n

個の元の順列を

k

個の巡回置換の積に分解する方法の数を符号なし第一種スターリング数

c (n, k)

または

[\frac{n}{k}]

と書く．符号付き第一種スターリング数は

s (n, k) = (- 1)^{n - k} c (n, k)

で定義される．

定理 7.

k = 0 \sum n c (n, k) x^{k} = x (x + 1) (x + 2) \dots (x + n - 1) = x^{(n)}

ここで

x^{(n)}

は上昇階乗べき（rising factorial）である．

証明.

n

に関する帰納法で示す．

n = 0

のとき両辺は

1

（空積）．

x^{(n)} = x^{(n - 1)} (x + n - 1)

より，

c (n, k) = c (n - 1, k - 1) + (n - 1) c (n - 1, k)

という漸化式が得られ，これは

n

個の元の順列において元

n

が新しい巡回置換を形成する（

c (n - 1, k - 1)

通り）か，既存の巡回置換の

n - 1

箇所のいずれかに挿入される（

(n - 1) c (n - 1, k)

通り）かに対応し，組合せ的にも成立する． □

4 第二種スターリング数の EGF

定理 8.

第二種スターリング数の EGF は

n = k \sum \infty S (n, k) \frac{x ^{n}}{n !} = \frac{( e ^{x} - 1 ) ^{k}}{k !}

である．

証明.

e^{x} - 1 = \sum_{n = 1}^{\infty} x^{n} / n!

は空でないラベル付き集合の EGF である．

(e^{x} - 1)^{k} / k!

は

k

個の空でないラベル付き集合への分割（順序を無視）の EGF であり，これは第二種スターリング数の定義そのものである． □

5 ベル数

定義 9 (ベル数).

n

元集合のすべての分割の総数をベル数

B_{n}

という．すなわち

B_{n} = \sum_{k = 0}^{n} S (n, k)

．

定理 10.

n = 0 \sum \infty B_{n} \frac{x ^{n}}{n !} = e^{e^{x} - 1}

証明.

B_{n} = \sum_{k} S (n, k)

であるから，

n = 0 \sum \infty B_{n} \frac{x ^{n}}{n !} = k = 0 \sum \infty \frac{( e ^{x} - 1 ) ^{k}}{k !} = e^{e^{x} - 1}

□

6 ケイリーの公式と Prüfer 列

定理 11 (ケイリーの公式（EGF による証明）).

n

頂点のラベル付き木の個数は

n^{n - 2}

である．

証明.

ラベル付き根付き木の EGF を

T (x)

とする．根付き木は根と，根に接続する部分木（再び根付き木）の列で特徴づけられるので，

T (x) = x e^{T (x)}

を満たす．Lagrange の反転公式より

[x^{n}] T (x) = \frac{1}{n} [y^{n - 1}] e^{n y} = \frac{1}{n} \cdot \frac{n ^{n - 1}}{( n - 1 )!} = \frac{n ^{n - 1}}{n !}

したがってラベル付き根付き木の数は

n^{n - 1}

である．根の選び方が

n

通りあるので，ラベル付き（根なし）木の数は

n^{n - 1} / n \cdot 1 = n^{n - 2}

となる．

より直接的には，Prü □

EGF の手法は，ラベル付き構造の数え上げにおいて極めて強力であり，Lagrange の反転公式や合成公式と組み合わせることで多くの組合せ恒等式を系統的に導出できる．

組合せ論離散数学教科書母関数 EGF

Folio公式

数学の「教科書が書かない行間」をLaTeXで．Folio公式アカウントです．

0 フォロワー·105 記事

母関数 II（指数型）― ラベル付き構造の数え上げ

1 指数型母関数の定義

2 積とラベル付き合併

3 第一種スターリング数

4 第二種スターリング数の EGF

5 ベル数

6 ケイリーの公式と Prüfer 列

あなたの専門知識を世界に発信しよう

Folio公式の他の記事

Folio LaTeXの基本 ― 標準LaTeXとの違いと始め方

カタラン数はなぜどこにでも現れるのか ― 括弧列・二分木・格子経路の不思議な一致

漸化式と母関数 ― 数列を「関数」にすると何が見えるか

包除原理はなぜ「足して引いて」を繰り返すのか ― ベン図からメビウス関数へ