漸化式の数理（終）- 母関数の応用

こんにちは．

前回，前々回と続いた漸化式の数理シリーズですが，一旦今回で終わろうと思います．

終わりを飾るのにふさわしい題材として，Catalan 数 $CnC_n$ と組み合わせの総数 $nCk{}_n C_k$ を母関数によって求めてみます．

なお，母関数を使った解法は一通りではないので，よりスマートな方法や，逆に redundant な方法もあるはずです．

母関数の復習

まず前回の復習から始めましょう．

ここでは，数列の添字は整数全体を走ります．数列 $(fn)n⊂C(f_n)_n \subset \mathbb{C}$ に対して，その母関数を $G(Z)=∑fnZnG (Z) = \sum f_n Z^n$ で定義します．
このような和を（形式的）Laurent 級数と呼び，数列と Laurent 級数を同一視します．
有限項からなる Laurent 級数 $∑n=−kdfnZn\sum_{n = - k}^d f_n Z^n$ を（形式的）Laurent 多項式と呼びます．

Laurent 級数全体のなすベクトル空間を $C[ ⁣[Z±1] ⁣]\mathbb{C} [\![ Z^{\pm 1} ]\!]$ と書き，Laurent 多項式全体のなす $C\mathbb{C}$ 代数を $C[Z±1]\mathbb{C} [Z^{\pm 1}]$ と書きます．

このとき，$C[ ⁣[Z±1] ⁣]\mathbb{C} [\![ Z^{\pm 1} ]\!]$ は環にはなりませんが，$C[Z±1]\mathbb{C} [Z^{\pm 1}]$ 加群にはなります．この $C[Z±1]\mathbb{C} [Z^{\pm 1}]$ の作用を用いて漸化式を調べる，という手法が母関数の肝でした．

また，Laurent 級数 $f(Z)=∑fnZnf (Z) = \sum f_n Z^n$ の偏微分が $∂f(Z):=∑nfnZn−1\partial f (Z) := \sum n f_n Z^{n - 1}$ によって定義されます．

Laurent 級数の微分法

Laurent 級数 $f(Z)=∑fnZnf (Z) = \sum f_n Z^n$ の定数項を $(f(Z))0=f0(f (Z))_0 = f_0$ のように表すことにします．（これは $f(Z)/Zf (Z) / Z$ の留数と等しくなります．）

Taylor の定理

整級数の係数を計算するのに便利な，Taylor の定理を紹介しておきます．

これは微分積分学でおなじみの定理ですが，整級数 $f(Z)=∑fnZn∈C[ ⁣[Z] ⁣]f (Z) = \sum f_n Z^n \in \mathbb{C} [\![ Z ]\!]$ に対して

$$fn=1n!(∂nf)0 f_n = \frac{1}{n!} \left( \partial^n f \right)_0$$

が成り立つ，というものです．証明は $nn$ に関する帰納法で一瞬ですね．

この定理を言い換えれば，整級数 $f(Z)f (Z)$ の係数を求めたければ，何回か偏微分して $Z=0Z = 0$ を代入すれば良い，ということです．
なので，偏微分に関する計算規則さえ分かれば，通常の微分積分学と同じようにできます．

積の微分

積の微分について考える前に，まず積が定義できるような Laurent 級数のクラスを用意する必要があります．

Laurent 級数 $f(Z)=∑fnZnf (Z) = \sum f_n Z^n$ の位数

$$ord f=sup⁡{n∈Z⩾0∣f−n≠0} \mathrm{ord}\, f = \sup \{ n \in \mathbb{Z}_{\geqslant 0} \mid f_{- n} \neq 0 \}$$

が有限のとき（つまり $ord f<∞\mathrm{ord}\, f \lt \infty$ のとき），$f(Z)f (Z)$ は下に有界であると言います．
下に有界な Laurent 級数全体のなす部分 $C[Z±1]\mathbb{C} [Z^{\pm 1}]$ 加群を $C( ⁣(Z) ⁣)\mathbb{C} (\!( Z )\!)$ と書くと，これは整級数環 $C[ ⁣[Z] ⁣]\mathbb{C} [\![ Z ]\!]$ の商体です．

すると，下に有界な Laurent 級数 $f(Z),g(Z)∈C( ⁣(Z) ⁣)f (Z), g (Z) \in \mathbb{C} (\!( Z )\!)$ に対して $∂(fg)=(∂f)g+f∂g\partial (f g) = (\partial f) g + f \partial g$ が成り立ちます．

実際，$f(Z)=∑fnZnf (Z) = \sum f_n Z^n$，$g(Z)=∑gmZmg (Z) = \sum g_m Z^m$ と書けば，

