高校数学解説

組み合わせに関する式を代数的に導出する

代数学,組合せ論　

108

$Z$ を整数全体の集合、 $N$ を $0$ 以上の整数全体の集合とする。

導入

次のことが知られている。

$n \in N, n > 0$ とする。

$n$ 個のボールをちょうど $n$ 色で塗り分ける方法は $n!$ 通りある。したがって、包除原理から

$\sum_{k = 0}^{n} (- 1)^{n - k}_{n} C_{k} k^{n} = n!$

が成り立つ。

この記事では、これを代数的な式変形によって証明する。

定義

二項係数

$n \in N, r \in Z$ に対し、 $_{n} C_{r}$ を以下で定義する。

$n = 0$ のとき、
- $r = 0$ のとき、 $_{0} C_{0} = 1$ とする。
- $r \neq 0$ のとき、 $_{0} C_{r} = 0$ とする。
$n > 0$ のとき、 $_{n} C_{r} =_{n - 1} C_{r - 1} +_{n - 1} C_{r}$ とする。

$_{0} C_{r}$ はクロネッカーのデルタを用いて $δ_{0 r}$ と書けるが、この記事ではこの性質を利用しない。

$n > 0$ のとき、 $_{n} C_{r}$ は $δ_{n r}$ と必ずしも等しいとは限らない。

差分

関数 $f : Z \to Z$ に対し、その差分 $Δ f$ を以下で定義する。

$Δ f (n) = f (n + 1) - f (n)$

また、 $\underset{n}{\underset{⏟}{Δ Δ \dots Δ}} f$ を $Δ^{n} f$ と書くことにする。

$Δ^{0} f = f$ である。

証明

いくつかの補題を示すことで行う。

$n \in N, n > 0, f : Z \to Z$ とする。
$\sum_{k = 0}^{n} (- 1)^{k}_{n} C_{k} f (k) = \sum_{k = 0}^{n - 1} - (- 1)^{k}_{n - 1} C_{k} Δ f (k)$

証明:

$\begin{aligned} \sum_{k = 0}^{n} (- 1)^{k}_{n} C_{k} f (k) \\ = & \sum_{k = 0}^{n} (- 1)^{k} (_{n - 1} C_{k - 1} +_{n - 1} C_{k}) f (k) \\ = & \sum_{k = 0}^{n} (- 1)^{k}_{n - 1} C_{k} f (k) + \sum_{k = 0}^{n} (- 1)^{k}_{n - 1} C_{k - 1} f (k) \\ = & \sum_{k = 0}^{n} (- 1)^{k}_{n - 1} C_{k} f (k) + 1 \cdot 0 \cdot f (0) + \sum_{k = 1}^{n} (- 1)^{k}_{n - 1} C_{k - 1} f (k) \\ = & \sum_{k = 0}^{n - 1} (- 1)^{k}_{n - 1} C_{k} f (k) + \sum_{k = 1}^{n} - (- 1)^{k - 1}_{n - 1} C_{k - 1} f (k) \\ = & \sum_{k = 0}^{n - 1} (- 1)^{k}_{n - 1} C_{k} f (k) + \sum_{k = 0}^{n - 1} - (- 1)^{k}_{n - 1} C_{k} f (k + 1) \\ = & \sum_{k = 0}^{n - 1} (- 1)^{k}_{n - 1} C_{k} (f (k) - f (k + 1)) \\ = & \sum_{k = 0}^{n - 1} - (- 1)^{k}_{n - 1} C_{k} Δ f (k) \end{aligned}$

差分の線形性

$a, b \in Z, f, g : Z \to Z$ とする。このとき、
$Δ (a f + b g) = a Δ f + b Δ g$
が成り立つ。

証明は非常に単純な式変形なので割愛する。

単項式の差分

$n \in N, n > 0$ とし、 $f (x) = x^{n}$ とする。このとき、 $Δ f$ は $n - 1$ 次式であり、その $n - 1$ 次の項の係数は $n$ である。

証明:

$\begin{aligned} Δ f \\ = & (x + 1)^{n} - x^{n} \\ = & \sum_{k = 0}^{n}_{n} C_{k} x^{k} - x^{n} \\ = & (\sum_{k = 0}^{n - 2}_{n} C_{k} x^{k} + n x^{n - 1} + x^{n}) - x^{n} \\ = & \sum_{k = 0}^{n - 2}_{n} C_{k} x^{k} + n x^{n - 1} \end{aligned}$

多項式の高階差分

$n \in N, a_{n}, \dots, a_{0} \in Z, a_{n} \neq 0$ とし、
$f (x) = a_{n} x^{n} + \dots + a_{1} x^{1} + a_{0} x^{0}$ であるとする。このとき、任意の $k \in N$ に対して次が成立する:
(1) $k > n$ であれば、 $Δ^{k} f = 0$ である。
(2) $k \leq n$ であれば、 $Δ^{k} f$ は $n - k$ 次式である。
(2) $k \leq n$ であれば、 $Δ^{k} f$ の最高次の項の係数は $a_{n} \cdot \frac{n!}{(n - k)!} = a_{n} \cdot n (n - 1) \dots (n - k + 1)$ である。

証明: $k$ に関する数学的帰納法によって行う。

$k = 0$ のとき、 $f$ は $n = n - 0$ 次式であり、最高次の項の係数が $a_{n} = a_{n} \cdot \frac{n!}{n!}$ であるから成り立つ。

$k = q$ で成り立つと仮定して $k = q + 1$ のとき、3つに場合分けする。

$q > n$ のとき、仮定から $Δ^{q} f = 0$ (定数関数)であり、いかなる $x$ に対しても $0 - 0 = 0$ が成立するので $Δ^{q + 1} f = 0$ も成り立つ。

$q = n$ のとき、仮定から $Δ^{q} f = a_{n} \cdot n!$ (定数関数)である。よって、 $q > n$ の時と同様に $Δ^{q + 1} f = 0$ が成り立つ。

$q < n$ のとき、 $(Δ^{q} f) (x) = a_{n} \cdot \frac{n!}{(n - q)!} x^{n - q} + Q (x)$ と書ける。ただし、 $b$ は整数であり、 $Q (x)$ は $n - q - 1$ 次以下の多項式である。このとき、

$\begin{aligned} (Δ^{q + 1} f) (x) \\ = & a_{n} \cdot \frac{n!}{(n - q)!} Δ (x^{n - q}) + Δ Q (x) \\ = & a_{n} \cdot \frac{n!}{(n - q)} \cdot ((n - q) (x^{n - q - 1}) + R (x)) + Δ Q (x) \end{aligned}$

である。ただし、 $R (x)$ は $n - q - 2$ 次以下の多項式である。

$Δ Q (x)$ も $n - q - 2$ 次以下であるから、

$a_{n} \cdot \frac{n!}{(n - q)!} \cdot (n - q) = a_{n} \cdot \frac{n!}{(n - q - 1)!}$

より $k = q + 1$ のときも成り立つことが示された。

よって、数学的帰納法により題意が示された。

ここから元の定理を証明する。

$n \in N$ とする。
$\sum_{k = 0}^{n} (- 1)^{n - k}_{n} C_{k} k^{n} = n!$

証明.

$\begin{aligned} \sum_{k = 0}^{n} (- 1)^{n - k}_{n} C_{k} k^{n} \\ = & (- 1)^{n} \sum_{k = 0}^{n} (- 1)^{- k}_{n} C_{k} k^{n} \\ = & (- 1)^{n} \sum_{k = 0}^{n} (- 1)^{k}_{n} C_{k} k^{n} \\ = & (- 1)^{n} \cdot (- 1)^{n} \sum_{k = 0}^{0} (- 1)^{k}_{n - n} C_{k} Δ^{n} k^{n} (補題1を n 回使った) \\ = & (- 1)^{2 n} \sum_{k = 0}^{0} (- 1)^{k}_{0} C_{k} n! \\ = & 1 (1 \cdot 1 \cdot n!) \\ = & n! \end{aligned}$