二項係数の母関数で遊ぼう - シン・ぱいおつ日記

こんにちは.

ぱいです.

今日は, 数列のいろいろな性質を示すときに母関数が役に立つという話を書きます.

例えば, 二項係数 ${}_{n}\mathrm{C}_{k}$ に関する次の定理を見てみましょう.

ただし, ${}_{n} \mathrm{C}_{k}$ は, 非負整数 $n$ , $k$ ( $k \leq n$ ) に対して次の式で定義される数列です.

\begin{align} {}_{n} \mathrm{C}_{k} = \dfrac{n!}{ \ k!(n-k)! \ } \end{align}.

定理 (ア)

非負整数 $n$ , $m$ と正整数 $k \leq n,m$ に対して, 次の (1), (2), (3) が成り立つ.

(1)　 ${}_{n+1} \mathrm{C}_{k} = {}_{n} \mathrm{C}_{k} + {}_{n} \mathrm{C}_{k-1}$ .

(2)　 $(k+1) \cdot {}_{n+1} \mathrm{C}_{k+1} = (n+1) \cdot {}_{n} \mathrm{C}_{k}$ .

(3)　 ${}_{n+m} \mathrm{C}_{k} = \sum_{i=0}^{k} {}_{n} \mathrm{C}_{i} \cdot {}_{m} \mathrm{C}_{k-i}$ .

二項係数 ${}_{n} \mathrm{C}_{k}$ は, 組み合わせ論的には「 $n$ 個のモノから順番を考慮せず $k$ 個を選び出す方法が何通りあるか」を表す数としても知られています.

定理 (ア) の (1), (2) は多分中学・高校の教科書などにも載っている公式です.

次の 2 パターンの方針による証明に馴染みのある人も多いのではないでしょうか.

(方針①)　分数 $n! / k! (n-k)!$ を変形して代数的に証明する.

(方針②)　組み合わせ論的に, モノを選び出すという事象をいろいろな視点で考察しながら証明する.

でも, 定理 (ア) の (3) はあまり見慣れない公式で, ↑ の方針①, ②による証明は簡単ではないと思います (※).

(※ 僕は方針①②で (3) を証明する方法を思いついていないので, 思いついた方は教えていただけると嬉しいです！)