$$(∂f)g=(∑nfnZn−1)(∑gmZm)=∑d(∑n+m=d+1nfngm)Zd,f∂g=(∑fnZn)(∑mgmZm−1)=∑d(∑n+m=d+1mfngm)Zd, (\partial f) g = \left( \sum n f_n Z^{n - 1} \right) \left( \sum g_m Z^m \right) = \sum_d \left( \sum_{n + m = d + 1} n f_n g_m \right) Z^d, \\ f \partial g = \left( \sum f_n Z^n \right) \left( \sum m g_m Z^{m - 1} \right) = \sum_d \left( \sum_{n + m = d + 1} m f_n g_m \right) Z^d, \\$$

なので

$$(∂f)g+f∂g=∑d(∑n+m=d+1(n+m)fngm)Zd=∂(fg) (\partial f) g + f \partial g = \sum_d \left( \sum_{n + m = d + 1} (n + m) f_n g_m \right) Z^d = \partial (f g)$$

が分かります．

特に，$nn$ に関する帰納法により $∂(fn)=nfn−1∂f\partial (f^n) = n f^{n - 1} \partial f$ も導かれます（$n∈Z⩾0n \in \mathbb{Z}_{\geqslant 0}$）．
次の商の微分を使えば，任意の $n∈Zn \in \mathbb{Z}$ で成り立つことも直ちに従います．

商の微分

下に有界な Laurent 級数 $0≠f(Z)=∑n=−k∞fnZn∈C( ⁣(Z) ⁣)0 \neq f (Z) = \sum_{n = - k}^\infty f_n Z^n \in \mathbb{C} (\!( Z )\!)$ に対して

$$∂(1f(Z))=−∂f(Z)f(Z)2 \partial \left( \frac{1}{f (Z)} \right) = - \frac{\partial f (Z)}{f (Z)^2}$$

となることを示します．
簡単のために，$g(Z):=1/f(Z)∈C( ⁣(Z) ⁣)g (Z) := 1 / f (Z) \in \mathbb{C} (\!( Z )\!)$ と置きます．

といっても証明は単純で，$f(Z)g(Z)=1f (Z) g (Z) = 1$ という等式を使うだけです．

両辺を偏微分すると $(∂f)g+f∂g=0(\partial f) g + f \partial g = 0$ となりますが，さらに両辺に $g(Z)g (Z)$ を掛ければ

$$∂g=gf∂g=−(∂f)g2 \partial g = g f \partial g = - (\partial f) g^2$$

となり，主張が従いました．

この等式と積の微分公式を合わせれば，下に有界な任意の Laurent 級数 $f(Z),g(Z)∈C( ⁣(Z) ⁣)f (Z), g (Z) \in \mathbb{C} (\!( Z )\!)$ に対して，$f(Z)≠0f (Z) \neq 0$ ならば

$$∂(g(Z)f(Z))=f(Z)∂g(Z)−g(Z)∂f(Z)f(Z)2 \partial \left( \frac{g (Z)}{f (Z)} \right) = \frac{f (Z) \partial g (Z) - g (Z) \partial f (Z)}{f (Z)^2}$$

も分かります．

冪根の微分

次に，級数 $f(Z)f (Z)$ の冪根 $f(Z)1/mf (Z)^{1 / m}$ の偏微分です（$m∈Z⩾1m \in \mathbb{Z}_{\geqslant 1}$）．

もちろん，任意の（下に有界な）Laurent 級数 $f(Z)f (Z)$ に対して，$g(Z)m=f(Z)g (Z)^m = f (Z)$ なる（下に有界な）Laurent 級数 $g(Z)g (Z)$ が存在するかどうかは非自明なので，その存在を最初に確かめます．

まず，下に有界な任意の Laurent 級数 $f(Z),g(Z),…,h(Z)∈C( ⁣(Z) ⁣)f (Z), g (Z), \dotsc, h (Z) \in \mathbb{C} (\!( Z )\!)$ に対して

$$f(Z)g(Z)⋯h(Z)=∑n=−∞∞(∑i+j+⋯+k=nfigj⋯hk)Zn f (Z) g (Z) \dotsm h (Z) = \sum_{n = - \infty}^\infty \left( \sum_{i + j + \dotsb + k = n} f_i g_j \dotsm h_k \right) Z^n$$

に注意しましょう．

$f(Z)=∑fnZn∈C[ ⁣[Z] ⁣]f (Z) = \sum f_n Z^n \in \mathbb{C} [\![ Z ]\!]$ を定数項が $00$ でないような整級数として，整級数 $g(Z)=∑gnZng (Z) = \sum g_n Z^n$ が $gm=fg^m = f$ を満たすための条件は

$$∑i1+⋯+im=ngi1⋯gim=fn(n⩾0) \sum_{i_1 + \dotsb + i_m = n} g_{i_1} \dotsm g_{i_m} = f_n \quad (n \geqslant 0)$$

