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

区別できる$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}$$
通り。

以上から、題意は示された。