こんにちは.
ぱいです.
今日は, 数列のいろいろな性質を示すときに母関数が役に立つという話を書きます.
例えば, 二項係数 に関する次の定理を見てみましょう.
ただし, は, 非負整数 , () に対して次の式で定義される数列です.
\begin{align} {}_{n} \mathrm{C}_{k} = \dfrac{n!}{ \ k!(n-k)! \ } \end{align}.
定理 (ア)
非負整数 , と正整数 に対して, 次の (1), (2), (3) が成り立つ.
(1)
.
(2) .
(3)
.
二項係数 は, 組み合わせ論的には「 個のモノから順番を考慮せず 個を選び出す方法が何通りあるか」を表す数としても知られています.
定理 (ア) の (1), (2) は多分中学・高校の教科書などにも載っている公式です.
次の 2 パターンの方針による証明に馴染みのある人も多いのではないでしょうか.
(方針①) 分数 を変形して代数的に証明する.
(方針②) 組み合わせ論的に, モノを選び出すという事象をいろいろな視点で考察しながら証明する.
でも, 定理 (ア) の (3) はあまり見慣れない公式で, ↑ の方針①, ②による証明は簡単ではないと思います (※).
(※ 僕は方針①②で (3) を証明する方法を思いついていないので, 思いついた方は教えていただけると嬉しいです!)
(2023/06/24 追記. 不自然対数くんに組み合わせ論的な考え方教えてもらって, 普通にめちゃめちゃシンプルな考え方で行けました (*o*)なんで僕思いつかなかったんだろう…笑)
そこで役に立つのが, 「母関数」です!
この記事では, 数列 , , ... に対して, 次のように表せる関数 を「数列 の母関数」と呼ぶことにします.
(G は generating function (母関数) の頭文字から取りました.)
\begin{align} G(t) = a_{0} + a_{1}t + a_{2} t^{2} + \cdots . \end{align}
以下, 二項係数 の母関数を求めて, 母関数を駆使しながら定理 (ア) を証明します!
続きを読む