1. No category

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) が一様収束することを示す．