(2023/06/24 追記. 不自然対数くんに組み合わせ論的な考え方教えてもらって, 普通にめちゃめちゃシンプルな考え方で行けました (＊ｏ＊）なんで僕思いつかなかったんだろう…笑)

そこで役に立つのが, 「母関数」です！

この記事では, 数列 $a_{0}$ , $a_{1}$ , $a_{2}$ ... に対して, 次のように表せる関数 $G(t)$ を「数列 $\{ a_{k} \}$ の母関数」と呼ぶことにします.

(G は generating function (母関数) の頭文字から取りました.)

\begin{align} G(t) = a_{0} + a_{1}t + a_{2} t^{2} + \cdots . \end{align}

以下, 二項係数 ${}_{n} \mathrm{C}_{k}$ の母関数を求めて, 母関数を駆使しながら定理 (ア) を証明します！

二項係数の母関数
定理 (ア) の (1) の証明
定理 (ア) の (2) の証明
定理 (ア) の (3) の証明

二項係数の母関数

二項係数の母関数について, 「二項定理」と呼ばれる次の定理が成り立ちます.

二項定理

任意の非負整数 $n$ に対して, 次が成り立つ.
\begin{align} (1+t)^{n} = {}_{n}\mathrm{C}_{0} + {}_{n}\mathrm{C}_{1} \, t + {}_{n}\mathrm{C}_{2} \, t^{2} + \cdots + {}_{n}\mathrm{C}_{n} \, t^{n} \quad (\forall t \in \mathbb{C}) . \end{align}
(式が途切れていたら, 横スクロールで見れるようになると思います)

(証明)

$n$ を固定し, $G(t) = (1+t)^{n}$ と置く.

$f(t)$ は, $k$ 階導関数 $G^{(k)}(t)$ を用いて次のように表せる.

\begin{align} G(t) = G(0) + G^{(1)}(0) \, t + \dfrac{G^{(2)}(0)}{2} \, t^{2} + \cdots + \dfrac{G^{(k)}(0)}{k!} \, t^{k} + \cdots + \dfrac{G^{(n)}(0)}{n!} \, t^{n} . \end{align}

ここで, $G(t)$ の $k$ 階導関数は $G^{(k)}(t) = n(n-1)\cdots(n-k+1) (1+t)^{n-k}$ である.

よって, $G(t)$ を展開したときの $t^{k}$ の係数は次のように表せる.

\begin{align} \dfrac{G^{(k)}(0)}{k!} & = \dfrac{n(n-1)\cdots(n-k+1)}{k!} \\ & = \dfrac{ \ n! / (n-k)! \ }{k!} \\ & = {}_{n} \mathrm{C}_{k}. \end{align}

以上から, $(1+t)^{n}$ は次のように表せる.

\begin{align} (1+t)^{n} = {}_{n}\mathrm{C}_{0} + {}_{n}\mathrm{C}_{1} \, t + {}_{n}\mathrm{C}_{2} \, t^{2} + \cdots + {}_{n}\mathrm{C}_{n} \, t^{n} \quad (\forall t \in \mathbb{C}) . \end{align}

■

定理 (ア) の (1) の証明

二項係数の母関数 (二項定理) を駆使して, 定理 (ア) の (1) を証明します！

定理 (ア) の (1)　（再掲）

非負整数 $n$ と正整数 $k \leq n$ に対して, 次の等式が成り立つ.

\begin{align}{}_{n+1} \mathrm{C}_{k} = {}_{n} \mathrm{C}_{k} + {}_{n} \mathrm{C}_{k-1} . \end{align}

(証明)

非負整数 $n$ を任意に取り, $f(t) = (1+t)^{n+1}$ と置く.

二項定理より, $f(t)$ は次のように表せる.

\begin{align} f(t) = \sum_{k=0}^{n+1} {}_{n+1}\mathrm{C}_{k} \, t^{k}. \end{align}

一方, $(1+t)^{n+1} = (1+t)(1+t)^{n}$ より, $f(t)$ は次のようにも表せる.

\begin{align} f(t) & = (1+t) (1+t)^{n} \\ & = (1+t) \sum_{k = 0}^{n} {}_{n}\mathrm{C}_{k} \, t^{k} \\ & = 1 \cdot \sum_{k = 0}^{n} {}_{n}\mathrm{C}_{k} \, t^{k} + t \cdot \sum_{k = 0}^{n} {}_{n}\mathrm{C}_{k} \, t^{k} \\ & = \sum_{k = 0}^{n} {}_{n}\mathrm{C}_{k} \, t^{k} + \sum_{\ell = 1}^{n+1} {}_{n}\mathrm{C}_{\ell - 1} \, t^{\ell} \\ & = {}_{n}\mathrm{C}_{0} + \sum_{k = 1}^{n} \big( {}_{n}\mathrm{C}_{k} + {}_{n}\mathrm{C}_{k-1} \big) \, t^{k} + {}_{n+1}\mathrm{C}_{n+1} \, t^{n+1} . \end{align}

$f(t)$ の2つの表し方について, 各 $t^{k}$ の係数を見比べれば, 次の公式が得られる.

\begin{align}{}_{n+1} \mathrm{C}_{k} = {}_{n} \mathrm{C}_{k} + {}_{n} \mathrm{C}_{k-1} . \end{align}

■

定理 (ア) の (2) の証明

二項係数の母関数 (二項定理) を駆使して, 定理 (ア) の (2) を証明します！

定理 (ア) の (2)　(再掲)

非負整数 $n$ , $k$ ( $k \leq n$ ) に対して, 次の等式が成り立つ.

\begin{align} (k+1) \cdot {}_{n+1} \mathrm{C}_{k+1} = (n+1) \cdot {}_{n} \mathrm{C}_{k} . \end{align}

(証明)

非負整数 $n$ を任意に取り, $g(t) = (1+t)^{n+1}$ と置く.

$g(t)$ の導関数について, 二項定理で展開してから項別微分をすると, 次のように表せる.

\begin{align} \dfrac{\mathrm{d}}{\mathrm{d}t} g(t) & = \dfrac{\mathrm{d}}{\mathrm{d}t} \sum_{\ell = 0}^{n+1} {}_{n+1}\mathrm{C}_{\ell} \, t^{\ell} \\ & = \sum_{\ell = 0}^{n+1} \dfrac{\mathrm{d}}{\mathrm{d}t} \, {}_{n+1}\mathrm{C}_{\ell} \, t^{\ell} \\ & = \sum_{\ell=1}^{n+1} \, \ell \cdot {}_{n+1}\mathrm{C}_{\ell} \, t^{\ell -1} \\ & = \sum_{k=0}^{n} \, (k+1) \cdot {}_{n+1}\mathrm{C}_{k+1} \, t^{k}. \end{align}

一方. 合成関数の微分で次のようにも表せる.

\begin{align} \dfrac{\mathrm{d}}{\mathrm{d}t} g(t) & = \dfrac{\mathrm{d}}{\mathrm{d}t} (1+t)^{n+1} \\ & = (n+1) (1+t)^{n} \\ & = (n+1) \sum_{k=0}^{n} {}_{n}\mathrm{C}_{k} \, t^{k} \\ & = \sum_{k=0}^{n} \, (n+1) \cdot {}_{n} \mathrm{C}_{k} \, t^{k}. \end{align}

$\tfrac{\mathrm{d}}{\mathrm{d}t} g(t)$ の2つの表し方について, 各 $t^{k}$ の係数を見比べれば, 次の公式が得られる.

\begin{align} (k+1) \cdot {}_{n+1} \mathrm{C}_{k+1} = (n+1) \cdot {}_{n} \mathrm{C}_{k} . \end{align}

■

定理 (ア) の (3) の証明

二項係数の母関数 (二項定理) を駆使して, 定理 (ア) の (3) を証明します！

定理 (ア) の (3)　（再掲）

非負整数 $n$ , $m$ , $k$ ( $k \leq n,m$ ) に対して, 次の等式が成り立つ.

\begin{align} {}_{n+m} \mathrm{C}_{k} = \sum_{i=0}^{k} {}_{n} \mathrm{C}_{i} \cdot {}_{m} \mathrm{C}_{k-i}. \end{align}

(証明)

非負整数 $n$ , $m$ を任意に取り, $h(t) = (1+t)^{n+m}$ と置く.

二項定理より, $h(t)$ は次のように表せる.

\begin{align} h(t) & = \sum_{k=0}^{n+m} {}_{n+m}\mathrm{C}_{k} \, t^{k}. \end{align}

一方, $h(t) = (1+t)^{n} (1+t)^{m}$ と分解してそれぞれの項で分けて二項定理を用いることで, 次のようにも表せる.

\begin{align} h(t) & = (1+t)^{n} (1+t)^{m} \\ & = \left( \sum_{i=0}^{n} {}_{n}\mathrm{C}_{i} \, t^{i} \right) \left( \sum_{j=0}^{m} {}_{m}\mathrm{C}_{j} \, t^{j} \right) \\ & = \sum_{k=0}^{n+m} \left( \sum_{i=0}^{k} {}_{n}\mathrm{C}_{i} \cdot {}_{m}\mathrm{C}_{k-i} \right) \, t^{k}. \end{align}

$h(t)$ の2つの表し方について, 各 $t^{k}$ の係数を見比べれば, 次の公式が得られる.

\begin{align} {}_{n+m} \mathrm{C}_{k} = \sum_{i=0}^{k} {}_{n} \mathrm{C}_{i} \cdot {}_{m} \mathrm{C}_{k-i}. \end{align}

■

分数をごちゃごちゃ計算したり, 組み合わせ論的な複雑な考え方をしなくても, 級数の形式的な操作だけで定理 (ア) の 3 つの公式が証明できました！

母関数って便利で強力な道具ですね♪

最後まで読んでいただき, ありがとうございました！