です．

$n=0n = 0$ を見れば $g0m=f0g_0^m = f_0$ なので，$g0:=f01/mg_0 := f_0^{1/m}$ を任意に取ります．（ここでは，$f0f_0$ が正の実数のとき $g0g_0$ も正の実数となるようにしておきます． ）
次に $n=1n = 1$ は $g0m−1g1=f1g_0^{m - 1} g_1 = f_1$ となっているので，$g1=f1g01−mg_1 = f_1 g_0^{1 - m}$ と求まります．
以下同様に，$∑gi1⋯gim\sum g_{i_1} \dotsm g_{i_m}$ は $g0m−1gng_0^{m - 1} g_n$ と「$g0,…,gn−1g_0, \dotsc, g_{n - 1}$ までの関数」の和で書けるので，$gng_n$ が帰納的に求まります．

なお，一般の $f(Z)∈C( ⁣(Z) ⁣)f (Z) \in \mathbb{C} (\!( Z )\!)$ だと $mm$ 乗根が存在するとは限りません．実際，$f(Z)=Znf (Z) = Z^n$ は $nn$ が $mm$ の倍数であるとき，かつそのときに限り $mm$ 乗根を持ちます．

さて，定数項が零でないような整級数 $f(Z)∈C[ ⁣[Z] ⁣]f (Z) \in \mathbb{C} [\![ Z ]\!]$ とその $mm$ 乗根 $g(Z)=f(Z)1/m∈C[ ⁣[Z] ⁣]g (Z) = f (Z)^{1/m} \in \mathbb{C} [\![ Z ]\!]$ を取ります．

$gm=fg^m = f$ の両辺を微分すれば $mgm−1∂g=∂fm g^{m - 1} \partial g = \partial f$ なので，よく知られた公式 $∂g=(1/m)g1−m∂f\partial g = (1/m) g^{1 - m} \partial f$ を得ます．
ここから $∂gℓ=(ℓ/m)gℓ−m∂f\partial g^\ell = (\ell / m) g^{\ell - m} \partial f$ も従います（$ℓ∈Z\ell \in \mathbb{Z}$）．

具体例

以上の議論により，（下に有界な）Laurent 級数の微分は通常の微分と同じように計算できることが分かります．
ここでは実際に，以下で用いる $(1+Z)m(1 + Z)^m$ と $1−4Z\sqrt{1 - 4 Z}$ の Taylor 展開を求めてみましょう．

$f(Z)=(1+Z)mf (Z) = (1 + Z)^m$ と置けば，容易に分かるように

