文献あり

ある二項係数の数式について

328

以下では、 $(\begin{matrix} p \\ q \end{matrix})$ で二項係数 $_{p} C_{q}$ を表します。

先日Wikipediaのこちらの記事で次のような式を見つけました $:$

$0 \leq q \leq n$ をみたす整数 $q, n$ に対して
$\sum_{k = q}^{n} (\begin{matrix} n \\ k \end{matrix}) (\begin{matrix} k \\ q \end{matrix}) = (\begin{matrix} n \\ q \end{matrix}) 2^{n - q}$
が成り立つ。

今回はこれを一般化した主張 $:$

$0 \leq q \leq n, 1 \leq i < N$ をみたす整数 $q, n, i, N$ に対して
$\sum_{k = q}^{n} (\begin{matrix} n \\ k \end{matrix}) (\begin{matrix} k \\ q \end{matrix}) i^{k - q} (N - i)^{n - k} = (\begin{matrix} n \\ q \end{matrix}) N^{n - q}$
が成り立つ。

を思いついたので、証明していきたいと思います。
(実際に、この式で $N = 2$ とすれば $i = 1$ となって最初の式と一致します)

区別できる $n$ 個のボールを、 $A_{1}, A_{2}, \dots, A_{N}, X$ の計 $N + 1$ 色で塗り分けることを考える( $A_{1}, A_{2}, \dots, A_{N}$ のうち使われない色があってもよいものとする)。ただし、このとき色 $X$ で塗られるボールがちょうど $q$ ( $0 \leq q \leq n$ )個であるようにする。このような方法を $2$ 通りで数え上げる。
( $1$ 通りめ)
色 $X$ で塗られるボールをはじめに選ぶ方法は $(\begin{matrix} n \\ q \end{matrix})$ 通り。
残りの $n - q$ 個のボールを $N$ 色で塗り分ける方法は、 $1$ つのボールにつき $N$ 通りの色の選択があることから $N^{n - q}$ 通り。
よって、ボールの塗り分け方は $(\begin{matrix} n \\ q \end{matrix}) N^{n - q}$ 通り。
( $2$ 通りめ)
$A_{1}, A_{2}, \dots, A_{i}, X (1 \leq i < N)$ の $i + 1$ 色で塗られるボールが $k$ ( $q \leq k \leq n)$ 個であるとする。
はじめに $k$ 個のボールを選ぶ方法は $(\begin{matrix} n \\ k \end{matrix})$ 通り。
この $k$ 個のボールの中から色 $X$ で塗られる $q$ 個のボールを選ぶ方法は $(\begin{matrix} k \\ q \end{matrix})$ 通り。
$k$ 個のボールのうち色 $X$ で塗られない $k - q$ 個のボールを塗り分ける方法は $i^{k - q}$ 通り。
$n$ 個のボールのうち残りの $n - k$ 個のボールを、残りの $N - i$ 色で塗り分ける方法は $(N - i)^{n - k}$ 通り。
以上より、 $k$ はちょうど $q \leq k \leq n$ を動くから、ボールの塗り分け方は
$\sum_{k = q}^{n} (\begin{matrix} n \\ k \end{matrix}) (\begin{matrix} k \\ q \end{matrix}) i^{k - q} (N - i)^{n - k}$
通り。