1 漸化式と線形漸化式 定義 1.1 (漸化式・定数係数線形漸化式・初期条件). 数列( a n ) n ≥ 0 (a_n)_{n\ge 0} ( a n ) n ≥ 0 漸化式 とは、各n n n a n a_n a n a 0 , … , a n − 1 a_0,\dots,a_{n-1} a 0 , … , a n − 1
とくに、定数c 1 , … , c k ∈ C c_1,\dots,c_k \in \C c 1 , … , c k ∈ C c k ≠ 0 c_k \neq 0 c k = 0 n ≥ k n \ge k n ≥ k
a n = c 1 a n − 1 + c 2 a n − 2 + ⋯ + c k a n − k a_n = c_1 a_{n-1} + c_2 a_{n-2} + \cdots + c_k a_{n-k} a n = c 1 a n − 1 + c 2 a n − 2 + ⋯ + c k a n − k の形をもつものを、k k k a n a_n a n k k k a 0 , a 1 , … , a k − 1 a_0, a_1, \dots, a_{k-1} a 0 , a 1 , … , a k − 1 初期条件 といいます。c k ≠ 0 c_k \neq 0 c k = 0 k k k a n − k a_{n-k} a n − k
多項式
χ ( x ) = x k − c 1 x k − 1 − c 2 x k − 2 − ⋯ − c k \chi(x) = x^k - c_1 x^{k-1} - c_2 x^{k-2} - \cdots - c_k χ ( x ) = x k − c 1 x k − 1 − c 2 x k − 2 − ⋯ − c k をこの漸化式の特性多項式 、方程式χ ( x ) = 0 \chi(x)=0 χ ( x ) = 0 特性方程式 とよびます。
初期条件a 0 , … , a k − 1 a_0,\dots,a_{k-1} a 0 , … , a k − 1 a k , a k + 1 , … a_k, a_{k+1},\dots a k , a k + 1 , …
補題 1.2 (初期値による決定). k k k ( a n ) n ≥ 0 (a_n)_{n\ge 0} ( a n ) n ≥ 0 ( a 0 , … , a k − 1 ) ∈ C k (a_0,\dots,a_{k-1})\in\C^k ( a 0 , … , a k − 1 ) ∈ C k ( a 0 , … , a k − 1 ) ∈ C k (a_0,\dots,a_{k-1})\in\C^k ( a 0 , … , a k − 1 ) ∈ C k
証明. 存在は、n ≥ k n \ge k n ≥ k a n : = c 1 a n − 1 + ⋯ + c k a n − k a_n := c_1 a_{n-1}+\cdots+c_k a_{n-k} a n := c 1 a n − 1 + ⋯ + c k a n − k ( a n ) , ( a n ′ ) (a_n),(a_n') ( a n ) , ( a n ′ ) 0 ≤ n ≤ k − 1 0\le n\le k-1 0 ≤ n ≤ k − 1 a n = a n ′ a_n=a_n' a n = a n ′ n ≥ k n\ge k n ≥ k 0 ≤ j < n 0\le j<n 0 ≤ j < n j j j a j = a j ′ a_j=a_j' a j = a j ′
a n = c 1 a n − 1 + ⋯ + c k a n − k = c 1 a n − 1 ′ + ⋯ + c k a n − k ′ = a n ′ a_n=c_1a_{n-1}+\cdots+c_ka_{n-k}
=c_1a_{n-1}'+\cdots+c_ka_{n-k}'=a_n' a n = c 1 a n − 1 + ⋯ + c k a n − k = c 1 a n − 1 ′ + ⋯ + c k a n − k ′ = a n ′ です。したがって、n n n n ≥ 0 n\ge0 n ≥ 0 a n = a n ′ a_n=a_n' a n = a n ′ §A3.10 定理 3.1 ）。▨
2 特性方程式による解法 補題 2.1 (因数分解された差分作用素の核). r 1 , … , r s ∈ C r_1,\dots,r_s\in\C r 1 , … , r s ∈ C m 1 , … , m s m_1,\dots,m_s m 1 , … , m s a = ( a n ) n ≥ 0 a=(a_n)_{n\ge 0} a = ( a n ) n ≥ 0
( D r a ) n : = a n + 1 − r a n (D_r a)_n:=a_{n+1}-r a_n ( D r a ) n := a n + 1 − r a n と定めます。このとき
D r 1 m 1 ⋯ D r s m s a = 0 D_{r_1}^{m_1}\cdots D_{r_s}^{m_s}a=0 D r 1 m 1 ⋯ D r s m s a = 0 であることと、零多項式または次数がm i m_i m i p i p_i p i
a n = ∑ i = 1 s p i ( n ) r i n ( n ≥ 0 ) a_n=\sum_{i=1}^{s}p_i(n)r_i^{\,n}\qquad(n\ge 0) a n = i = 1 ∑ s p i ( n ) r i n ( n ≥ 0 ) と表されることは同値です。さらに、この表示の多項式p 1 , … , p s p_1,\dots,p_s p 1 , … , p s
証明. E E E ( E a ) n = a n + 1 (Ea)_n=a_{n+1} ( E a ) n = a n + 1 I I I D r = E − r I D_r=E-rI D r = E − r I D r D_r D r
まず根が一つの場合を示します。D r m a = 0 D_r^m a=0 D r m a = 0 b n = r − n a n b_n=r^{-n}a_n b n = r − n a n
( D r a ) n = r n + 1 ( b n + 1 − b n ) (D_r a)_n=r^{n+1}(b_{n+1}-b_n) ( D r a ) n = r n + 1 ( b n + 1 − b n ) であり、前進差分を( Δ b ) n = b n + 1 − b n (\Delta b)_n=b_{n+1}-b_n ( Δ b ) n = b n + 1 − b n
( D r m a ) n = r n + m ( Δ m b ) n (D_r^m a)_n=r^{n+m}(\Delta^m b)_n ( D r m a ) n = r n + m ( Δ m b ) n を得ます。よってD r m a = 0 D_r^m a=0 D r m a = 0 Δ m b = 0 \Delta^m b=0 Δ m b = 0
Δ m b = 0 \Delta^m b=0 Δ m b = 0 b n b_n b n n n n m m m m m m m = 1 m=1 m = 1 Δ b = 0 \Delta b=0 Δ b = 0 b n = b 0 b_n=b_0 b n = b 0 m > 1 m>1 m > 1 d = Δ b d=\Delta b d = Δ b Δ m − 1 d = 0 \Delta^{m-1}d=0 Δ m − 1 d = 0 c 1 , … , c m − 1 c_1,\dots,c_{m-1} c 1 , … , c m − 1
d n = ∑ j = 0 m − 2 c j + 1 ( n j ) d_n=\sum_{j=0}^{m-2}c_{j+1}\binom{n}{j} d n = j = 0 ∑ m − 2 c j + 1 ( j n ) と書けます。c 0 = b 0 c_0=b_0 c 0 = b 0 ∑ t = 0 n − 1 ( t j ) = ( n j + 1 ) \sum_{t=0}^{n-1}\binom{t}{j}=\binom{n}{j+1} ∑ t = 0 n − 1 ( j t ) = ( j + 1 n )
b n = b 0 + ∑ t = 0 n − 1 d t = ∑ j = 0 m − 1 c j ( n j ) b_n=b_0+\sum_{t=0}^{n-1}d_t
=\sum_{j=0}^{m-1}c_j\binom{n}{j} b n = b 0 + t = 0 ∑ n − 1 d t = j = 0 ∑ m − 1 c j ( j n ) となります。この表示はc 0 = b 0 c_0=b_0 c 0 = b 0 d = Δ b d=\Delta b d = Δ b m m m Δ \Delta Δ m m m
次に根の個数s s s s = 1 s=1 s = 1 s > 1 s>1 s > 1
ψ ( x ) = ∏ i = 2 s ( x − r i ) m i , Ψ = ψ ( E ) \psi(x)=\prod_{i=2}^{s}(x-r_i)^{m_i},\qquad \Psi=\psi(E) ψ ( x ) = i = 2 ∏ s ( x − r i ) m i , Ψ = ψ ( E ) とおきます。仮定からD r 1 m 1 ( Ψ a ) = 0 D_{r_1}^{m_1}(\Psi a)=0 D r 1 m 1 ( Ψ a ) = 0 m 1 m_1 m 1 q q q
( Ψ a ) n = q ( n ) r 1 n (\Psi a)_n=q(n)r_1^{\,n} ( Ψ a ) n = q ( n ) r 1 n となります。
ここで、次数がm 1 m_1 m 1 q q q p p p
Ψ ( p ( n ) r 1 n ) = q ( n ) r 1 n \Psi\bigl(p(n)r_1^{\,n}\bigr)=q(n)r_1^{\,n} Ψ ( p ( n ) r 1 n ) = q ( n ) r 1 n となることを示します。ψ ( x ) = ∑ t γ t x t \psi(x)=\sum_t\gamma_t x^t ψ ( x ) = ∑ t γ t x t r 1 n r_1^n r 1 n
∑ t γ t r 1 t p ( n + t ) \sum_t\gamma_t r_1^t p(n+t) t ∑ γ t r 1 t p ( n + t ) です。p p p d d d A ≠ 0 A\ne0 A = 0
A ∑ t γ t r 1 t = A ψ ( r 1 ) A\sum_t\gamma_t r_1^t=A\psi(r_1) A t ∑ γ t r 1 t = A ψ ( r 1 ) です。根が相異なるためψ ( r 1 ) = ∏ i = 2 s ( r 1 − r i ) m i ≠ 0 \psi(r_1)=\prod_{i=2}^{s}(r_1-r_i)^{m_i}\ne0 ψ ( r 1 ) = ∏ i = 2 s ( r 1 − r i ) m i = 0 q = 0 q=0 q = 0 p = 0 p=0 p = 0 q ≠ 0 q\ne0 q = 0 q q q p p p p p p p p p p p p
このp p p Ψ ( a − p ( n ) r 1 n ) = 0 \Psi(a-p(n)r_1^n)=0 Ψ ( a − p ( n ) r 1 n ) = 0 a − p ( n ) r 1 n a-p(n)r_1^n a − p ( n ) r 1 n i = 2 , … , s i=2,\dots,s i = 2 , … , s p i ( n ) r i n p_i(n)r_i^n p i ( n ) r i n D r i m i D_{r_i}^{m_i} D r i m i
最後に表示の一意性を示します。∑ i p i ( n ) r i n = 0 \sum_i p_i(n)r_i^n=0 ∑ i p i ( n ) r i n = 0 i i i ∏ ℓ ≠ i D r ℓ m ℓ \prod_{\ell\ne i}D_{r_\ell}^{m_\ell} ∏ ℓ = i D r ℓ m ℓ ℓ ≠ i \ell\ne i ℓ = i p i ( n ) r i n p_i(n)r_i^n p i ( n ) r i n ψ ( r i ) ≠ 0 \psi(r_i)\ne0 ψ ( r i ) = 0 p i = 0 p_i=0 p i = 0 i i i p i p_i p i ▨
定理 2.2 (相異なる特性根に対する一般解). 定義 1.1 のk k k χ \chi χ r 1 , … , r k r_1,\dots,r_k r 1 , … , r k ( a n ) (a_n) ( a n )
a n = A 1 r 1 n + A 2 r 2 n + ⋯ + A k r k n a_n = A_1 r_1^{\,n} + A_2 r_2^{\,n} + \cdots + A_k r_k^{\,n} a n = A 1 r 1 n + A 2 r 2 n + ⋯ + A k r k n の形にただ一通りに表され、係数A 1 , … , A k A_1,\dots,A_k A 1 , … , A k
証明. χ ( 0 ) = − c k ≠ 0 \chi(0)=-c_k\ne0 χ ( 0 ) = − c k = 0 r i r_i r i n + k n+k n + k
a n + k − c 1 a n + k − 1 − ⋯ − c k a n = ( χ ( E ) a ) n = ( D r 1 ⋯ D r k a ) n a_{n+k}-c_1a_{n+k-1}-\cdots-c_ka_n
=\bigl(\chi(E)a\bigr)_n
=\bigl(D_{r_1}\cdots D_{r_k}a\bigr)_n a n + k − c 1 a n + k − 1 − ⋯ − c k a n = ( χ ( E ) a ) n = ( D r 1 ⋯ D r k a ) n です。したがって漸化式を満たすことはD r 1 ⋯ D r k a = 0 D_{r_1}\cdots D_{r_k}a=0 D r 1 ⋯ D r k a = 0 補題 2.1 をm 1 = ⋯ = m k = 1 m_1=\cdots=m_k=1 m 1 = ⋯ = m k = 1 p i p_i p i A i A_i A i 補題 1.2 により一意なので、係数A 1 , … , A k A_1,\dots,A_k A 1 , … , A k ▨
特性根が重複する場合には、幾何数列に多項式係数を掛けた項が現れます。
系 2.3 (重複根に対する基本解). 特性多項式がχ ( x ) = ∏ i = 1 s ( x − r i ) m i \chi(x) = \prod_{i=1}^{s}(x - r_i)^{m_i} χ ( x ) = ∏ i = 1 s ( x − r i ) m i r 1 , … , r s r_1,\dots,r_s r 1 , … , r s m i ≥ 1 m_i \ge 1 m i ≥ 1 ∑ i = 1 s m i = k \sum_{i=1}^{s} m_i = k ∑ i = 1 s m i = k
( n j r i n ) n ≥ 0 , 0 ≤ j ≤ m i − 1 \bigl(n^{\,j}\, r_i^{\,n}\bigr)_{n\ge0}, \qquad 0 \le j \le m_i - 1 ( n j r i n ) n ≥ 0 , 0 ≤ j ≤ m i − 1 はいずれも漸化式の解です。任意の解は
a n = ∑ i p i ( n ) r i n a_n = \sum_i p_i(n)\, r_i^{\,n} a n = i ∑ p i ( n ) r i n の形にただ一通りに表されます。ここでp i p_i p i deg p i < m i \deg p_i<m_i deg p i < m i
証明. χ ( 0 ) = − c k ≠ 0 \chi(0)=-c_k\ne0 χ ( 0 ) = − c k = 0 r i r_i r i
χ ( E ) a = D r 1 m 1 ⋯ D r s m s a = 0 \chi(E)a=D_{r_1}^{m_1}\cdots D_{r_s}^{m_s}a=0 χ ( E ) a = D r 1 m 1 ⋯ D r s m s a = 0 と同値です。補題 2.1 から、任意の解について多項式p i p_i p i n j r i n n^j r_i^n n j r i n p i ( n ) = n j p_i(n)=n^j p i ( n ) = n j ▨
例 2.4 (フィボナッチ数列とビネの公式). フィボナッチ数列をF 0 = 0 , F 1 = 1 , F n = F n − 1 + F n − 2 ( n ≥ 2 ) F_0 = 0,\ F_1 = 1,\ F_n = F_{n-1} + F_{n-2}\ (n\ge 2) F 0 = 0 , F 1 = 1 , F n = F n − 1 + F n − 2 ( n ≥ 2 ) 2 2 2
x 2 = x + 1 , すなわち x 2 − x − 1 = 0. x^2 = x + 1, \qquad \text{すなわち}\quad x^2 - x - 1 = 0. x 2 = x + 1 , すなわち x 2 − x − 1 = 0. です。根はφ = 1 + 5 2 , ψ = 1 − 5 2 \varphi = \dfrac{1+\sqrt5}{2},\ \psi = \dfrac{1-\sqrt5}{2} φ = 2 1 + 5 , ψ = 2 1 − 5 定理 2.2 よりF n = A φ n + B ψ n F_n = A\varphi^n + B\psi^n F n = A φ n + B ψ n
{ A + B = F 0 = 0 , A φ + B ψ = F 1 = 1 , \begin{cases} A + B = F_0 = 0,\\ A\varphi + B\psi = F_1 = 1, \end{cases} { A + B = F 0 = 0 , A φ + B ψ = F 1 = 1 , を得ます。第一式よりB = − A B = -A B = − A A ( φ − ψ ) = 1 A(\varphi - \psi) = 1 A ( φ − ψ ) = 1 φ − ψ = 5 \varphi - \psi = \sqrt5 φ − ψ = 5 A = 1 5 , B = − 1 5 A = \dfrac{1}{\sqrt5},\ B = -\dfrac{1}{\sqrt5} A = 5 1 , B = − 5 1 ビネの公式
F n = φ n − ψ n 5 F_n = \frac{\varphi^{\,n} - \psi^{\,n}}{\sqrt5} F n = 5 φ n − ψ n を得ます。
φ n = L n + F n 5 2 \varphi^n = \dfrac{L_n + F_n\sqrt5}{2} φ n = 2 L n + F n 5 L n L_n L n φ n − ψ n = F n 5 \varphi^n - \psi^n = F_n\sqrt5 φ n − ψ n = F n 5 φ 5 = 11 + 5 5 2 , ψ 5 = 11 − 5 5 2 \varphi^5 = \dfrac{11 + 5\sqrt5}{2},\ \psi^5 = \dfrac{11 - 5\sqrt5}{2} φ 5 = 2 11 + 5 5 , ψ 5 = 2 11 − 5 5
φ 5 − ψ 5 5 = 5 5 5 = 5. \frac{\varphi^5 - \psi^5}{\sqrt5} = \frac{5\sqrt5}{\sqrt5} = 5. 5 φ 5 − ψ 5 = 5 5 5 = 5. です。漸化式から直接得られる値はF 0 , … , F 5 = 0 , 1 , 1 , 2 , 3 , 5 F_0,\dots,F_5 = 0,1,1,2,3,5 F 0 , … , F 5 = 0 , 1 , 1 , 2 , 3 , 5 F 5 = 5 F_5 = 5 F 5 = 5 n = 10 n=10 n = 10 φ 10 − ψ 10 = 55 5 \varphi^{10}-\psi^{10} = 55\sqrt5 φ 10 − ψ 10 = 55 5 55 55 55 F 10 = 55 F_{10}=55 F 10 = 55
3 行列反復としての線形漸化式 命題 3.1 (状態ベクトルによる行列表現). 定義 1.1 のk k k v n = ( a n , a n − 1 , … , a n − k + 1 ) T v_n = (a_n, a_{n-1}, \dots, a_{n-k+1})^{\mathsf T} v n = ( a n , a n − 1 , … , a n − k + 1 ) T n ≥ k − 1 n\ge k-1 n ≥ k − 1 k × k k\times k k × k コンパニオン行列
C = ( c 1 c 2 ⋯ c k − 1 c k 1 0 ⋯ 0 0 0 1 ⋯ 0 0 ⋮ ⋱ ⋮ 0 0 ⋯ 1 0 ) C = \begin{pmatrix}
c_1 & c_2 & \cdots & c_{k-1} & c_k \\
1 & 0 & \cdots & 0 & 0 \\
0 & 1 & \cdots & 0 & 0 \\
\vdots & & \ddots & & \vdots \\
0 & 0 & \cdots & 1 & 0
\end{pmatrix} C = c 1 1 0 ⋮ 0 c 2 0 1 0 ⋯ ⋯ ⋯ ⋱ ⋯ c k − 1 0 0 1 c k 0 0 ⋮ 0 によりv n = C v n − 1 v_n = C\, v_{n-1} v n = C v n − 1 v n = C n − k + 1 v k − 1 v_n = C^{\,n-k+1} v_{k-1} v n = C n − k + 1 v k − 1 C C C χ \chi χ C C C C n = P D n P − 1 C^n = P D^n P^{-1} C n = P D n P − 1 r i n r_i^{\,n} r i n 定理 2.2 を再現します。
証明. v n = C v n − 1 v_n = C v_{n-1} v n = C v n − 1 C v n − 1 C v_{n-1} C v n − 1 1 1 1 c 1 a n − 1 + c 2 a n − 2 + ⋯ + c k a n − k c_1 a_{n-1} + c_2 a_{n-2} + \cdots + c_k a_{n-k} c 1 a n − 1 + c 2 a n − 2 + ⋯ + c k a n − k a n a_n a n j j j 2 ≤ j ≤ k 2\le j\le k 2 ≤ j ≤ k C C C j j j ( j − 1 ) (j-1) ( j − 1 ) 1 1 1 a n − ( j − 1 ) a_{n-(j-1)} a n − ( j − 1 ) v n v_n v n j j j v n = C v n − 1 v_n = C v_{n-1} v n = C v n − 1 v n = C n − k + 1 v k − 1 v_n = C^{\,n-k+1}v_{k-1} v n = C n − k + 1 v k − 1
C C C χ \chi χ 1 1 1 k k k k = 2 k=2 k = 2
det ( x I − C ) = det ( x − c 1 − c 2 − 1 x ) = x ( x − c 1 ) − c 2 = x 2 − c 1 x − c 2 = χ ( x ) , \det(xI - C) = \det\begin{pmatrix} x - c_1 & -c_2 \\ -1 & x \end{pmatrix} = x(x-c_1) - c_2 = x^2 - c_1 x - c_2 = \chi(x), det ( x I − C ) = det ( x − c 1 − 1 − c 2 x ) = x ( x − c 1 ) − c 2 = x 2 − c 1 x − c 2 = χ ( x ) , となるため、確かに一致します。したがってC C C §D3.12 定義 1.1 ）はχ ( x ) = 0 \chi(x)=0 χ ( x ) = 0
特性根が相異なるとき、C C C k k k C = P D P − 1 C = PDP^{-1} C = P D P − 1 D = diag ( r 1 , … , r k ) D = \operatorname{diag}(r_1,\dots,r_k) D = diag ( r 1 , … , r k ) §D3.13 例 2.1 ）によりC n = P D n P − 1 C^n = P D^n P^{-1} C n = P D n P − 1 ( 1 , ℓ ) (1,\ell) ( 1 , ℓ ) ∑ i ( P ) 1 i ( P − 1 ) i ℓ r i n \sum_i (P)_{1i}(P^{-1})_{i\ell} r_i^n ∑ i ( P ) 1 i ( P − 1 ) i ℓ r i n r i n r_i^n r i n a n a_n a n v n = C n − k + 1 v k − 1 v_n = C^{\,n-k+1}v_{k-1} v n = C n − k + 1 v k − 1 1 1 1 a n = ∑ i A i r i n a_n = \sum_i A_i r_i^n a n = ∑ i A i r i n 定理 2.2 と一致します。▨
フィボナッチ数列の場合にはC = ( 1 1 1 0 ) C = \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix} C = ( 1 1 1 0 ) C n = ( F n + 1 F n F n F n − 1 ) C^n = \begin{pmatrix} F_{n+1} & F_n \\ F_n & F_{n-1}\end{pmatrix} C n = ( F n + 1 F n F n F n − 1 ) φ , ψ \varphi,\psi φ , ψ 例 2.4 のビネの公式はこの対角化の第1 1 1
4 母関数 定義 4.1 (通常型母関数). 数列( a n ) n ≥ 0 (a_n)_{n\ge 0} ( a n ) n ≥ 0 通常型母関数 （ordinary generating function, OGF）とは、形式的冪級数
A ( x ) = ∑ n ≥ 0 a n x n ∈ C [ [ x ] ] A(x) = \sum_{n\ge 0} a_n x^n \in \C[[x]] A ( x ) = n ≥ 0 ∑ a n x n ∈ C [[ x ]] です。ここでx x x 不定元 であり、級数の収束は問いません。二つの形式的冪級数は係数がすべて一致するときに等しいと定め、演算は
( ∑ a n x n ) + ( ∑ b n x n ) = ∑ ( a n + b n ) x n , ( ∑ a n x n ) ( ∑ b n x n ) = ∑ n ≥ 0 ( ∑ j = 0 n a j b n − j ) x n \Bigl(\sum a_n x^n\Bigr) + \Bigl(\sum b_n x^n\Bigr) = \sum (a_n + b_n) x^n, \qquad
\Bigl(\sum a_n x^n\Bigr)\Bigl(\sum b_n x^n\Bigr) = \sum_{n\ge0}\Bigl(\sum_{j=0}^{n} a_j b_{n-j}\Bigr) x^n ( ∑ a n x n ) + ( ∑ b n x n ) = ∑ ( a n + b n ) x n , ( ∑ a n x n ) ( ∑ b n x n ) = n ≥ 0 ∑ ( j = 0 ∑ n a j b n − j ) x n で定めます。後者をコーシー積 とよびます。第n n n [ x n ] A ( x ) = a n [x^n]A(x) = a_n [ x n ] A ( x ) = a n
( 1 − x ) ∑ n ≥ 0 x n = 1 , すなわち 1 1 − x = ∑ n ≥ 0 x n (1 - x)\sum_{n\ge0} x^n = 1, \qquad \text{すなわち}\quad \frac{1}{1-x} = \sum_{n\ge0} x^n ( 1 − x ) n ≥ 0 ∑ x n = 1 , すなわち 1 − x 1 = n ≥ 0 ∑ x n は、収束の主張ではなくC [ [ x ] ] \C[[x]] C [[ x ]] 1 1 1 0 0 0
以後の計算では、形式的冪級数の和と積について、括弧の付け替え、因子の並べ替え、および分配法則による展開を用います。これらの操作が許されるのは、C [ [ x ] ] \C[[x]] C [[ x ]]
証明. a i = [ x i ] A a_i = [x^i]A a i = [ x i ] A b j = [ x j ] B b_j = [x^j]B b j = [ x j ] B c k = [ x k ] C c_k = [x^k]C c k = [ x k ] C 定義 4.1 ）、各主張について両辺の第n n n n ≥ 0 n \ge 0 n ≥ 0
1. 和は係数ごとに定めてあり、( C , + ) (\C, +) ( C , + )
2. C \C C i + j = n i + j = n i + j = n ( i , j ) (i, j) ( i , j ) ( j , i ) (j, i) ( j , i )
[ x n ] ( A B ) = ∑ i + j = n a i b j = ∑ j + i = n b j a i = [ x n ] ( B A ) . [x^n](AB) = \sum_{i+j=n} a_i b_j = \sum_{j+i=n} b_j a_i = [x^n](BA). [ x n ] ( A B ) = i + j = n ∑ a i b j = j + i = n ∑ b j a i = [ x n ] ( B A ) . したがってA B = B A AB=BA A B = B A
3. 定義を二度用いると
[ x n ] ( ( A B ) C ) = ∑ m + k = n ( ∑ i + j = m a i b j ) c k [x^n]\bigl((AB)C\bigr) = \sum_{m+k=n}\Bigl(\sum_{i+j=m} a_i b_j\Bigr) c_k [ x n ] ( ( A B ) C ) = m + k = n ∑ ( i + j = m ∑ a i b j ) c k です。内側は有限和なので、C \C C c k c_k c k C \C C ( a i b j ) c k = a i ( b j c k ) (a_i b_j) c_k = a_i (b_j c_k) ( a i b j ) c k = a i ( b j c k ) ( m , k ) (m, k) ( m , k ) i + j = m i + j = m i + j = m ( i , j ) (i, j) ( i , j ) ( i , j , k ) (i, j, k) ( i , j , k ) i + j + k = n i + j + k = n i + j + k = n
[ x n ] ( ( A B ) C ) = ∑ i , j , k ≥ 0 i + j + k = n a i b j c k [x^n]\bigl((AB)C\bigr) = \sum_{\substack{i,j,k\ge 0\\ i+j+k=n}} a_i b_j c_k [ x n ] ( ( A B ) C ) = i , j , k ≥ 0 i + j + k = n ∑ a i b j c k を得ます。同じ計算をA ( B C ) A(BC) A ( B C ) n n n ( A B ) C = A ( B C ) (AB)C = A(BC) ( A B ) C = A ( B C )
4. C \C C
[ x n ] ( A ( B + C ) ) = ∑ i + j = n a i ( b j + c j ) = ∑ i + j = n a i b j + ∑ i + j = n a i c j = [ x n ] ( A B ) + [ x n ] ( A C ) . [x^n]\bigl(A(B + C)\bigr) = \sum_{i+j=n} a_i (b_j + c_j) = \sum_{i+j=n} a_i b_j + \sum_{i+j=n} a_i c_j = [x^n](AB) + [x^n](AC). [ x n ] ( A ( B + C ) ) = i + j = n ∑ a i ( b j + c j ) = i + j = n ∑ a i b j + i + j = n ∑ a i c j = [ x n ] ( A B ) + [ x n ] ( A C ) . したがってA ( B + C ) = A B + A C A(B+C)=AB+AC A ( B + C ) = A B + A C
5. [ x j ] 1 [x^j]1 [ x j ] 1 j = 0 j = 0 j = 0 1 1 1 j ≥ 1 j \ge 1 j ≥ 1 0 0 0 [ x n ] ( A ⋅ 1 ) = ∑ i + j = n a i [ x j ] 1 = a n [x^n](A\cdot 1) = \sum_{i+j=n} a_i\,[x^j]1 = a_n [ x n ] ( A ⋅ 1 ) = ∑ i + j = n a i [ x j ] 1 = a n A ⋅ 1 = A A \cdot 1 = A A ⋅ 1 = A 1 ⋅ A = A 1 \cdot A = A 1 ⋅ A = A ▨
母関数から一般項を取り出す計算では、1 / ( 1 − x ) 1/(1-x) 1/ ( 1 − x ) P ( x ) / Q ( x ) P(x)/Q(x) P ( x ) / Q ( x ) C [ [ x ] ] \C[[x]] C [[ x ]]
証明. （逆元が存在すればa 0 ≠ 0 a_0 \ne 0 a 0 = 0 A B = 1 AB = 1 A B = 1 0 0 0 a 0 b 0 = 1 a_0 b_0 = 1 a 0 b 0 = 1 C \C C a 0 b 0 = 1 a_0 b_0 = 1 a 0 b 0 = 1 a 0 ≠ 0 a_0 \ne 0 a 0 = 0
（a 0 ≠ 0 a_0 \ne 0 a 0 = 0 a 0 ≠ 0 a_0 \ne 0 a 0 = 0 B B B n n n b 0 , … , b n − 1 b_0, \dots, b_{n-1} b 0 , … , b n − 1 n n n B ∈ C [ [ x ] ] B \in \C[[x]] B ∈ C [[ x ]] [ x 0 ] ( A B ) = a 0 b 0 = 1 [x^0](AB) = a_0 b_0 = 1 [ x 0 ] ( A B ) = a 0 b 0 = 1 n ≥ 1 n \ge 1 n ≥ 1
[ x n ] ( A B ) = ∑ j = 0 n a j b n − j = a 0 b n + ∑ j = 1 n a j b n − j = − ∑ j = 1 n a j b n − j + ∑ j = 1 n a j b n − j = 0 [x^n](AB) = \sum_{j=0}^{n} a_j b_{n-j} = a_0 b_n + \sum_{j=1}^{n} a_j b_{n-j} = -\sum_{j=1}^{n} a_j b_{n-j} + \sum_{j=1}^{n} a_j b_{n-j} = 0 [ x n ] ( A B ) = j = 0 ∑ n a j b n − j = a 0 b n + j = 1 ∑ n a j b n − j = − j = 1 ∑ n a j b n − j + j = 1 ∑ n a j b n − j = 0 です。したがってA B = 1 AB = 1 A B = 1
（一意性） A B = 1 AB = 1 A B = 1 A B ′ = 1 AB' = 1 A B ′ = 1 命題 4.2 の 2、3、5 により
B ′ = B ′ ⋅ 1 = B ′ ( A B ) = ( B ′ A ) B = ( A B ′ ) B = 1 ⋅ B = B B' = B'\cdot 1 = B'(AB) = (B'A)B = (AB')B = 1\cdot B = B B ′ = B ′ ⋅ 1 = B ′ ( A B ) = ( B ′ A ) B = ( A B ′ ) B = 1 ⋅ B = B です。▨
例 4.4 (等比級数と有理型母関数の分母の逆元). A ( x ) = 1 − x A(x) = 1 - x A ( x ) = 1 − x a 0 = 1 ≠ 0 a_0 = 1 \ne 0 a 0 = 1 = 0 命題 4.3 により逆元をもちます。係数の再帰はb 0 = 1 b_0 = 1 b 0 = 1 n ≥ 1 n \ge 1 n ≥ 1 b n = − a 1 b n − 1 = b n − 1 b_n = -a_1 b_{n-1} = b_{n-1} b n = − a 1 b n − 1 = b n − 1 n n n b n = 1 b_n = 1 b n = 1
1 1 − x = ∑ n ≥ 0 x n \frac{1}{1-x} = \sum_{n\ge0} x^n 1 − x 1 = n ≥ 0 ∑ x n を得ます。これは定義 4.1 の基本等式です。同じ計算により、α ∈ C \alpha \in \C α ∈ C 1 − α x 1 - \alpha x 1 − α x ∑ n ≥ 0 α n x n \sum_{n\ge0}\alpha^n x^n ∑ n ≥ 0 α n x n 定理 5.1 で現れる分母Q ( x ) = 1 − c 1 x − ⋯ − c k x k Q(x) = 1 - c_1 x - \cdots - c_k x^k Q ( x ) = 1 − c 1 x − ⋯ − c k x k Q ( 0 ) = 1 ≠ 0 Q(0) = 1 \ne 0 Q ( 0 ) = 1 = 0 A ( x ) = P ( x ) / Q ( x ) A(x) = P(x)/Q(x) A ( x ) = P ( x ) / Q ( x ) C [ [ x ] ] \C[[x]] C [[ x ]]
命題 4.5 (母関数の演算と数列操作の対応). A ( x ) = ∑ a n x n , B ( x ) = ∑ b n x n A(x) = \sum a_n x^n,\ B(x) = \sum b_n x^n A ( x ) = ∑ a n x n , B ( x ) = ∑ b n x n λ ∈ C \lambda\in\C λ ∈ C r ≥ 1 r\ge 1 r ≥ 1
（和・スカラー倍）A + B A + B A + B ( a n + b n ) (a_n + b_n) ( a n + b n ) λ A \lambda A λ A ( λ a n ) (\lambda a_n) ( λ a n )
（右シフト）x r A ( x ) x^r A(x) x r A ( x ) ( a n − r ) n ≥ 0 (a_{n-r})_{n\ge 0} ( a n − r ) n ≥ 0 a n : = 0 ( n < 0 ) a_{n} := 0\ (n<0) a n := 0 ( n < 0 )
（左シフト）A ( x ) − ∑ j = 0 r − 1 a j x j x r \dfrac{A(x) - \sum_{j=0}^{r-1} a_j x^j}{x^r} x r A ( x ) − ∑ j = 0 r − 1 a j x j ( a n + r ) n ≥ 0 (a_{n+r})_{n\ge0} ( a n + r ) n ≥ 0
（積・畳み込み）A ( x ) B ( x ) A(x)B(x) A ( x ) B ( x ) ( ∑ j = 0 n a j b n − j ) n ≥ 0 \bigl(\sum_{j=0}^{n} a_j b_{n-j}\bigr)_{n\ge0} ( ∑ j = 0 n a j b n − j ) n ≥ 0
証明. いずれも[ x n ] [x^n] [ x n ]
1 は定義そのものです。2 ではx r A ( x ) = ∑ m ≥ 0 a m x m + r = ∑ n ≥ r a n − r x n x^r A(x) = \sum_{m\ge0} a_m x^{m+r} = \sum_{n\ge r} a_{n-r} x^n x r A ( x ) = ∑ m ≥ 0 a m x m + r = ∑ n ≥ r a n − r x n n < r n<r n < r 0 = a n − r 0 = a_{n-r} 0 = a n − r 0 0 0 A ( x ) − ∑ j < r a j x j = ∑ m ≥ r a m x m A(x) - \sum_{j<r} a_j x^j = \sum_{m\ge r} a_m x^m A ( x ) − ∑ j < r a j x j = ∑ m ≥ r a m x m x r x^r x r ∑ m ≥ r a m x m − r = ∑ n ≥ 0 a n + r x n \sum_{m\ge r} a_m x^{m-r} = \sum_{n\ge0} a_{n+r} x^n ∑ m ≥ r a m x m − r = ∑ n ≥ 0 a n + r x n 定義 4.1 ）から直ちに従います。▨
5 母関数による漸化式の解法 定理 5.1 (線形漸化式の母関数は有理関数). 定義 1.1 のk k k ( a n ) (a_n) ( a n ) A ( x ) A(x) A ( x )
Q ( x ) = 1 − c 1 x − c 2 x 2 − ⋯ − c k x k Q(x) = 1 - c_1 x - c_2 x^2 - \cdots - c_k x^k Q ( x ) = 1 − c 1 x − c 2 x 2 − ⋯ − c k x k とおくと有理関数
A ( x ) = P ( x ) Q ( x ) , deg P < k A(x) = \frac{P(x)}{Q(x)}, \qquad \deg P < k A ( x ) = Q ( x ) P ( x ) , deg P < k に等しくなります。ここで分子P P P Q ( x ) = ∏ i ( 1 − r i x ) m i Q(x) = \prod_i (1 - r_i x)^{m_i} Q ( x ) = ∏ i ( 1 − r i x ) m i r i r_i r i m i m_i m i 1 / r i 1/r_i 1/ r i A = P / Q A=P/Q A = P / Q m i m_i m i P ( 1 / r i ) ≠ 0 P(1/r_i)\ne0 P ( 1/ r i ) = 0 ( 1 − r i x ) (1-r_i x) ( 1 − r i x ) 1 / r i 1/r_i 1/ r i m i m_i m i
証明. Q ( x ) A ( x ) Q(x)A(x) Q ( x ) A ( x ) n n n Q ( x ) = ∑ t = 0 k b t x t Q(x) = \sum_{t=0}^{k} b_t x^t Q ( x ) = ∑ t = 0 k b t x t b 0 = 1 , b t = − c t b_0 = 1,\ b_t = -c_t b 0 = 1 , b t = − c t
[ x n ] ( Q ( x ) A ( x ) ) = ∑ t = 0 min ( n , k ) b t a n − t . [x^n]\bigl(Q(x)A(x)\bigr) = \sum_{t=0}^{\min(n,k)} b_t\, a_{n-t}. [ x n ] ( Q ( x ) A ( x ) ) = t = 0 ∑ m i n ( n , k ) b t a n − t . n ≥ k n \ge k n ≥ k a n − c 1 a n − 1 − ⋯ − c k a n − k a_n - c_1 a_{n-1} - \cdots - c_k a_{n-k} a n − c 1 a n − 1 − ⋯ − c k a n − k 0 0 0 P ( x ) : = Q ( x ) A ( x ) P(x) := Q(x)A(x) P ( x ) := Q ( x ) A ( x ) x k x^k x k deg P ≤ k − 1 < k \deg P \le k-1 < k deg P ≤ k − 1 < k Q ( 0 ) = 1 ≠ 0 Q(0) = 1 \ne 0 Q ( 0 ) = 1 = 0 命題 4.3 によりQ Q Q C [ [ x ] ] \C[[x]] C [[ x ]] Q − 1 Q^{-1} Q − 1 A ( x ) = P ( x ) / Q ( x ) A(x) = P(x)/Q(x) A ( x ) = P ( x ) / Q ( x ) [ x n ] P = ∑ t = 0 n b t a n − t ( 0 ≤ n ≤ k − 1 ) [x^n]P = \sum_{t=0}^{n} b_t a_{n-t}\ (0\le n\le k-1) [ x n ] P = ∑ t = 0 n b t a n − t ( 0 ≤ n ≤ k − 1 ) a 0 , … , a k − 1 a_0,\dots,a_{k-1} a 0 , … , a k − 1
分母の分解を確かめます。特性多項式はχ ( y ) = ∏ i ( y − r i ) m i \chi(y) = \prod_i (y - r_i)^{m_i} χ ( y ) = ∏ i ( y − r i ) m i ∑ i m i = k \sum_i m_i = k ∑ i m i = k y = 1 / x y = 1/x y = 1/ x x k x^k x k
x k χ ( 1 / x ) = x k ( x − k − c 1 x − ( k − 1 ) − ⋯ − c k ) = 1 − c 1 x − ⋯ − c k x k = Q ( x ) , x^k \chi(1/x) = x^k\bigl(x^{-k} - c_1 x^{-(k-1)} - \cdots - c_k\bigr) = 1 - c_1 x - \cdots - c_k x^k = Q(x), x k χ ( 1/ x ) = x k ( x − k − c 1 x − ( k − 1 ) − ⋯ − c k ) = 1 − c 1 x − ⋯ − c k x k = Q ( x ) , です。一方、∑ i m i = k \sum_i m_i = k ∑ i m i = k x k χ ( 1 / x ) = ∏ i x m i ( 1 / x − r i ) m i = ∏ i ( 1 − r i x ) m i x^k \chi(1/x) = \prod_i x^{m_i}(1/x - r_i)^{m_i} = \prod_i (1 - r_i x)^{m_i} x k χ ( 1/ x ) = ∏ i x m i ( 1/ x − r i ) m i = ∏ i ( 1 − r i x ) m i Q ( x ) = ∏ i ( 1 − r i x ) m i Q(x) = \prod_i (1 - r_i x)^{m_i} Q ( x ) = ∏ i ( 1 − r i x ) m i Q ( 0 ) = 1 ≠ 0 Q(0)=1\ne0 Q ( 0 ) = 1 = 0 x = 0 x=0 x = 0 Q Q Q A = P / Q A = P/Q A = P / Q deg P < deg Q = k \deg P < \deg Q = k deg P < deg Q = k
A ( x ) = ∑ i ∑ ℓ = 1 m i d i , ℓ ( 1 − r i x ) ℓ A(x) = \sum_i \sum_{\ell=1}^{m_i} \frac{d_{i,\ell}}{(1 - r_i x)^{\ell}} A ( x ) = i ∑ ℓ = 1 ∑ m i ( 1 − r i x ) ℓ d i , ℓ が一意に存在します。分母が一次式の冪の積である真分数式について、この分解の存在と一意性は代数の標準的な結果であり、本記事では証明せずに認めて用います。
この表示では、分子P P P ( 1 − r i x ) (1-r_i x) ( 1 − r i x ) P / Q P/Q P / Q m i m_i m i d i , ℓ d_{i,\ell} d i , ℓ 1 / r i 1/r_i 1/ r i P ( 1 / r i ) ≠ 0 P(1/r_i)\ne0 P ( 1/ r i ) = 0 ( 1 − r i x ) (1-r_i x) ( 1 − r i x ) x = 1 / r i x=1/r_i x = 1/ r i 1 / r i 1/r_i 1/ r i m i m_i m i 命題 5.2 で展開すると、a n = [ x n ] A ( x ) a_n = [x^n]A(x) a n = [ x n ] A ( x ) ▨
命題 5.2 (基本分数の係数展開). α ∈ C \alpha \in \C α ∈ C m ≥ 1 m\ge 1 m ≥ 1 C [ [ x ] ] \C[[x]] C [[ x ]]
1 ( 1 − α x ) m = ∑ n ≥ 0 ( n + m − 1 m − 1 ) α n x n \frac{1}{(1 - \alpha x)^{m}} = \sum_{n\ge 0} \binom{n + m - 1}{m - 1}\, \alpha^{\,n}\, x^n ( 1 − α x ) m 1 = n ≥ 0 ∑ ( m − 1 n + m − 1 ) α n x n が成り立ちます。したがって定理 5.1 の分解の各項d i , ℓ ( 1 − r i x ) ℓ \dfrac{d_{i,\ell}}{(1 - r_i x)^{\ell}} ( 1 − r i x ) ℓ d i , ℓ r i n r_i^{\,n} r i n n n n ℓ − 1 \ell-1 ℓ − 1 r i r_i r i m i m_i m i a n = ∑ i p i ( n ) r i n a_n = \sum_i p_i(n) r_i^{\,n} a n = ∑ i p i ( n ) r i n deg p i < m i \deg p_i < m_i deg p i < m i
証明. m m m m = 1 m=1 m = 1 ∑ n ( n 0 ) α n x n = ∑ n α n x n \sum_n \binom{n}{0}\alpha^n x^n = \sum_n \alpha^n x^n ∑ n ( 0 n ) α n x n = ∑ n α n x n 定義 4.1 の基本等式でx x x α x \alpha x α x 1 1 − α x \dfrac{1}{1-\alpha x} 1 − α x 1 m − 1 m-1 m − 1 1 ( 1 − α x ) m = 1 ( 1 − α x ) m − 1 ⋅ 1 1 − α x \dfrac{1}{(1-\alpha x)^m} = \dfrac{1}{(1-\alpha x)^{m-1}}\cdot\dfrac{1}{1-\alpha x} ( 1 − α x ) m 1 = ( 1 − α x ) m − 1 1 ⋅ 1 − α x 1 命題 4.5 ）により
[ x n ] 1 ( 1 − α x ) m = ∑ j = 0 n ( j + m − 2 m − 2 ) α j ⋅ α n − j = α n ∑ j = 0 n ( j + m − 2 m − 2 ) . [x^n]\frac{1}{(1-\alpha x)^m} = \sum_{j=0}^{n} \binom{j + m - 2}{m - 2}\alpha^{j}\cdot \alpha^{n-j} = \alpha^{n}\sum_{j=0}^{n}\binom{j + m - 2}{m - 2}. [ x n ] ( 1 − α x ) m 1 = j = 0 ∑ n ( m − 2 j + m − 2 ) α j ⋅ α n − j = α n j = 0 ∑ n ( m − 2 j + m − 2 ) . です。ここでホッケースティック恒等式 ∑ j = 0 n ( j + m − 2 m − 2 ) = ( n + m − 1 m − 1 ) \sum_{j=0}^{n}\binom{j+m-2}{m-2} = \binom{n+m-1}{m-1} ∑ j = 0 n ( m − 2 j + m − 2 ) = ( m − 1 n + m − 1 ) ( s + 1 m − 1 ) − ( s m − 1 ) = ( s m − 2 ) \binom{s+1}{m-1} - \binom{s}{m-1} = \binom{s}{m-2} ( m − 1 s + 1 ) − ( m − 1 s ) = ( m − 2 s ) s = m − 2 , … , n + m − 2 s = m-2,\dots,n+m-2 s = m − 2 , … , n + m − 2 ( n + m − 1 m − 1 ) − ( m − 2 m − 1 ) = ( n + m − 1 m − 1 ) \binom{n+m-1}{m-1} - \binom{m-2}{m-1} = \binom{n+m-1}{m-1} ( m − 1 n + m − 1 ) − ( m − 1 m − 2 ) = ( m − 1 n + m − 1 ) ( m − 2 m − 1 ) = 0 \binom{m-2}{m-1}=0 ( m − 1 m − 2 ) = 0 [ x n ] = ( n + m − 1 m − 1 ) α n [x^n] = \binom{n+m-1}{m-1}\alpha^n [ x n ] = ( m − 1 n + m − 1 ) α n
( n + ℓ − 1 ℓ − 1 ) \binom{n+\ell-1}{\ell-1} ( ℓ − 1 n + ℓ − 1 ) n n n ℓ − 1 \ell-1 ℓ − 1 d i , ℓ ( 1 − r i x ) ℓ \dfrac{d_{i,\ell}}{(1-r_ix)^\ell} ( 1 − r i x ) ℓ d i , ℓ r i n r_i^n r i n ℓ − 1 \ell-1 ℓ − 1 ℓ \ell ℓ 1 1 1 m i m_i m i r i n r_i^n r i n < m i <m_i < m i p i ( n ) p_i(n) p i ( n ) ▨
母関数の方法は非斉次項や、係数が畳み込みで結合する非線形の漸化式にも及びます。代表例がカタラン数です。
例 5.4 (カタラン数). n n n + 1 +1 + 1 n n n − 1 -1 − 1 n + 1 n+1 n + 1 カタラン数 C n C_n C n C 0 = 1 C_0 = 1 C 0 = 1
C n + 1 = ∑ i = 0 n C i C n − i ( n ≥ 0 ) C_{n+1} = \sum_{i=0}^{n} C_i\, C_{n-i} \qquad (n\ge 0) C n + 1 = i = 0 ∑ n C i C n − i ( n ≥ 0 ) を満たします。これは、最初の分割点で二つの独立な部分構造に分かれることによります。OGFC ( x ) = ∑ n ≥ 0 C n x n C(x) = \sum_{n\ge0} C_n x^n C ( x ) = ∑ n ≥ 0 C n x n 命題 4.5 よりC ( x ) 2 C(x)^2 C ( x ) 2
C ( x ) = 1 + x C ( x ) 2 C(x) = 1 + x\, C(x)^2 C ( x ) = 1 + x C ( x ) 2 を得ます。この等式から
( 1 − 2 x C ( x ) ) 2 = 1 − 4 x C ( x ) + 4 x 2 C ( x ) 2 = 1 − 4 x \bigl(1-2xC(x)\bigr)^2
=1-4xC(x)+4x^2C(x)^2
=1-4x ( 1 − 2 x C ( x ) ) 2 = 1 − 4 x C ( x ) + 4 x 2 C ( x ) 2 = 1 − 4 x となります。定数項が1 1 1 1 − 4 x 1-4x 1 − 4 x T ( x ) = 1 + ∑ n ≥ 1 t n x n T(x)=1+\sum_{n\ge1}t_nx^n T ( x ) = 1 + ∑ n ≥ 1 t n x n T ( x ) 2 = 1 − 4 x T(x)^2=1-4x T ( x ) 2 = 1 − 4 x n n n
2 t n + ∑ j = 1 n − 1 t j t n − j 2t_n+\sum_{j=1}^{n-1}t_jt_{n-j} 2 t n + j = 1 ∑ n − 1 t j t n − j であり、t 1 , t 2 , … t_1,t_2,\dots t 1 , t 2 , … 1 − 4 x \sqrt{1-4x} 1 − 4 x 1 − 2 x C ( x ) = 1 − 4 x 1-2xC(x)=\sqrt{1-4x} 1 − 2 x C ( x ) = 1 − 4 x
C ( x ) = 1 − 1 − 4 x 2 x C(x)=\frac{1-\sqrt{1-4x}}{2x} C ( x ) = 2 x 1 − 1 − 4 x です。分子1 − 1 − 4 x = 2 x C ( x ) 1-\sqrt{1-4x}=2xC(x) 1 − 1 − 4 x = 2 x C ( x ) x x x 1 + 1 − 4 x 2 x \dfrac{1+\sqrt{1-4x}}{2x} 2 x 1 + 1 − 4 x 2 2 2 x − 1 x^{-1} x − 1 C [ [ x ] ] \C[[x]] C [[ x ]]
閉形式は一般化二項級数( 1 − 4 x ) 1 / 2 = ∑ n ≥ 0 ( 1 / 2 n ) ( − 4 x ) n (1 - 4x)^{1/2} = \sum_{n\ge0}\binom{1/2}{n}(-4x)^n ( 1 − 4 x ) 1/2 = ∑ n ≥ 0 ( n 1/2 ) ( − 4 x ) n 1 1 1 1 − 4 x 1-4x 1 − 4 x 1 − 4 x \sqrt{1-4x} 1 − 4 x C n = [ x n ] C ( x ) = − 1 2 [ x n + 1 ] 1 − 4 x = − 1 2 ( 1 / 2 n + 1 ) ( − 4 ) n + 1 C_n = [x^n]C(x) = -\tfrac12 [x^{n+1}]\sqrt{1-4x} = -\tfrac12\binom{1/2}{n+1}(-4)^{n+1} C n = [ x n ] C ( x ) = − 2 1 [ x n + 1 ] 1 − 4 x = − 2 1 ( n + 1 1/2 ) ( − 4 ) n + 1
C n = 1 n + 1 ( 2 n n ) . C_n = \frac{1}{n+1}\binom{2n}{n}. C n = n + 1 1 ( n 2 n ) . ここでは( 1 / 2 n + 1 ) = ( − 1 ) n ( 2 n ) ! 2 2 n + 1 n ! ( n + 1 ) ! \binom{1/2}{n+1} = \dfrac{(-1)^n (2n)!}{2^{2n+1}\, n!\,(n+1)!} ( n + 1 1/2 ) = 2 2 n + 1 n ! ( n + 1 )! ( − 1 ) n ( 2 n )!
係数を検算します。漸化式からC 0 , … , C 4 C_0,\dots,C_4 C 0 , … , C 4
C 1 = C 0 2 = 1 , C 2 = 2 C 0 C 1 = 2 , C 3 = 2 C 0 C 2 + C 1 2 = 5 , C 4 = 2 C 0 C 3 + 2 C 1 C 2 = 14. C_1 = C_0^2 = 1,\quad C_2 = 2C_0C_1 = 2,\quad C_3 = 2C_0C_2 + C_1^2 = 5,\quad C_4 = 2C_0C_3 + 2C_1C_2 = 14. C 1 = C 0 2 = 1 , C 2 = 2 C 0 C 1 = 2 , C 3 = 2 C 0 C 2 + C 1 2 = 5 , C 4 = 2 C 0 C 3 + 2 C 1 C 2 = 14. 閉形式1 n + 1 ( 2 n n ) \tfrac{1}{n+1}\binom{2n}{n} n + 1 1 ( n 2 n ) 1 , 1 , 2 , 5 , 14 1, 1, 2, 5, 14 1 , 1 , 2 , 5 , 14 n = 4 n=4 n = 4 1 5 ( 8 4 ) = 70 5 = 14 \tfrac15\binom84 = \tfrac{70}{5} = 14 5 1 ( 4 8 ) = 5 70 = 14
6 指数型母関数 定義 6.1 (指数型母関数). 数列( a n ) n ≥ 0 (a_n)_{n\ge 0} ( a n ) n ≥ 0 指数型母関数 （exponential generating function, EGF）とは、形式的冪級数
A ^ ( x ) = ∑ n ≥ 0 a n x n n ! \hat A(x) = \sum_{n\ge 0} a_n \frac{x^n}{n!} A ^ ( x ) = n ≥ 0 ∑ a n n ! x n です。EGF は、要素に区別（ラベル）のある構造の数え上げに適しています。実際、二つの EGF の積は
A ^ ( x ) B ^ ( x ) = ∑ n ≥ 0 ( ∑ k = 0 n ( n k ) a k b n − k ) x n n ! \hat A(x)\,\hat B(x) = \sum_{n\ge0}\Bigl(\sum_{k=0}^{n}\binom{n}{k} a_k\, b_{n-k}\Bigr)\frac{x^n}{n!} A ^ ( x ) B ^ ( x ) = n ≥ 0 ∑ ( k = 0 ∑ n ( k n ) a k b n − k ) n ! x n という二項型の畳み込み を与えます。[ x n ] [x^n] [ x n ] ∑ k a k k ! b n − k ( n − k ) ! = 1 n ! ∑ k ( n k ) a k b n − k \sum_k \tfrac{a_k}{k!}\tfrac{b_{n-k}}{(n-k)!} = \tfrac{1}{n!}\sum_k \binom{n}{k}a_k b_{n-k} ∑ k k ! a k ( n − k )! b n − k = n ! 1 ∑ k ( k n ) a k b n − k ( n k ) \binom{n}{k} ( k n ) n n n
固定されたn n n a n = n ! a_n=n! a n = n !
∑ n ≥ 0 n ! x n n ! = ∑ n ≥ 0 x n = 1 1 − x \sum_{n\ge0}n!\frac{x^n}{n!}=\sum_{n\ge0}x^n=\frac{1}{1-x} n ≥ 0 ∑ n ! n ! x n = n ≥ 0 ∑ x n = 1 − x 1 です。一方、各n n n a n = 1 a_n=1 a n = 1 ∑ n ≥ 0 x n n ! = e x \sum_{n\ge0}\tfrac{x^n}{n!}=e^x ∑ n ≥ 0 n ! x n = e x
通常型と指数型の使い分けは、対象にラベルがあるか（順列・分割のようにラベル付き）ないか（整数の分割・格子路のように非ラベル）に対応します。本記事の斉次線形漸化式では、OGF が有理関数になる点が重要です。ラベル付き構造の系統的な数え上げ（種の理論）は後続の話題です。
7 誤りを避けるための確認事項
特性方程式と母関数の分母を区別します。 漸化式a n = c 1 a n − 1 + ⋯ + c k a n − k a_n = c_1 a_{n-1} + \cdots + c_k a_{n-k} a n = c 1 a n − 1 + ⋯ + c k a n − k χ ( x ) = x k − c 1 x k − 1 − ⋯ − c k \chi(x) = x^k - c_1 x^{k-1} - \cdots - c_k χ ( x ) = x k − c 1 x k − 1 − ⋯ − c k 定義 1.1 ）であり、母関数の分母Q ( x ) = 1 − c 1 x − ⋯ − c k x k Q(x) = 1 - c_1 x - \cdots - c_k x^k Q ( x ) = 1 − c 1 x − ⋯ − c k x k 定理 5.1 ）とは異なります。両者はQ ( x ) = x k χ ( 1 / x ) Q(x) = x^k\chi(1/x) Q ( x ) = x k χ ( 1/ x ) χ \chi χ r i r_i r i Q Q Q 1 / r i 1/r_i 1/ r i − c t -c_t − c t 重複根では多項式因子を含めます。 特性根r r r m m m r n , n r n , … , n m − 1 r n r^n, n r^n, \dots, n^{m-1}r^n r n , n r n , … , n m − 1 r n 系 2.3 ）。同じ列r n r^n r n m m m Q Q Q ( 1 − r x ) (1-rx) ( 1 − r x ) m m m A = P / Q A=P/Q A = P / Q 注意 5.3 ）。冪級数の逆数をとる前に定数項を確認します。 1 / A ( x ) 1/A(x) 1/ A ( x ) C [ [ x ] ] \C[[x]] C [[ x ]] A ( 0 ) ≠ 0 A(0)\ne 0 A ( 0 ) = 0 命題 4.3 ）。A ( 0 ) = 0 A(0)=0 A ( 0 ) = 0 1 / x 1/x 1/ x C [ [ x ] ] \C[[x]] C [[ x ]] Q ( x ) Q(x) Q ( x ) Q ( 0 ) = 1 Q(0)=1 Q ( 0 ) = 1 母関数の左シフトでは初期項を除きます。 左シフト( a n + r ) (a_{n+r}) ( a n + r ) A ( x ) / x r A(x)/x^r A ( x ) / x r ( A ( x ) − ∑ j < r a j x j ) / x r \bigl(A(x) - \sum_{j<r} a_j x^j\bigr)/x^r ( A ( x ) − ∑ j < r a j x j ) / x r 命題 4.5 ）。低次の項を除かなければ、存在しない負の添字が導入されます。Q ( x ) A ( x ) Q(x)A(x) Q ( x ) A ( x ) 定理 5.1 ）。カタラン数では形式的平方根の定数項を指定します。 C ( x ) = 1 + x C ( x ) 2 C(x) = 1 + xC(x)^2 C ( x ) = 1 + x C ( x ) 2 1 − 4 x \sqrt{1-4x} 1 − 4 x 1 1 1 1 − 1 − 4 x 2 x \dfrac{1-\sqrt{1-4x}}{2x} 2 x 1 − 1 − 4 x x x x 1 + 1 − 4 x 2 x \dfrac{1+\sqrt{1-4x}}{2x} 2 x 1 + 1 − 4 x x − 1 x^{-1} x − 1 C [ [ x ] ] \C[[x]] C [[ x ]] 例 5.4 ）。通常型と指数型の積を区別します。 OGF の積はコーシー積∑ j a j b n − j \sum_j a_j b_{n-j} ∑ j a j b n − j ∑ k ( n k ) a k b n − k \sum_k \binom{n}{k} a_k b_{n-k} ∑ k ( k n ) a k b n − k 定義 4.1 、定義 6.1 ）。ラベルの有無によって用いる母関数と演算則が変わります。線形漸化式の一般項を求める場合には、OGF が有理関数になる通常型で十分です。