1 べき級数型母関数
1. 母関数
数列{an}n≥0 の母関数とは，
g(x) =
∑∞ n=0
anxn
で定義される形式的ベキ級数．
ベキ級数同士には和差 ± および積× の演算が形式的に定義でき，形式的ベキ級数 の集合は1を単位元とする環になる．
他の代数・解析計算をするときは少々注意が必要．
2. 重複組合せ
自然数N を一つ指定して，an を 1から N までの自然数から重複を許して n 個取 り出す取り出し方の総数とする．
an =
(N +n−1 N −1
)
=R[x1, x2,· · · , xN] の次数 n の階数
=x1, x2,· · · , xN でできる次数n の単項式の個数 最初の等式を，高校生的方法で説明．
3. 重複組合せの関数表示
重複組合せの総数の数列 {an} の母関数は，
∑∞ n=0
(N +n−1 N −1
)
xn= 1 (1−x)N とも表せる．これを確かめるため，
1 1−x1
1
1−x2 · · · 1 1−xN
= (1 +x1+x21+· · ·)(1 +x2+x22 +· · ·)· · ·(1 +xN +x2N +· · ·)
= 1 + ∑
1≤i≤N
xi+ ∑
1≤i≤j≤N
xixj+ ∑
1≤i≤j≤k≤N
xixjxk+· · ·
を考える．最終式の級数の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=α1an−1+α2an−2+· · ·+αkan−k で表せるとき，{an}n≥0 の母関数は有理関数になる．
6. 説明
{an}n≥0 の母関数をg(x) =∑∞
n=0anxn とおくと，
(1−α1x−α2x2− · · · −αkxk)g(x) =P(x)
は，k 次以上の項の係数はすべて漸化式により相殺されるので，高々k−1 次の多 項式になる．したがって g は有理関数．
7. コメント
有理式は分母が因数分解できれば部分分数展開でき，an の一般項を n の式で表す のは
1 (1−x)k =
∑∞ n=0
(k+n−1)!
(k−1)!n! xn に帰着される．
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−2x)(1 +x+ 2x2)+ 1
と計算できる．この形から，α を 2x2+x+ 1 = 0 の解とすると，an の一般形は an=−3
4 (
−2n+ 2 ¯α−1 2(α+ 2) · 1
αn − 1
(α+ 2) · 1
¯ αn
)
− 1 2 であることが分かる．
9. 演習
(1) A(x) =∑
nanxn, B(x) = ∑
nbnxn, C(x) =∑
ncnxn とし，以下に答えよ．
(1) cn=∑
j+2k≤najbk のときC を A と B で表せ．
(2) nbn =∑n
k=02kak/(n−k)! のときA を B で表せ．
(3) r が実数で，an =∑n k=0
(r+k
k
)bn−k のときA を B で表せ．
(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 個の文字の積 x1x2· · ·xn を n−1 個の2項演算の合成に分解する仕方の総数は (2n−2)!
n!(n−1)! = 1 (2n−1)
(2n−1 n
)
11. 証明
a1 = 1 と約束すれば，
an =a1an−1+a2an−2 +· · ·+an−1a1 がなりたつ．{an}n≥0 の母関数を g(x)とおけば
g2(x) =g(x)−1
をみたす．そこでこれを g(x)に関する2次関数と見なして解くと
g(x) = 1±√ 1−4x 2
g(0) = 0 なので，正しい解は − の方．この右辺を級数展開することにより結果が
えられる．
12. 例（ベルヌーイ数）
B0 = 1, Bn=
∑n k=0
(n k
)
Bn−k(n ≥2)
で定義される数列B0, B1,· · · は，ベルヌーイ数とよばれ，数学の随所に現れる．右 側の関係式は第 n 項が相殺され，n−1以下の項の関係式を与える．{Bn}n≥0 の指 数型母関数にex−1 をかけると
(ex−1)
∑∞ n=0
Bn n!xn=
( ∞
∑
k=1
1 k!xk
) ( ∞
∑
n=0
Bn n!xn
)
=
∑∞ n=0
1 n!
( n
∑
k=1
Bn−k k!(n−k)!
) xn
=
∑∞ n=0
1 n!
( n
∑
k=0
(n k
)
Bn−k−Bn
) xn
=x したがって指数型母関数は
∑∞ n=0
Bn
n! xn= x ex−1 13. 例 (分割数)
自然数 n を，（単数を含む）複数の自然数の和として表す表し方の個数を n の分割 数といい，p(n) で表す．ただし p(0) = 1と約束する．
14. 分割数の母関数 分割数の母関数は，
∑
n
p(n)xn =
∏∞ n=1
1 1−xn
と表示される．右辺の無限積は |x| <1 に含まれる勝手なコンパクト集合上一様収 束する．
右辺をえるためにn を自然数とし，
1
1−xnn = 1 +xnn+x2nn +· · ·
を n≥1 に関して無限積をとると
∏∞ n=1
1
1−xnn = (1 +x1+x21+· · ·)(1 +x22+x42+· · ·)· · ·
= 1 +x1+x21 +x22+x31+x1x22+x33+· · ·
=
∑∞ n=0
∑
i1≤i2≤···≤ik i1+i2+···+ik=n
xii1
1xii2
2· · ·xiik
k
ここで最後のかっこ内の和は，n を固定したときの n の分割に関する和で，k は分 割の長さを表し，固定された数字ではない．
これにより，右辺の n 次の項はちょうど p(n) 個の単項式からなるので，x=x1 = x2 =· · · とおけばよい．
15. 分割数の増大度
安易な上からの評価として，分割した数の並べ方も考慮に入れると組合せに帰着 でき，
p(n)<
n−1
∑
k=0
(n−1 k
)
= 2n−1
で，n について指数オーダーで増大する関数で上から押さえられている．実はP(n) 自身, n に関して指数オーダーで増大することが知られている．
16. 数列の無限積の定義
数列{an}n≥0 に対して，第k項までの和∑k
n=1anによりえられる数列{∑k
n=1an}k≥0
が収束するとき，{an}n≥0 からえられる級数∑∞
n=1an は収束すると言った．ここで は和を積に置き換える．
第k項までの積∏k
n=1anによりえられる数列{∏k
n=1an}n≥0が収束するとき，{an}n≥0
の無限積 ∏∞
n=1an は収束するという．
数列 {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=∏k
n=1(1 +un) とおくと，
|pk| ≤
∏k n=1
(1 +|un|)≤
∏k n=1
e|un|=ePkn=1|un|≤eσ
とくに第2項の右辺による評価より，この段階で∏∞
n=1(1 +|un|)は収束することが 分かる．
さらに vn=pn−pn−1 とおくと，vn =unpn−1 であり，
|vn|=|unpn−1| ≤eσ|un| 一方，仮定より∑∞
n=1unは絶対収束するので∑∞
n=1vnも絶対収束する．したがって級 数∑∞
n=1vn は収束するが，∑k
n=1vn=pkであり，その収束先∑∞
n=0vn = limk→∞pk は∏∞
n=1(1 +un) の収束先に他ならない．
19. 関数列の無限積
{un(x)}n≥0 を閉区間 K 上の連続関数列で，∑∞
n=1|un(x)| が K 上で一様収束する とする．（このとき収束先の関数 u∞(x)は連続で，supx∈Ku∞(x) =σ <∞）．この とき∏∞
n=1(1 +un(x)) は K 上一様収束する．とくに連続．
20. 証明
数列の場合と同様に二つの評価
|pk(x)| ≤eσ, |vn(x)| ≤eσ|un(x)| がえられる．一方∑∞
n=1|un(x)| は一様収束するので，任意のε に対し自然数 N が 存在して，
∑∞ n=N
|un(x)| ≤ε が任意の x∈K に対して成り立つ．これより
∑∞ n=N
|vn(x)| ≤eσε
これは (∏k
n=0(1 +un(x))) = pk(x) =∑k
n=1vn(x)が一様収束することを示す．
