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

二項係数

289

以下では、$\c{p}{q}$で二項係数${}_{p}C_{q}$を表します。

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

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

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

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

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

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