$$∂nf(Z)={m!(m−n)!(1+Z)m−n(0⩽n⩽m),0(n⩾m+1) \partial^n f (Z) = \begin{cases} \displaystyle \frac{m!}{(m - n)!} (1 + Z)^{m - n} & (0 \leqslant n \leqslant m), \\ 0 & (n \geqslant m + 1) \end{cases}$$

が成り立ちます．よって，Taylor の定理によって

$$(1+Z)m=∑n=0mm!n!(m−n)!Zn (1 + Z)^m = \sum_{n = 0}^m \frac{m!}{n! (m - n)!} Z^n$$

となります．

次に $f(Z)=1−4Zf (Z) = \sqrt{1 - 4 Z}$ の Taylor 展開ですが，

$$∂n+1f(Z)=−2⋅(2n)!n!f−1−2n(n⩾0) \partial^{n + 1} f (Z) = -2 \cdot \frac{(2 n)!}{n!} f^{-1 -2n} \quad (n \geqslant 0)$$

が $nn$ に関する帰納法で分かります．

実際，

$$∂f=12⋅f1−2∂(1−4Z)=−2f−1 \partial f = \frac{1}{2} \cdot f^{1 - 2} \partial (1 - 4 Z) = - 2 f^{-1}$$

なので，$n=0n = 0$ のときは成り立ちます．さらに，

$$∂(f−1−2n)=−1−2n2f(−1−2n)−2∂(1−4Z)=2(1+2n)f−3−2n \partial \left( f^{-1 -2n} \right) = \frac{-1 - 2n}{2} f^{(-1 - 2n) - 2} \partial ( 1 - 4 Z) = 2 (1 + 2 n) f^{-3 - 2n}$$

なので一般の $nn$ でも成り立ちます．

よって，Taylor の定理から

$$1−4Z=1−2∑n=0∞(2n)!n!(n+1)!Zn+1 \sqrt{1 - 4 Z} = 1 - 2 \sum_{n = 0}^\infty \frac{(2 n)!}{n! (n + 1)!} Z^{n + 1}$$

を得ます．

Catalan 数

Catalan 数 $CnC_n$ の漸化式を見てみましょう：

$${C0=1Cn+1=∑i=0nCiCn−i=∑i+j=nCiCj(n⩾0). \begin{cases} C_0 = 1 \\ \displaystyle C_{n + 1} = \sum_{i = 0}^n C_i C_{n - i} = \sum_{i + j = n} C_i C_j & (n \geqslant 0). \end{cases}$$

これは $CiCjC_i C_j$ という項を含んでいるので，非線形漸化式です．

Catalan 数の母関数を $G(Z)=∑n⩾0CnZn∈C[ ⁣[Z] ⁣]G (Z) = \sum_{n \geqslant 0} C_n Z^n \in \mathbb{C} [\![ Z ]\!]$ と置きます．Catalan 数の漸化式には "対角線" つまり $CiCn−iC_i C_{n - i}$ の形の項しか現れないことに注意すれば，右辺は $G(Z)2G (Z)^2$ を使って書けるのでは，と予想できます．

実際，

$$G(Z)2=∑n⩾0(∑i+j=nCiCj)Zn=∑n⩾0Cn+1Zn G (Z)^2 = \sum_{n \geqslant 0} \left( \sum_{i + j = n} C_i C_j \right) Z^n = \sum_{n \geqslant 0} C_{n + 1} Z^n$$

となるので，$C( ⁣(Z) ⁣)\mathbb{C} (\!( Z )\!)$ における方程式 $G(Z)2=(G(Z)−1)/ZG (Z)^2 = (G (Z) - 1) / Z$ を得ます．$C( ⁣(Z) ⁣)\mathbb{C} (\!( Z )\!)$ は標数 $00$ の体なので "2次方程式の解の公式" が成立し，

$$G(Z)=1±1−4Z2Z G (Z) = \frac{1 \pm \sqrt{1 - 4 Z}}{2 Z}$$

となります．

ここで，上で求めた

$$1−4Z=1−2∑n=0∞(2n)!n!(n+1)!Zn+1 \sqrt{1 - 4 Z} = 1 - 2 \sum_{n = 0}^\infty \frac{(2 n)!}{n! (n + 1)!} Z^{n + 1}$$

を代入すれば

$$G(Z)=∑n⩾0(2n)!n!(n+1)!Zn G (Z) = \sum_{n \geqslant 0} \frac{(2 n)!}{n! (n + 1)!} Z^n$$

となり，Catalan 数の一般項が求まりました．
（$±\pm$ の正負について，もし $++$ なら $1+1−4Z1 + \sqrt{1 - 4 Z}$ の定数項が $00$ でなくなるので，$(1+1−4Z)/2Z(1 + \sqrt{1 - 4 Z}) / 2 Z$ が整級数ではなくなってしまいます．$G(Z)G (Z)$ は整級数なので $G(Z)≠(1+1−4Z)/2ZG (Z) \neq (1 + \sqrt{1 - 4 Z}) / 2 Z$ となり，矛盾します．）

組み合わせの総数

組み合わせの総数 $nCk{}_n C_k$ の満たす漸化式は

$${0C0=δk,0(k∈Z),nCk=n−1Ck+n−1Ck−1(n⩾1,k∈Z) \begin{cases} {}_0 C_0 = \delta_{k, 0} & (k \in \mathbb{Z}), \\ {}_n C_k = {}_{n - 1} C_k + {}_{n - 1} C_{k - 1} & (n \geqslant 1, k \in \mathbb{Z}) \end{cases}$$

でした．各 $(nCk)k({}_n C_k)_k$ から定まる母関数を $Gn(Z)=∑nCkZk∈C[ ⁣[Z±1] ⁣]G_n (Z) = \sum {}_n C_k Z^k \in \mathbb{C} [\![ Z^{\pm 1} ]\!]$ と置きます．漸化式は $Gn(Z)=(1+Z)Gn−1(Z)G_n (Z) = (1 + Z) G_{n - 1} (Z)$ を意味するので，

$$Gn(Z)=(1+Z)nG0(Z)=(1+Z)n G_n (Z) = (1 + Z)^n G_0 (Z) = (1 + Z)^n$$

となり，すでに $(1+Z)n(1 + Z)^n$ の Taylor 展開は求まっていたので，結局

$$Gn(Z)=∑k=0nn!k!(n−k)!Zk G_n (Z) = \sum_{k = 0}^n \frac{n!}{k! (n - k)!} Z^k$$

が分かりました．

終わりに

形式的母関数の理論，いかがでしたでしょうか．
母関数というのは結局のところただの数列なので，級数の収束という概念がありません．収束半径を求めなくて良いのはとても嬉しいですね．

形式的 Laurent 級数は母関数だけでなく様々な場面で出てくるのですが，興味があればぜひ学んでみてください．

また面白い数学があれば紹介したいと思います．が，プログラミングと結びつけるのもなかなか大変です．
まあそういうところも面白いのですが．