組み合わせに関する式を代数的に導出する
$$ \newcommand{\ncr}[2]{{}_{#1} \mathrm{C} _{#2}} $$
$ \mathbb{Z} $を整数全体の集合、$ \mathbb{N} $を$ 0 $以上の整数全体の集合とする。
導入
次のことが知られている。
$ n \in \mathbb{N}, n > 0 $とする。
$ n $個のボールをちょうど$ n $色で塗り分ける方法は$ n! $通りある。したがって、包除原理から
$$ \sum_{k=0}^n (-1)^{n-k} \ncr{n}{k} k^n = n! $$
が成り立つ。
この記事では、これを代数的な式変形によって証明する。
定義
$ n \in \mathbb{N}, r \in \mathbb{Z} $に対し、$ \ncr{n}{r} $を以下で定義する。
- $ n = 0 $のとき、
- $ r = 0 $のとき、$ \ncr{0}{0} = 1 $とする。
- $ r \neq 0 $のとき、$ \ncr{0}{r} = 0 $とする。
- $ n > 0 $のとき、$ \ncr{n}{r} = \ncr{n - 1}{r - 1} + \ncr{n - 1}{r} $とする。
$ \ncr{0}{r} $はクロネッカーのデルタを用いて$ \delta_{0r} $と書けるが、この記事ではこの性質を利用しない。
$ n > 0 $のとき、$ \ncr{n}{r} $は$ \delta_{nr} $と必ずしも等しいとは限らない。
関数$ f: \mathbb{Z} \rightarrow \mathbb{Z} $に対し、その差分$ \Delta f $を以下で定義する。
$$ \Delta f (n) = f(n + 1) - f(n) $$
また、$ \underbrace{\Delta\Delta\cdots\Delta}_{n}f $を$ \Delta^n f $と書くことにする。
$ \Delta^0 f = f $である。
証明
いくつかの補題を示すことで行う。
$ n \in \mathbb{N}, n > 0, f : \mathbb{Z} \rightarrow \mathbb{Z} $とする。
$$ \sum_{k = 0}^{n} (-1)^k \ncr{n}{k} f(k) = \sum_{k = 0}^{n-1} -(-1)^k \ncr{n-1}{k} \Delta f(k) $$
証明:
\begin{align*} & \sum_{k = 0}^{n} (-1)^k \ncr{n}{k} f(k) \\ =& \sum_{k = 0}^{n} (-1)^k (\ncr{n-1}{k-1} + \ncr{n-1}{k}) f(k) \\ =& \sum_{k = 0}^{n} (-1)^k \ncr{n-1}{k} f(k) + \sum_{k = 0}^{n} (-1)^k \ncr{n-1}{k-1} f(k) \\ =& \sum_{k = 0}^{n} (-1)^k \ncr{n-1}{k} f(k) + 1 \cdot 0 \cdot f(0) + \sum_{k = 1}^{n} (-1)^k \ncr{n-1}{k-1} f(k) \\ =& \sum_{k = 0}^{n-1} (-1)^k \ncr{n-1}{k} f(k) + \sum_{k = 1}^{n} -(-1)^{k-1} \ncr{n-1}{k-1} f(k) \\ =& \sum_{k = 0}^{n-1} (-1)^k \ncr{n-1}{k} f(k) + \sum_{k = 0}^{n-1} -(-1)^{k} \ncr{n-1}{k} f(k+1) \\ =& \sum_{k = 0}^{n-1} (-1)^k \ncr{n-1}{k} (f(k) - f(k+1)) \\ =& \sum_{k = 0}^{n-1} -(-1)^k \ncr{n-1}{k} \Delta f(k) \end{align*}
$ a, b \in \mathbb{Z}, f, g : \mathbb{Z} \rightarrow \mathbb{Z} $とする。このとき、
$ \Delta(af + bg) = a \Delta f + b \Delta g $
が成り立つ。
証明は非常に単純な式変形なので割愛する。
$ n \in \mathbb{N}, n > 0 $とし、$ f(x) = x^n $とする。このとき、$ \Delta f $は$ n - 1 $次式であり、その$ n - 1 $次の項の係数は$ n $である。
証明:
\begin{align*} & \Delta f \\ =& (x+1)^n - x^n \\ =& \sum_{k=0}^n \ncr{n}{k} x^k - x^n \\ =& \left(\sum_{k=0}^{n-2} \ncr{n}{k} x^k + nx^{n-1} + x^n \right) - x^n \\ =& \sum_{k=0}^{n-2} \ncr{n}{k} x^k + nx^{n-1} \end{align*}
$ n \in \mathbb{N}, a_n, \cdots, a_0 \in \mathbb{Z}, a_n \neq 0 $とし、
$$ f(x) = a_n x^n + \cdots + a_1 x^1 + a_0 x^0 $$であるとする。このとき、任意の$ k \in \mathbb{N} $に対して次が成立する:
(1) $ k > n $であれば、$ \Delta^k f = 0 $である。
(2) $ k \leq n $であれば、$ \Delta^k f $は$ n - k $次式である。
(2) $ k \leq n $であれば、$ \Delta^k f $の最高次の項の係数は$ a_n \cdot \frac {n!}{(n-k)!} = a_n \cdot n(n-1)\cdots(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 $のとき、仮定から$ \Delta^q f = 0 $(定数関数)であり、いかなる$ x $に対しても$ 0 - 0 = 0 $が成立するので$ \Delta^{q + 1} f = 0 $も成り立つ。
$ q = n $のとき、仮定から$ \Delta^q f = a_n \cdot n! $(定数関数)である。よって、$ q > n $の時と同様に$ \Delta^{q + 1} f = 0 $が成り立つ。
$ q < n $のとき、$ (\Delta^q f)(x) = a_n \cdot \frac{n!}{(n-q)!} x^{n-q} + Q(x) $と書ける。ただし、$ b $は整数であり、$ Q(x) $は$ n - q - 1 $次以下の多項式である。このとき、
\begin{align*} & (\Delta^{q+1} f)(x) \\ =& a_n \cdot \frac{n!}{(n-q)!} \Delta(x^{n-q}) + \Delta Q(x) \\ =& a_n \cdot \frac{n!}{(n-q)} \cdot \left((n-q) (x^{n-q-1}) + R(x)\right) + \Delta Q(x) \\ \end{align*}
である。ただし、$ R(x) $は$ n - q - 2 $次以下の多項式である。
$ \Delta 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 \mathbb{N} $とする。
$$ \sum_{k=0}^n (-1)^{n-k} \ncr{n}{k} k^n = n! $$
証明.
\begin{align*} & \sum_{k=0}^n (-1)^{n-k} \ncr{n}{k} k^n \\ =& (-1)^n \sum_{k=0}^n (-1)^{-k} \ncr{n}{k} k^n \\ =& (-1)^n \sum_{k=0}^n (-1)^{k} \ncr{n}{k} k^n \\ =& (-1)^n \cdot (-1)^n \sum_{k=0}^0 (-1)^{k} \ncr{n-n}{k} \Delta^n k^n \hspace{5mm}(\text{補題1を}n\text{回使った}) \\ =& (-1)^{2n} \sum_{k=0}^0 (-1)^{k} \ncr{0}{k} n! \\ =& 1 (1 \cdot 1 \cdot n!) \\ =& n! \end{align*}
(Q.E.D.)
あとがき
組み合わせに関する式を、包除原理を使わずに式変形だけで導出することができました。「補題1が包除原理なんじゃないか」「数学的帰納法は使っていいのか」「$ \Delta $は解析学から盗んできたんじゃないのか」などと言われそうですが、主要な部分を式変形だけで解くことができて数学の優しさを感じました。
