16.2 母関数を使った数え上げ

母関数は \(n\) 個のオブジェクトを選択する個数の表現・数え上げで特に有用となる。例えば、チョコレートとプレーンの \(2\) 種類のドーナツの中から合計 \(n\) 個のドーナツを選ぶ方法の個数を \(d_{n}\)とするとき、\(d_{n} = n + 1\) が成り立つ。なぜなら、ドーナツの選び方が \(n + 1\) 通り ── 全てプレーン、\(1\) 個のチョコレートと \(n - 1\) 個のプレーン、\(2\) 個のチョコレートと \(n - 2\) 個のプレーン、 \(\cdots\) 、全てチョコレート ── あるからである。よってドーナツの選び方の個数の母関数¹を \(D(x)\) とすれば、\(D(x)\) は \(x^{n}\) の係数が \(d_{n} = n + 1\) の無限級数であり、等式 \(\text{(16.5)}\) から次の等式が分かる:

\[ D(x) = \frac{1}{(1 - x)^{2}} \tag{16.6}\]

16.2.1 リンゴとバナナも

一般に、二つの物 ── 例えばリンゴappleとバナナbanana ── を何らかの制約に沿って選択する方法の個数を考えていて、\(n\) 個のリンゴを選ぶ方法は \(a_{n}\) 通り、\(n\) 個のバナナを選ぶ方法は \(b_{n}\) 通りあるとする。このときリンゴの選び方の個数の母関数は次の \(A(x)\) となる:

\[ A(x) ::= \sum_{n=0}^{\infty} a_{n} x^{n} \]

同様に、バナナの選び方の個数の母関数は次の \(B(x)\) となる:

\[ B(x) ::= \sum_{n=0}^{\infty} b_{n} x^{n} \]

リンゴは \(6\) 個ごとにカゴに入っていて、カゴ単位でしか選択できないと仮定しよう。つまり次の関係が成り立つとする:

\[ a_{n} = \begin{cases} 1\ \ & \text{(\(n\) が \(6\) の倍数のとき)} \\ 0\ \ & \text{(それ以外のとき)} \end{cases} \]

このとき、\(A(x)\) は次のように変形できる:

\[ \begin{aligned} A(x) &= 1 + x^{6} + x^{12} + \cdots + x^{6n} + \cdots \\ &= 1 + y + y^{2} + \cdots + y^{n} + \cdots \qquad (\text{\(y = x^{6}\) とした}) \\[4pt] &= \frac{1}{1 - y} = \frac{1}{1 - x^{6}} \end{aligned} \]

さらに、バナナは \(2\) 種類ある ── 赤いバナナと黄色いバナナがある ── と仮定しよう。このとき先ほどのドーナツを選ぶ問題と同様の議論で \(b_{n} = n + 1\) であり、等式 \(\text{(16.6)}\) より次が分かる:

\[ B(x) = \frac{1}{(1 - x)^{2}} \]

では、リンゴとバナナを全部で \(n\) 個選ぶとき、選び方は何通りあるだろうか？まずリンゴの個数を決めるとする。これは \(0\) 以上 \(n\) 以下の整数 \(k\) を選ぶのに等しい。\(k\) 個のリンゴの選び方は定義より \(a_{k}\) 通りある。そして、残った \(n - k\) 個のバナナの選び方は定義より \(b_{n-k}\) 通りある。よって \(k\) 個のリンゴと \(n-k\) 個のバナナを選ぶ方法は \(a_{k}b_{n-k}\) 通りある。よって、リンゴとバナナを全部で \(n\) 個選ぶ方法の個数は次のように表せる:

\[ a_{0}b_{n} + a_{1}b_{n-1} + a_{2}b_{n-2} + \cdots + a_{n}b_{0} \tag{16.7}\]

16.2.2 母関数の積

数え上げと母関数の間にはクールな関係がある: 式 \(\text{(16.7)}\) は積 \(A(x) \cdot B(x)\) の \(x^{n}\) の係数に等しい。言い換えれば:

規則[乗算則 (product rule)]

任意の母関数 \(A(x) ::= \sum a_{n} x^{n}\) と \(B(x) ::= \sum b_{n} x^{n}\) に対して、次の等式が成り立つ:

\[ [x^{n}](A(x) \cdot B(x)) = a_{0}b_{n} + a_{1}b_{n-1} + a_{2}b_{n-2} + \cdots + a_{n}b_{0} \tag{16.8}\]

母関数の乗算則を理解するには、積 \(A(x) \cdot B(x)\) に含まれる全ての項を示した次の無限に大きい表を思い浮かべるとよい。右下の領域にある各項は、左にある \(A(x)\) の項と上にある \(B(x)\) の項である:

\[ \def\arraystretch{1.5}\begin{array}{c|ccccc} & b_{0}x^{0} & b_{1}x^{1} & b_{2}x^{2} & b_{3}x^{3} & \cdots \\ \hline a_{0}x_{0} & a_{0}b_{0}x^{0} & a_{0}b_{1}x^{1} & a_{0}b_{2}x^{2} & a_{0}b_{3}x^{3} & \cdots \\ a_{1}x_{1} & a_{1}b_{0}x^{1} & a_{1}b_{1}x^{2} & a_{1}b_{2}x^{3} & \cdots & \\ a_{2}x_{2} & a_{2}b_{0}x^{2} & a_{2}b_{1}x^{3} & \cdots & & \\ a_{3}x_{3} & a_{3}b_{0}x^{3} & \cdots & & & \end{array} \]

この表では \(x\) の次数が同じ項が斜め \(45^{\circ}\) に並ぶので、積 \(A(x) \cdot B(x)\) の \(x^{n}\) の係数は左上から \(n\) 個目の対角線上にある項の和に等しい。この和を表したのが式 \(\text{(16.7)}\) である。積 \(A(x) \cdot B(x)\) の係数を並べた列は、列 \((a_{0}, a_{1}, a_{2}, \ldots)\) と列 \((b_{0}, b_{1}, b_{2}, \ldots)\) の畳み込み (convolution) と呼ばれる。列の畳み込みは代数で使われるのに加えて、制御理論と信号処理でも利用される。

この乗算則があると、幾何級数が収束するかどうかに関わらず \(1/(1 - x)\) に等しいことを代数的に正当化できる。具体的には次の通りである。定数 \(1\) は次の母関数を表す:

\[ 1 = 1 + 0x + 0x^{2} + \cdots + 0x^{n} + \cdots \]

同様に、式 \(1 - x\) は次の母関数を表す:

\[ 1 - x = 1 + (-1)x + 0x^{2} + \cdots + 0 x^{n} + \cdots \]

よって乗算則を使えば、全ての項の係数が \(1\) である \(G(x)\) と \(1 -x\) の積を完全に厳密な形で計算できる:

\[ (1 - x) \cdot G(x) = 1 + 0x + 0x^{2} + \cdots + 0x^{n} + \cdots = 1 \]

言い換えれば、乗算則を認めるとき、幾何級数 \(G(x)\) は \(1-x\) の乗算に関する逆元 \(1/(1 - x)\) となる。

母関数と定数の積も同様の議論で正当化される。つまり、乗算則の特殊ケースとして次の規則が言える:

規則[定数倍則 (constant factor rule)]

任意の定数 \(c\) と母関数 \(F(x)\) に対して、次の等式が成り立つ:

\[ [x^{n}](c \cdot F(x)) = c \cdot [x^{n}] F(x) \tag{16.9}\]

16.2.3 畳み込み則

ここまでの議論を次の規則にまとめる:

規則[畳み込み則 (convolution rule)]

集合 \(\mathcal{A}\), \(\mathcal{B}\) が共通要素を持たないとする。集合 \(\mathcal{A}\) から何らかの条件に従って要素を選ぶ方法の個数の母関数が \(A(x)\) で、集合 \(\mathcal{B}\) から何らかの条件に従って要素を選ぶ方法の個数の母関数が \(B(x)\) のとき、同じ条件に従って和集合 \(\mathcal{A} \cup \mathcal{B}\) から要素を選ぶ方法の個数の母関数は \(A(x)B(x)\) である。

この規則では「同じ条件に従って和集合 \(\mathcal{A} \cup \mathcal{B}\) から要素を選択する」の意味が重要になる。直感的に言えば、これは \(\mathcal{A}\) と \(\mathcal{B}\) から要素を選ぶときに存在した制約が \(\mathcal{A} \cup \mathcal{B}\) から選ぶときにも課されることを意味する²。

16.2.4 畳み込み則を使ったドーナツの数え上げ

畳み込み則を使うと、チョコレートとプレーンのドーナツから \(n\) 個を選ぶ方法の個数の母関数 \(D(x)\) に関する等式 \(\text{(16.6)}\) の異なる導出が得られる。まず、\(n\) 個のチョコレートドーナツを選ぶ方法は \(n\) の値にかかわらず \(1\) 通りしか存在しない。これは、\(n\) 個のチョコレートを選ぶ方法の個数の母関数の係数が全て \(1\) であることを意味する。これまで何度か触れてきたように、この母関数は \(G(x) = 1/(1-x)\) である。同様に、\(n\) 個のプレーンドーナツを選ぶ方法の個数も同じ母関数を持つ。よって畳み込み則より、チョコレートとプレーンのドーナツの両方が選べるとき合計で \(n\) 個のドーナツを選ぶ方法の個数の母関数 \(D(x)\) は次のように計算できる:

\[ D(x) = \frac{1}{1 - x} \cdot \frac{1}{1 - x} = \frac{1}{(1 - x)^{2}} \]

これで等式 \(\text{(16.5)}\) を使わずに \(\text{(16.6)}\) を導出できた。

ちょうど今示した畳み込み則の応用は、ドーナツが \(2\) 種類ではなく \(k\) 種類ある一般化された問題にも適用できる。\(k\) 種類のドーナツから \(n\) 個を選ぶ方法の個数の母関数は \(1/(1 - x)^{k}\) である。この問題の解答は系 15.5.3 より \(\binom{n + (k - 1)}{n}\) なので、次の等式を得る:

\[ [x^{n}] \left( \frac{1}{(1 - x)^{k}} \right) = \binom{n + (k - 1)}{n} \tag{16.10}\]

Maclaurin の定理を使った係数の抽出

\(1 / (1 - x)^{k}\) の係数はドーナツの選び方の数え上げ問題を実際に解くことで求まった。しかし、この係数を代数的に求める方法も教育的な価値があるので示しておく。次の定理が利用される:

定理 16.2.1[Maclaurinマクローリンの定理 (Maclaurin's theorem)]

関数 \(f \colon \mathbb{R} \to \mathbb{R}\) が無限回微分可能なら、次の等式が成り立つ:

\[ f(x) = f(0) + f^{\prime} (0) x + \frac{f^{\prime\prime}(0)}{2!} x^{2} + \frac{f^{\prime\prime\prime}(0)}{3!} x^{3} + \cdots + \frac{f^{(n)}(0)}{n!} x^{n} + \cdots \]

この定理からは、\(1/(1-x)^{k}\) の \(x^{n}\) の係数を求めるには、この関数の \(n\) 次導関数を \(x = 0\) で評価した値を \(n!\) で割ればよいと分かる。\(1/(1-x)^{k}\) の \(n\) 次導関数の計算 (問題 16.5) はそれほど難しくない。次の等式が成り立つ:

\[ \frac{d^{n}}{d^{n}x} \frac{1}{(1 - x)^{k}} = k (k + 1) \cdots (k + n - 1) (1 - x)^{-(k + n)} \]

ここから次を得る:

\[ \begin{aligned} [x^{n}] \left( \frac{1}{(1 - x)^{k}} \right) &= \left( \frac{d^{n}}{d^{n}x} \frac{1}{(1 - x)^{k}} \right) (0) \cdot \frac{1}{n!} \\[15pt] &= \frac{k (k + 1) \cdots (k + n - 1) (1 - 0)^{-(k + n)}}{n!} \\[10pt] &= \binom{n + (k - 1)}{n} \end{aligned} \]

これで、ドーナツの選び方の個数を与える系 15.5.3 を使わずに \(x^{n}\) の係数を求めることができた。逆に、この代数的な議論と畳み込み則を使って系 15.5.3 を導くこともできる。

16.2.5 畳み込み則を使った二項定理の導出

畳み込み則からは二項定理 (定理 15.6.3) に関する新しい視点も得られる。単元集合 \(\left\{ a_{1} \right\}\) から \(n\) 個の異なる要素を選ぶ方法の個数の母関数は \(1 + x\) である: \(0\) 個の要素を選ぶ方法は \(1\) 個、\(1\) 個の要素を選ぶ方法は \(1\) 個あり、\(2\) 個以上の要素を選ぶ方法は存在しない。同様に、単元集合 \(\left\{ a_{i} \right\}\) から \(n\) 個の異なる要素を選ぶ方法の個数の母関数も \(1 + x\) である。よって畳み込み則より、集合 \(\left\{ a_{1}, a_{2}, \ldots, a_{m} \right\}\) から \(n\) 個の異なる要素を選ぶ方法の個数の母関数、言い換えれば \(n\) 要素部分集合の個数の母関数は、\(m\) 個の単元集合を個別に考えたときの母関数の積 \((1 + x)^{m}\) だと分かる。一方で、\(m\) 個の要素から異なる \(n\) 個を選ぶ方法の個数は \(\binom{m}{n}\) だから、次の等式が成り立つと結論できる:

\[ [x^{n}](1 + x)^{m} = \binom{m}{n} \]

これは二項定理 (定理 15.6.3) に等しい。こうして、\((1 + x)^{m}\) を積の和に展開した式を一切考えることなく二項定理の証明が完了した。

これまでに見たドーナツの選び方の数え上げや二項定理の導出は、母関数が強力な理由を示す例である:

母関数を使うと、数え上げの問題を代数的な式の操作で解けるようになる。逆に、代数的恒等式を数え上げの手法で証明できるようにもなる。

16.2.6 不条理な数え上げ問題

ここまでは以前に解いたことのある問題を母関数で考えてきた。次は、始めて目にする難しい ── というより、不条理な ── 数え上げ問題を考えてみよう。次の制約が満たされるように \(n\) 個のフルーツ (リンゴ・バナナ・オレンジ・ナシ) を選択する方法は何通りあるだろうか？

リンゴの個数は偶数
バナナの個数は \(5\) の倍数
オレンジの個数は \(4\) 個以下
ナシの個数は \(1\) 個以下

例えば、\(6\) 個のフルーツを選択する方法は \(7\) 通りある:

\[ \def\arraystretch{1.2}\begin{array}{c|ccccccc} \text{リンゴ} & 6 & 4 & 4 & 2 & 2 & 0 & 0 \\ \text{バナナ} & 0 & 0 & 0 & 0 & 0 & 5 & 5 \\ \text{オレンジ} & 0 & 2 & 1 & 4 & 3 & 1 & 0 \\ \text{ナシ} & 0 & 0 & 1 & 0 & 1 & 0 & 1 \end{array} \]

制約が非常に複雑なので、綺麗な解答を得るのは不可能に思える。しかし、母関数を考えると話が変わる。

まず、リンゴの選び方の個数の母関数 \(A(x)\) を考えよう。\(0\) 個のリンゴを選ぶ方法は \(1\) 通りある。リンゴの個数は偶数である必要があるので、\(1\) 個のリンゴを選ぶ方法は存在しない。\(2\) 個のリンゴを選ぶ方法は \(1\) 通りあり、\(3\) 個のリンゴを選ぶ方法は存在せず、以下同様となる。よって次の等式が分かる:

\[ A(x) = 1 + x^{2} + x^{4} + x^{6} + \cdots = \frac{1}{1 - x^{2}} \]

同様に、バナナの選び方の個数の母関数 \(B(x)\) は次のように表せる:

\[ B(x) = 1 + x^{5} + x^{10} + x^{15} + \cdots = \frac{1}{1 - x^{5}} \]

続いてオレンジの選び方の個数の母関数 \(O(x)\) を考えよう。\(0\) 個のオレンジを選ぶ方法は \(1\) 個あり、\(1\) 個や \(2\) 個の場合でも同様であるものの、オレンジは \(4\) 個までしか選べない。よって次の等式が分かる:

\[ O(x) = 1 + x + x^{2} + x^{3} + x^{4} = \frac{1 - x^{5}}{1 - x} \]

最後の変形では有限幾何級数の公式 \(\text{(14.2)}\) を使った。最後に、ナシは \(0\) 個または \(1\) 個しか選べない。ここからナシの選び方の個数の母関数 \(P(x)\) が分かる:

\[ P(x) = 1 + x \]

以上の事実と畳み込み則より、全てのフルーツが選べる場合の選び方の個数の母関数を計算できる:

\[ \begin{aligned} A(x)B(x)O(x)P(x) &= \frac{1}{1 - x^{2}} \cdot \frac{1}{1 - x^{5}} \cdot \frac{1 - x^{5}}{1 - x} \cdot (1 + x) \\[10pt] &= \frac{1}{(1 - x)^{2}} \\[10pt] &= 1 + 2x + 3x^{2} + 4x^{3} + \cdots \end{aligned} \]

ほとんどの部分式が打ち消される！最後に残るのは \(1/(1 - x^{2})\) であり、これに等しい冪級数は以前に見た。母関数の \(x^{n}\) の係数が \(n + 1\) なので、\(n\) 個のフルーツを選ぶ方法の個数は \(n + 1\) だと分かる。これは先ほど示した例と矛盾しない: \(6\) 個のフルーツを選ぶ方法は \(7\) 通りあった。素晴らしい！

この例は母関数による数え上げの有用性を強調するために意図的に作られたものである。ただ、単純に考えると母関数を使わない初等的な導出も存在するように思える。実はそういった導出も存在する (問題 16.8)。

訳注: 「ドーナツの選び方の個数の母関数」は正確には「ドーナツの選び方の個数を並べた無限列の母関数」あるいは「ドーナツの選び方の個数を並べた無限列が係数を並べた無限列に等しいような母関数」と表現すべきだが、長すぎるので省略した。以降も同様とした。 ↩︎
厳密に言えば「任意の \(n\) に対して、\(\mathcal{A} \cup \mathcal{B}\) から取った \(n\) 個の要素全体の集合と \(\mathcal{A}\) と \(\mathcal{B}\) から別々に取った計 \(n\) 個の要素 (を表す組) 全体の集合の間に全単射が存在する」とき畳み込み則は成り立つ。厳密でない表現でも読者は十分理解できるだろうと判断した。 ↩︎