母関数 I（通常型）― 数列を多項式で扱う

通常型母関数（OGF）の定義から積と畳み込みの関係，フィボナッチ数のBinet公式の導出，カタラン数・分割数の母関数を扱う．

2026年2月27日

1 通常型母関数の定義

定義 1 (通常型母関数).

数列

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

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

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

を

(a_{n})

の通常型母関数（ordinary generating function, OGF）という．

注意 2.

母関数は「形式的」べき級数であり，

x

に具体的な値を代入する必要はない．収束性は問わず，係数の代数的操作に意味がある．ただし，具体的な公式の導出に解析的議論を用いることもある．

例 3.

a_{n} = 1

（

n \geq 0

）の OGF は

\sum_{n = 0}^{\infty} x^{n} = \frac{1}{1 - x}

である．

a_{n} = n

の OGF は

\sum_{n = 0}^{\infty} n x^{n} = \frac{x}{( 1 - x ) ^{2}}

である．

2 積と畳み込み

定理 4.

数列

(a_{n})

，

(b_{n})

の OGF をそれぞれ

A (x)

，

B (x)

とする．積

C (x) = A (x) B (x)

の係数

c_{n}

は

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

で与えられる．これを

(a_{n})

と

(b_{n})

の畳み込み（convolution）という．

証明.

形式的べき級数の積の定義そのものである．

A (x) B (x) = \sum_{n} (\sum_{k = 0}^{n} a_{k} b_{n - k}) x^{n}

である． □

3 フィボナッチ数と Binet の公式

定義 5 (フィボナッチ数列).

F_{0} = 0

，

F_{1} = 1

，

F_{n} = F_{n - 1} + F_{n - 2}

（

n \geq 2

）で定まる数列をフィボナッチ数列という．

定理 6 (Binet の公式).

F_{n} = \frac{φ ^{n} - ψ ^{n}}{5}

ここで

φ = \frac{1 + 5}{2}

，

ψ = \frac{1 - 5}{2}

である．

証明.

F (x) = \sum_{n = 0}^{\infty} F_{n} x^{n}

とおく．漸化式

F_{n} = F_{n - 1} + F_{n - 2}

の両辺に

x^{n}

を掛けて

n \geq 2

で和をとると

F (x) - F_{1} x - F_{0} = x (F (x) - F_{0}) + x^{2} F (x)

整理して

F (x) (1 - x - x^{2}) = x

より

F (x) = \frac{x}{1 - x - x ^{2}}

．

部分分数分解を行う．

1 - x - x^{2} = - (x - (- φ^{- 1})) (x - (- ψ^{- 1}))

であるから

F (x) = \frac{1}{5} (\frac{1}{1 - φ x} - \frac{1}{1 - ψ x})

\frac{1}{1 - αx} = \sum_{n = 0}^{\infty} α^{n} x^{n}

より

F_{n} = \frac{φ ^{n} - ψ ^{n}}{5}

が得られる． □

4 カタラン数の母関数

定義 7 (カタラン数).

C_{n} = \frac{1}{n + 1} (n 2 n)

（

n \geq 0

）を第

n

カタラン数という．

定理 8.

カタラン数の OGF

C (x) = \sum_{n = 0}^{\infty} C_{n} x^{n}

は

C (x) = \frac{1 - 1 - 4 x}{2 x}

で与えられる．

証明.

カタラン数は漸化式

C_{n} = \sum_{k = 0}^{n - 1} C_{k} C_{n - 1 - k}

（

n \geq 1

，

C_{0} = 1

）を満たす．これは

C (x) = 1 + x C (x)^{2}

と書ける．二次方程式

x C^{2} - C + 1 = 0

を解いて

C (x) = \frac{1 \pm 1 - 4 x}{2 x}

．

C (0) = C_{0} = 1

の条件から

-

符号を選ぶ． □

5 分割数の母関数

定義 9 (分割数).

非負整数

n

を正整数の和として表す方法（順序を問わない）の数を分割数

p (n)

という．

定理 10 (Euler の分割数の母関数).

n = 0 \sum \infty p (n) x^{n} = k = 1 \prod \infty \frac{1}{1 - x ^{k}}

証明.

各正整数

k

を何個使うかを考える．

k

を

j

回使うことは

x^{kj}

に対応し，

\frac{1}{1 - x ^{k}} = j = 0 \sum \infty x^{kj}

である．すべての

k

にわたる積をとると，

x^{n}

の係数は

n

を正整数の和に分割する方法の数

p (n)

に等しい． □

注意 11.

分割数の漸化式は Euler の五角数定理

\prod_{k = 1}^{\infty} (1 - x^{k}) = \sum_{m = - \infty}^{\infty} (- 1)^{m} x^{m (3 m - 1) /2}

から導かれる．

母関数 I（通常型）― 数列を多項式で扱う

1 通常型母関数の定義

2 積と畳み込み

3 フィボナッチ数と Binet の公式

4 カタラン数の母関数

5 分割数の母関数

関連する「教科書の行間」記事

Share your expertise with the world

More from Folio公式

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

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

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

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