1 べき級数型母関数 1. 母関数数列 {an }n≥0 の母関数とは， g(x) = ∞ ∑ an xn n=0 で定義される形式的ベキ級数．ベキ級数同士には和差 ± および積 × の演算が形式的に定義でき，形式的ベキ級数の集合は 1 を単位元とする環になる．他の代数・解析計算をするときは少々注意が必要． 2. 重複組合せ自然数 N を一つ指定して，an を 1 から N までの自然数から重複を許して n 個取り出す取り出し方の総数とする． ) ( N +n−1 an = N −1 = R[x1 , x2 , · · · , xN ] の次数 n の階数 = x1 , x2 , · · · , xN でできる次数 n の単項式の個数最初の等式を，高校生的方法で説明． 3. 重複組合せの関数表示重複組合せの総数の数列 {an } の母関数は， 1 (1 − x)N とも表せる．これを確かめるため． 1 1 1 ··· 1 − x1 1 − x2 1 − xn 2 = (1 + x1 + x1 + · · · )(1 + x2 + x22 + · · · ) · · · (1 + xn + x2n + · · · ) ∑ ∑ ∑ =1+ xi + x i xj + xi xj xk + · · · 1≤i≤n 1≤i≤j≤n 1≤i≤j≤k≤n を考える．最終式の級数の n 次の項にはすべての n 次の単項式が各々1 回現れるので，x1 = x2 = · · · = xn = x とおけば，各係数は重複組合せの個数になる．右辺を計算するとき，1/(1 − x) = 1 + x + x2 + · · · という |x| < 1 という範囲で成り立つ解析的な等式を使っているので，等号は，|x| < 1 で x で定義された関数として成り立つ． 4. 関数表示から母関数の原型を導くテーラー展開を計算する． 5. 例 (線形漸化式) a0 , a1 , · · · , ak−1 があたえられ，さらに任意の n ≥ k に対して数列 {an }n≥0 が，定数 α1 , α2 , · · · , αk を用いて漸化式 an = α1 an−1 + α2 an−2 + · · · + αk an−k で表せるとき，{an }n≥0 の母関数は有理関数になる． 6. 説明 ∑ n {an }n≥0 の母関数を g(x) = ∞ n=0 an x とおくと， (1 − α1 x − α2 x2 − · · · − αk xk )g(x) = P (x) は，k 次以上の項の係数はすべて漸化式により相殺されるので，高々 k − 1 次の多項式になる．したがって g は有理関数． 7. コメント有理式は分母が因数分解できれば部分分数展開でき，an の一般項を n の式で表すのは ∞ ∑ 1 (k + n − 1)! n = x k (1 − x) (k − 1)! n! n=0 に帰着される． 8. 例（非線形漸化式）正四面体の辺をわたり歩くランダムウォークを考える．始点となる頂点を指定し，後戻りはせずに，n 回目に始点に戻ってくるウォークの個数を an とし，an を明示的に求めたい．ステップ数が n ≥ 1 のウォークの個数は 3 · 2n−1 である．これらのウォークは，始点に到達するものが an 個，n − 1 ステップで始点に到達していたものが 2an−1 個，n + 1 ステップに始点に到達するものが an+1 個の独立なウォークの和からなるので， an+1 + an + 2an−1 = 3 · 2n−1 (n ≥ 2) という漸化式をみたす．漸化式の成立範囲が n ≥ 2 なので，初期条件は a0 = 1, a1 = a2 = 0 となる．g(x) をこの数列の母艦数とすれば，線形な場合と同様な方法で g(x) = 6x3 +1 (1 − 2x)(1 + x + 2x2 ) と計算できる．この形から，α を 2x2 + x + 1 = 0 の解とすると，an の一般形は ) ( 3 1 1 1 1 2¯ α−1 n an = − · n− · n − −2 + 4 2(α + 2) α (α + 2) α ¯ 2 であることが分かる． 9. 演習 ∑ ∑ an xn , B(x) = n bn xn , C(x) = n cn xn とし，以下に答えよ． ∑ (1) cn = j+2k≤n aj bk のとき C を A と B で表せ． ∑ (2) nbn = nk=0 2k ak /(n − k)! のとき A を B で表せ． ∑ ( ) (3) r が実数で，an = nk=0 r+k bn−k のとき A を B で表せ． k (1) A(x) = ∑ n (2) a0 = a1 = 1 の下で，漸化式 an = an−1 + an−2 (n ≥ 2) を解け． (3) a0 = a1 = 1 の下で，漸化式 an = an−1 + 2an−2 + (−1)n (n ≥ 2) を解け． (4) 1 円玉，5 円玉，10 円玉，50 円玉，100 円玉，500 円玉を組み合わせて n 円にする組み合わせ方の個数 {an }n≥0 (ただし a0 = 1 とする) の母関数を求めよ．さらに a10000 を計算せよ． (5) 2 × n の長方形を 1 × 2 のドミノで詰める詰め方の個数 {an }n≥0 (ただし a0 = 1 とする) の母関数を求め，an を n の式で表せ． (6) n 桁の自然数で，となり合う桁の数が異なりかつ 10 で割れるものの個数を求めよ． 10. 例 (カタラン数) n 個の文字の積 x1 x2 · · · xn を n − 1 個の 2 項演算の合成に分解する仕方の個数は ( ) 2n − 1 (2n − 2)! 1 = n!(n − 1)! (2n − 1) n 11. 証明 a1 = 1 と約束すれば， an = a1 an−1 + a2 an−2 + · · · + an−1 a1 がなりたつ．{an }n≥0 の母関数を g(x) とおけば g 2 (x) = g(x) − 1 をみたす．そこでこれを g(x) に関する 2 次関数と見なして解くと √ 1 ± 1 − 4x g(x) = 2 g(0) = 0 なので，正しい解は − の方．この右辺を級数展開することにより結果がえられる． 12. 例（ベルヌーイ数） B0 = 1, Bn = n ( ) ∑ n k k=0 Bn−k (n ≥ 2) で定義される数列 B0 , B1 , · · · は，ベルヌーイ数とよばれ，数学の随所に現れる．右側の関係式は第 n 項が相殺され，n − 1 以下の項の関係式を与える．{Bn }n≥0 の指数型母関数に ex − 1 をかけると (∞ )( ∞ ) ∞ ∑ ∑ ∑ B 1 B n n n n (ex − 1) x = xk x n! k! n! n=0 n=0 k=1 ( n ) ∞ ∑ 1 ∑ Bn−k = xn n! k=1 k!(n − k)! n=0 ( n ( ) ) ∞ ∑ 1 ∑ n = Bn−k − Bn xn n! k n=0 k=0 =x したがって指数型母関数は ∞ ∑ Bn n=0 n! xn = ex x −1 13. 例 (分割数) 自然数 n を，（単数を含む）複数の自然数の和として表す表し方の個数を n の分割数といい，p(n) で表す．ただし p(0) = 1 と約束する． 14. 分割数の母関数分割数の母関数は， ∑ n p(n)x = n ∞ ∏ 1 1 − xn n=1 と表示される．右辺の無限積は |x| < 1 に含まれる勝手なコンパクト集合上一様収束する．右辺をえるために n を自然数とし， 1 = 1 + xnn + x2n n + ··· n 1 − xn を n ≥ 1 に関して無限積をとると ∞ ∏ 1 = (1 + x1 + x21 + · · · )(1 + x22 + x42 + · · · ) · · · n 1 − xn n=1 = 1 + x1 + x21 + x22 + x31 + x1 x22 + x33 + · · ·   ∞ ∑ ∑  = xii11 xii22 · · · xiikk   n=0 i1 ≤i2 ≤···≤ik i1 +i2 +···+ik =n ここで最後のかっこ内の和は，n を固定したときの n の分割に関する和で，k は分割の長さを表し，固定された数字ではない．これにより，右辺の n 次の項はちょうど p(n) 個の単項式からなるので，x = x1 = x2 = · · · とおけばよい． 15. 分割数の増大度安易な上からの評価として，分割した数の並べ方も考慮に入れると組合せに帰着でき， ) n−1 ( ∑ n−1 p(n) < = 2n−1 k k=0 で，n について指数オーダーで増大する関数で上から押さえられている．実は P (n) 自身, n に関して指数オーダーで増大することが知られている． 16. 数列の無限積の定義 ∑k ∑k 数列 {an }n≥0 に対して，第 k 項までの和 n=1 an によりえられる数列 { n=1 an }k≥0 ∑∞ が収束するとき，{an }n≥0 からえられる級数 n=1 an は収束すると言った．ここでは和を積に置き換える． ∏k ∏k 第 k 項までの積 n=1 an によりえられる数列 { n=1 an }n≥0 が収束するとき，{an }n≥0 ∏∞ の無限積 n=1 an は収束するという．数列 {an } のメンバーに 0 が一つでもあると，その無限積は他の値によらず 0 になるので，すべての n について an 6= 0 を課す事が妥当である．さらに n → ∞ のとき an → 1 の場合が最も興味深い． 17. 数列の無限積の収束 ∑∞ ∑∞ 級数 n un が絶対収束する，すなわち n |un | = σ(< ∞) をみたすとする．この ∏∞ ∏∞ とき無限積 n=1 (1 + |un |) および n=1 (1 + un ) は収束する． 18. 証明 ∏ pk = kn=1 (1 + un ) とおくと， |pk | ≤ k ∏ (1 + |un |) ≤ n=1 k ∏ Pk e|un | = e n=1 |un | ≤ eσ n=1 とくに第 2 項の右辺による評価より，この段階で分かる． ∏∞ n=1 (1 + |un |) は収束することがさらに vn = pn − pn−1 とおくと，vn = un pn−1 であり， |vn | = |un pn−1 | ≤ eσ |un | ∑∞ ∑∞ 一方，仮定より n=1 un は絶対収束するので n=1 vn も絶対収束する．したがって級 ∑∞ ∑k ∑∞ 数 n=1 vn は収束するが， n=1 vn = pk であり，その収束先 n=0 vn = limk→∞ pk ∏∞ は n=1 (1 + un ) の収束先に他ならない． 19. 関数列の無限積 ∑ {un (x)}n≥0 を閉区間 K 上の連続関数列で， ∞ n=1 |un (x)| が K 上で一様収束するとする．（このとき収束先の関数 u∞ (x) は連続で，supx∈K u∞ (x) = σ < ∞）．この ∏∞ とき n=1 (1 + un (x)) は K 上一様収束する．とくに連続． 20. 証明数列の場合と同様に二つの評価 |pk (x)| ≤ eσ , がえられる．一方存在して， ∑∞ n=1 |vn (x)| ≤ eσ |un (x)| |un (x)| は一様収束するので，任意の ε に対し自然数 N が ∞ ∑ |un (x)| ≤ ε n=N が任意の x ∈ K に対して成り立つ．これより ∞ ∑ |vn (x)| ≤ eσ ε n=N ∑k ∏k これは ( n=0 (1 + un (x))) = pk (x) = n=1 vn (x) が一様収束することを示す．