組合せ論と代数 ― 形式的べき級数と代数的組合せ論入門

形式的べき級数環$\mathbb{Q}[[x]]$の代数構造，逆元・合成・微分，P-recursive列，Lagrangeの反転公式，WZ法と超幾何級数を紹介する．

2026年2月27日

1 形式的べき級数環

定義 1 (形式的べき級数環).

Q

上の形式的べき級数環

Q [[x]]

とは，形式的な無限和

f (x) = n = 0 \sum \infty a_{n} x^{n} (a_{n} \in Q)

全体の集合に，各係数ごとの加法と畳み込みによる乗法を定めた環である．

定理 2.

Q [[x]]

は整域である．すなわち

f (x) \neq = 0

かつ

g (x) \neq = 0

ならば

f (x) g (x) \neq = 0

である．

証明.

f (x) = \sum a_{n} x^{n}

，

g (x) = \sum b_{n} x^{n}

とし，

a_{p} \neq = 0

，

b_{q} \neq = 0

となる最小の

p, q

をとる．

f (x) g (x)

の

x^{p + q}

の係数は

\sum_{k = 0}^{p + q} a_{k} b_{p + q - k}

であるが，

k < p

のとき

a_{k} = 0

，

k > p

のとき

p + q - k < q

より

b_{p + q - k} = 0

であるから，

a_{p} b_{q} \neq = 0

のみが残る． □

2 逆元

定理 3.

f (x) = \sum_{n = 0}^{\infty} a_{n} x^{n} \in Q [[x]]

が乗法逆元を持つための必要十分条件は

a_{0} \neq = 0

である．

証明.

(\Rightarrow)

f (x) g (x) = 1

ならば定数項同士の積が

1

であるから

a_{0} \neq = 0

．

(\Leftarrow)

g (x) = \sum b_{n} x^{n}

を

f (x) g (x) = 1

で定める．

b_{0} = 1/ a_{0}

，

n \geq 1

に対して

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

より

b_{n} = - \frac{1}{a _{0}} k = 1 \sum n a_{k} b_{n - k}

で帰納的に一意に定まる． □

3 合成

定義 4 (合成).

f (x) = \sum a_{n} x^{n}

，

g (x) = \sum_{n \geq 1} b_{n} x^{n}

（

g

の定数項が

0

）に対して，合成（composition）

f (g (x)) = \sum_{n = 0}^{\infty} a_{n} g (x)^{n}

は

Q [[x]]

の元として well-defined である．

定理 5.

g (x) = \sum_{n \geq 1} b_{n} x^{n}

が合成逆

\overset{g}{ˉ}

（

g (\overset{g}{ˉ} (x)) = \overset{g}{ˉ} (g (x)) = x

）を持つための必要十分条件は

b_{1} \neq = 0

である．

証明.

\overset{g}{ˉ} (x) = \sum c_{n} x^{n}

（

c_{0} = 0

）を

g (\overset{g}{ˉ} (x)) = x

から帰納的に求める．

x

の係数を比較して

b_{1} c_{1} = 1

より

c_{1} = 1/ b_{1}

（

b_{1} \neq = 0

が必要十分）．高次の係数も逐次一意に定まる． □

4 形式的微分

定義 6 (形式的微分).

D (n = 0 \sum \infty a_{n} x^{n}) = n = 1 \sum \infty n a_{n} x^{n - 1}

を形式的微分という．

D

は

Q [[x]]

上の導分（derivation）であり，

D (f g) = D (f) g + f D (g)

を満たす．

5 P-recursive 列

定義 7 (P-recursive 列（holonomic 列）).

数列

(a_{n})

がP-recursive（holonomic）であるとは，

n

の多項式

p_{0} (n), p_{1} (n), \dots, p_{d} (n)

（

p_{d}

は恒等的に

0

でない）が存在して

p_{d} (n) a_{n + d} + p_{d - 1} (n) a_{n + d - 1} + \dots + p_{0} (n) a_{n} = 0

が十分大きな

n

で成り立つことをいう．

例 8.

a_{n} = n!

は

a_{n + 1} = (n + 1) a_{n}

，すなわち

a_{n + 1} - (n + 1) a_{n} = 0

を満たすので P-recursive である．

a_{n} = (n 2 n)

も P-recursive である（

(n + 1) a_{n + 1} = 2 (2 n + 1) a_{n}

）．

注意 9.

