問題.
今回は, 自作問題の1-(12), コンビネーションを含む計算の解答・解説です.
問題.
\({}_0C_0=1\)とする. \(n\geqq j\geqq0\)を満たす整数\(n, j\)について
\(\displaystyle \sum_{i=j}^n {(-1)^i\cdot{}_nC_i\cdot{}_iC_j}\)
を計算せよ.
こういった問題では\(n\)や\(j\)として小さい数(0, 1, 2)などを実際に入れて計算してみることで答えを予想すると筋道が立ちやすいかもしれません.
コンビネーションの記号の定義
\( {}_nC_i = \dfrac{n!}{i!(n-i)!}\)
を利用して上手く式を変形します.
また, 2項定理から導かれる次の等式も利用することになります.
\(\displaystyle \sum_{l=0}^N (-1)^l\cdot{}_NC_l=(-1+1)^N=0\)
解答例.
\begin{align*}
S(n, j) = \sum_{i=j}^n (-1)^i\cdot{}_nC_{i}\cdot{}_iC_j
\end{align*}
とおく.
[1] \(n=j\)のとき
\begin{align*}
S(n, n) &= (-1)^n\cdot{}_nC_n\cdot{}_nC_n\\
&= (-1)^n
\end{align*}
[2] \(n>j\)のとき
\begin{align*}
{}_nC_i\cdot{}_iC_j &= \dfrac{n!}{i!(n-i)!}\cdot\dfrac{i!}{j!(i-j)!}\\
&= \dfrac{n!}{j!(i-j)!(n-i)!}\\
&= \dfrac{n!}{j!(n-j)!}\cdot\dfrac{(n-j)!}{(i-j)!(n-i)!}\\
&= {}_nC_j\cdot {}_{n-j}C_{i-j}
\end{align*}
なので,
\begin{align*}
S(n, j) = \sum_{i=j}^n (-1)^i\cdot{}_nC_j\cdot {}_{n-j}C_{i-j}
\end{align*}
\(i-j=m\)とおくと, \(i\)が\(j\)から\(n\)まで増えるとき, \(m\)は\(0\)から\(n-j\)まで増えることになるので,
\begin{align*}
S(n, j) &= \sum_{m=0}^{n-j} (-1)^{m+j}\cdot{}_nC_j\cdot{}_{n-j}C_m\\
&= (-1)^j\cdot{}_nC_j\cdot\sum_{m=0}^{n-j} (-1)^m\cdot{}_{n-j}C_{m}\\
&= (-1)^j\cdot{}_nC_j\cdot(1-1)^{n-j}\\
&= (-1)^j\cdot{}_nC_j\cdot 0\\
&= 0
\end{align*}
以上より,
\begin{align*}
\sum_{i=j}^n (-1)^i\cdot{}_nC_i\cdot {}_iC_j = \left\{
\begin{array}{ll}
(-1)^n & (n=j\geqq 0)\\
0 & (n>j\geqq 0)
\end{array}\right.
\end{align*}