P-recursive 列の母関数は微分方程式（線形 ODE with polynomial coefficients）を満たすD-finite 級数と呼ばれる．P-recursive 列のクラスは加法・乗法（Hadamard 積）・畳み込みで閉じており，組合せ論で現れる多くの数列がこのクラスに属する．

6 Lagrange の反転公式

定理 10 (Lagrange の反転公式).

ϕ (x) \in Q [[x]]

，

ϕ (0) \neq = 0

とする．

f (x) = x ϕ (f (x))

を満たす形式的べき級数

f (x)

（

f (0) = 0

）が一意に存在し，

[x^{n}] f (x) = \frac{1}{n} [y^{n - 1}] ϕ (y)^{n}

が成り立つ．より一般に，任意の

h (x) \in Q [[x]]

に対して

[x^{n}] h (f (x)) = \frac{1}{n} [y^{n - 1}] h^{'} (y) ϕ (y)^{n}

証明.

f (x) = x ϕ (f (x))

より

x = f / ϕ (f)

．

g = f

を新しい変数と思えば

x (g) = g / ϕ (g)

であり，

[x^{n}] h (f (x))

は

x

と

g

の変数変換のヤコビアンを用いて計算できる．

形式的には，

[x^{n}] h (f) = \frac{1}{n} [x^{n - 1}] h^{'} (x) ϕ (x)^{n}

を留数計算の類似で示す．

[x^{n}] h (f) = \frac{1}{2 πi} \oint h (f (x)) x^{- n - 1} d x

．

x = g / ϕ (g)

と置換すると

d x = (ϕ (g) - g ϕ^{'} (g)) / ϕ (g)^{2} d g

であり，整理すれば結論が得られる（形式的べき級数の枠組みでは係数の比較で直接証明できる）． □

例 11.

カタラン数：

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

（

ϕ (y) = (1 + y)^{2}

）より

[x^{n}] f (x) = \frac{1}{n} [y^{n - 1}] (1 + y)^{2 n} = \frac{1}{n} (n - 1 2 n) = \frac{1}{n + 1} (n 2 n) = C_{n}

．

7 WZ 法と超幾何級数

定義 12 (超幾何項).

数列

(t_{k})

が超幾何項（hypergeometric term）であるとは，

t_{k + 1} / t_{k}

が

k

の有理関数であることをいう．

定義 13 (超幾何級数).

_{p} F_{q} (a_{1}, \dots, a_{p} b_{1}, \dots, b_{q}; x) = k = 0 \sum \infty \frac{( a _{1} ) _{k} \dots ( a _{p} ) _{k}}{( b _{1} ) _{k} \dots ( b _{q} ) _{k}} \frac{x ^{k}}{k !}

を超幾何級数という．ここで

(a)_{k} = a (a + 1) \dots (a + k - 1)

はポッホハマー記号（上昇階乗）である．

定理 14 (WZ 法の原理（Wilf–Zeilberger, 1990年）).

等式

\sum_{k} F (n, k) = c

（定数）を証明するには，

G (n, k) = R (n, k) F (n, k)

なる有理関数

R (n, k)

（WZ 証明証書）を見つけて

F (n + 1, k) - F (n, k) = G (n, k + 1) - G (n, k)

が成り立つことを確認すれば十分である．

k

について和をとると右辺は望遠鏡和で

0

となり，

\sum_{k} F (n + 1, k) = \sum_{k} F (n, k)

が得られる．

注意 15.

Gosper のアルゴリズムにより，超幾何項の不定和分を有限的に計算できるかどうかを判定でき，WZ ペアの存在を確認できる．Zeilberger のアルゴリズム（creative telescoping）は超幾何和に対する漸化式を自動的に発見する．これらの手法は計算機代数による組合せ等式の自動証明の基盤をなす．

例 16.

Vandermonde の畳み込み

\sum_{k = 0}^{r} (k m) (r - k n) = (r m + n)

は

_{2} F_{1} (- m, - r; n - r + 1; 1) = (r m + n) / (r n)

（Chu–Vandermonde の等式）の特殊な場合であり，WZ 法により機械的に証明できる．

組合せ論離散数学教科書形式的べき級数代数的組合せ論

Folio公式

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

0 followers·105 articles

組合せ論と代数 ― 形式的べき級数と代数的組合せ論入門

1 形式的べき級数環

2 逆元

3 合成

4 形式的微分

5 P-recursive 列

6 Lagrange の反転公式

7 WZ 法と超幾何級数

Share your expertise with the world

More from Folio公式

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

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

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

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