シグマとnCr | 教えて数学理科

\(\require{cancel}\)

\({}_n\mathrm{C}_r\) を含むシグマ計算の例題です。

二項定理
\((1+x)^n={}_n\mathrm{C}_0+{}_n\mathrm{C}_1x+{}_n\mathrm{C}_2x^2+\cdots+{}_n\mathrm{C}_nx^n\)
が基本となります。この\(x\)に\(1\)や\(-1\)などの数字を適宜代入することになります。

(例題1)次の等式を証明せよ。ただし\(n\)は自然数とする。
(1)\(\displaystyle\sum_{k=1}^{n}k\cdot{}_n\mathrm{C}_k=n\cdot2^{n-1}\)

(2)\(\displaystyle\sum_{k=1}^{n}k^2\cdot{}_n\mathrm{C}_k=n(n+1)\cdot2^{n-2}\)

どちらも左辺の\(k,k^2\)が残っていると、\((1+x)^n\) の式に代入してもうまくいかないので、まず\(k,k^2\)を消す方向で進めていきます。
なお微分(数Ⅲ)を利用した別解もあります。

(解答)
(1)
(左辺)
\(=\displaystyle\sum_{k=1}^{n}k\cdot{}_n\mathrm{C}_k\)
\(=\displaystyle\sum_{k=1}^{n}\bcancel{k}\cdot\displaystyle\frac{n!}{(n-k)!\cdot \bcancel{k!}}\)

\(=\displaystyle\sum_{k=1}^{n}\displaystyle\frac{n!}{(n-k)!\cdot (k-1)!}\)

(分母に着目して \((n-k)+(k-1)=n-1\) で、\({}_{n-1}\mathrm{C}_{k-1}=\displaystyle\frac{(n-1)!}{(n-k)!\cdot(k-1)!}\) より)

\(=\displaystyle\sum_{k=1}^{n}n\cdot\displaystyle\frac{(n-1)!}{(n-k)!\cdot (k-1)!}\)

\(=\displaystyle\sum_{k=1}^{n}n\cdot{}_{n-1}\mathrm{C}_{k-1}\)

\(=n\displaystyle\sum_{k=1}^{n}{}_{n-1}\mathrm{C}_{k-1}\)

ここで
\(\displaystyle\sum_{k=1}^{n}{}_{n-1}\mathrm{C}_{k-1}={}_{n-1}\mathrm{C}_{0}+{}_{n-1}\mathrm{C}_{1}+\cdots+{}_{n-1}\mathrm{C}_{n-1}\)
であり

(\({}_{n-1}\mathrm{C}\)の形なので \(n-1\)乗を考えて)

\((1+x)^{n-1}={}_{n-1}\mathrm{C}_{0}+{}_{n-1}\mathrm{C}_{1}x+\cdots+{}_{n-1}\mathrm{C}_{n-1}x^{n-1}\)

\(x=1\) を代入すると
\(2^{n-1}={}_{n-1}\mathrm{C}_{0}+{}_{n-1}\mathrm{C}_{1}+\cdots+{}_{n-1}\mathrm{C}_{n-1}\)　だから

(左辺)\(=n\cdot2^{n-1}\)

(2)
(左辺)
\(=\displaystyle\sum_{k=1}^{n}k^2\cdot{}_n\mathrm{C}_k\)

\(=\displaystyle\sum_{k=1}^{n}k^2\cdot\displaystyle\frac{n!}{(n-k)!\cdot k!}\)

\(=\displaystyle\sum_{k=1}^{n}k\cdot\displaystyle\frac{n!}{(n-k)!\cdot (k-1)!}\)

さらに\(k\)を消去するために、\(k=(k-1)+1\) と変形します。

\(=\displaystyle\sum_{k=1}^{n}\{(k-1)+1\}\cdot\displaystyle\frac{n!}{(n-k)!\cdot (k-1)!}\)

\(=\displaystyle\sum_{k=1}^{n}(k-1)\cdot\displaystyle\frac{n!}{(n-k)!\cdot (k-1)!}+\displaystyle\sum_{k=1}^{n}\displaystyle\frac{n!}{(n-k)!\cdot (k-1)!}\)

左側のシグマについて\(k=1\) のときは\(0\)になるので、\(k=2,3,\cdots\) として分母分子を\(k-1\)で割ります。

\(=\displaystyle\sum_{k=2}^{n}\displaystyle\frac{n!}{(n-k)!\cdot (k-2)!}+\displaystyle\sum_{k=1}^{n}\displaystyle\frac{n!}{(n-k)!\cdot (k-1)!}\)

\(=n(n-1)\displaystyle\sum_{k=2}^{n}\displaystyle\frac{(n-2)!}{(n-k)!\cdot (k-2)!}+n\displaystyle\sum_{k=1}^{n}\displaystyle\frac{(n-1)!}{(n-k)!\cdot (k-1)!}\)

\(=n(n-1)\displaystyle\sum_{k=2}^{n}{}_{n-2}\mathrm{C}_{k-2}+n\displaystyle\sum_{k=1}^{n}{}_{n-1}\mathrm{C}_{k-1}\)

ここで
\(\displaystyle\sum_{k=2}^{n}{}_{n-2}\mathrm{C}_{k-2}={}_{n-2}\mathrm{C}_{0}+{}_{n-2}\mathrm{C}_{1}+\cdots+{}_{n-2}\mathrm{C}_{n-2}\)
であり

\((1+x)^{n-2}={}_{n-2}\mathrm{C}_{0}+{}_{n-2}\mathrm{C}_{1}x+\cdots+{}_{n-2}\mathrm{C}_{n-2}x^{n-2}\)

\(x=1\) を代入して
\(2^{n-2}={}_{n-2}\mathrm{C}_{0}+{}_{n-2}\mathrm{C}_{1}+\cdots+{}_{n-2}\mathrm{C}_{n-2}\)
だから、(1)とあわせて

\(n(n-1)\displaystyle\sum_{k=2}^{n}{}_{n-2}\mathrm{C}_{k-2}+n\displaystyle\sum_{k=1}^{n}{}_{n-1}\mathrm{C}_{k-1}\)

\(=n(n-1)\cdot2^{n-2}+n\cdot2^{n-1}\)

\(=n(n-1)\cdot2^{n-2}+2n\cdot2^{n-2}\)

\(=n(n+1)\cdot2^{n-2}\)

(微分利用の別解)
(1)
\((1+x)^{n}={}_n\mathrm{C}_0+{}_n\mathrm{C}_1x+{}_n\mathrm{C}_2x^2+{}_n\mathrm{C}_3x^3+\cdots+{}_n\mathrm{C}_nx^n\)

両辺を\(x\)で微分すると
\(n(1+x)^{n-1}={}_n\mathrm{C}_1+2{}_n\mathrm{C}_2x+3{}_n\mathrm{C}_3x^2+\cdots+\cdots+n{}_n\mathrm{C}_nx^{n-1}\)

\(x=1\) を代入して
\(n\cdot2^{n-1}={}_n\mathrm{C}_1+2{}_n\mathrm{C}_2+3{}_n\mathrm{C}_3+\cdots+\cdots+n{}_n\mathrm{C}_n\)

\(=\displaystyle\sum_{k=1}^{n}k\cdot{}_n\mathrm{C}_k\)

(2)
(1)より
\(n(1+x)^{n-1}={}_n\mathrm{C}_1+2{}_n\mathrm{C}_2x+3{}_n\mathrm{C}_3x^2+\cdots+\cdots+n{}_n\mathrm{C}_nx^{n-1}\)

係数が2乗になるように両辺\(x\)倍して再び微分します。

両辺\(x\)倍して
\(nx(1+x)^{n-1}={}_n\mathrm{C}_1x+2{}_n\mathrm{C}_2x^2+3{}_n\mathrm{C}_3x^3+\cdots+\cdots+n{}_n\mathrm{C}_nx^{n}\)

\(x\)で微分して
\(n(1+x)^{n-1}+nx(n-1)(1+x)^{n-2}\)
\(={}_n\mathrm{C}_1x+2^2{}_n\mathrm{C}_2x+3^2{}_n\mathrm{C}_3x^2+\cdots+n^2{}_n\mathrm{C}_nx^{n-1}\)

\(x=1\)を代入して
\(n\cdot2^{n-1}+n(n-1)2^{n-2}\)
\(={}_n\mathrm{C}_1+2^2{}_n\mathrm{C}_2+3^2{}_n\mathrm{C}_3+\cdots+n^2{}_n\mathrm{C}_n\)・・・(A)

((A)の左辺)
\(=n\cdot2^{n-1}+n(n-1)2^{n-2}\)
\(=2n\cdot2^{n-2}+n(n-1)2^{n-2}\)
\(=n(n+1)\cdot2^{n-2}\)

((A)の右辺)
\(=\displaystyle\sum_{k=1}^{n}k^2\cdot{}_n\mathrm{C}_k\)

よって
\(\displaystyle\sum_{k=1}^{n}k^2\cdot{}_n\mathrm{C}_k=n(n+1)\cdot2^{n-2}\)

(例題2)
\(\displaystyle\sum_{k=0}^{n-1}\displaystyle\frac{{}_{2n}\mathrm{C}_{2k+1}}{2k+2}\) を求めよ。ただし\(n\)は自然数とする。

同様に分母の\(2k+1\) を消去する方針でいきます。
なお別解として積分する方法もあります。

(解答)
\(\displaystyle\sum_{k=0}^{n-1}\displaystyle\frac{{}_{2n}\mathrm{C}_{2k+1}}{2k+2}\)

\(=\displaystyle\sum_{k=0}^{n-1}\displaystyle\frac{1}{2k+2}\cdot\displaystyle\frac{(2n)!}{(2n-2k-1)!\cdot(2k+1)!}\)

\(=\displaystyle\sum_{k=0}^{n-1}\displaystyle\frac{(2n)!}{(2n-2k-1)!\cdot(2k+2)!}\)

(\((2n-2k-1)+(2k+2)=2n+1\) に着目して)

\(=\displaystyle\frac{1}{2n+1}\displaystyle\sum_{k=0}^{n-1}\displaystyle\frac{(2n+1)!}{(2n-2k-1)!\cdot(2k+2)!}\)

\(=\displaystyle\frac{1}{2n+1}\displaystyle\sum_{k=0}^{n-1}{}_{2n+1}\mathrm{C}_{2k+2}\)

ここで
\(\displaystyle\sum_{k=0}^{n-1}{}_{2n+1}\mathrm{C}_{2k+2}={}_{2n+1}\mathrm{C}_{2}+{}_{2n+1}\mathrm{C}_{4}+\cdots+{}_{2n+1}\mathrm{C}_{2n}\)

とびとびになっていますが、とりあえず \((1+x)^{2n+1}\) を考えます。

\((1+x)^{2n+1}\)
\(={}_{2n+1}\mathrm{C}_{0}+{}_{2n+1}\mathrm{C}_{1}x+{}_{2n+1}\mathrm{C}_{2}x^2+{}_{2n+1}\mathrm{C}_{3}x^3+{}_{2n+1}\mathrm{C}_{4}x^4+\cdots+{}_{2n+1}\mathrm{C}_{2n}x^{2n}+{}_{2n+1}\mathrm{C}_{2n+1}x^{2n+1}\)・・・①

①に\(x=1\)と、符号を交互にするために\(x=-1\) を代入します。

①に\(x=1,-1\)を代入して

\(2^{2n+1}={}_{2n+1}\mathrm{C}_{0}+{}_{2n+1}\mathrm{C}_{1}+{}_{2n+1}\mathrm{C}_{2}+{}_{2n+1}\mathrm{C}_{3}+{}_{2n+1}\mathrm{C}_{4}+\cdots+{}_{2n+1}\mathrm{C}_{2n}+{}_{2n+1}\mathrm{C}_{2n+1}\)・・・②

\(0={}_{2n+1}\mathrm{C}_{0}-{}_{2n+1}\mathrm{C}_{1}+{}_{2n+1}\mathrm{C}_{2}-{}_{2n+1}\mathrm{C}_{3}+{}_{2n+1}\mathrm{C}_{4}+\cdots+{}_{2n+1}\mathrm{C}_{2n}-{}_{2n+1}\mathrm{C}_{2n+1}\)・・・③

②+③より
\(2^{2n+1}=2({}_{2n+1}\mathrm{C}_{0}+{}_{2n+1}\mathrm{C}_{2}+{}_{2n+1}\mathrm{C}_{4}+\cdots+{}_{2n+1}\mathrm{C}_{2n})\)

両辺\(2\)で割って、\({}_{2n+1}\mathrm{C}_{0}\)が余分なので、これだけ数値にします。

\(2^{2n}=1+{}_{2n+1}\mathrm{C}_{2}+{}_{2n+1}\mathrm{C}_{4}+\cdots+{}_{2n+1}\mathrm{C}_{2n}\)

よって
\({}_{2n+1}\mathrm{C}_{2}+{}_{2n+1}\mathrm{C}_{4}+\cdots+{}_{2n+1}\mathrm{C}_{2n}=4^n-1\)

したがって
(与式)\(=\displaystyle\frac{1}{2n+1}\displaystyle\sum_{k=0}^{n-1}{}_{2n+1}\mathrm{C}_{2k+2}\)

\(=\displaystyle\frac{4^{n}-1}{2n+1}\)

(積分を利用した別解)
\((1+x)^{2n}\)
\(={}_{2n}\mathrm{C}_{0}+{}_{2n}\mathrm{C}_{1}x+{}_{2n}\mathrm{C}_{2}x^2+{}_{2n}\mathrm{C}_{3}x^3+\cdots+{}_{2n}\mathrm{C}_{2n}x^{2n}\)

\(x\)について積分すると
\(\displaystyle\frac{(1+x)^{2n+1}}{2n+1}\)
\(={}_{2n}\mathrm{C}_{0}x+\displaystyle\frac{{}_{2n}\mathrm{C}_{1}}{2}x^2+\displaystyle\frac{{}_{2n}\mathrm{C}_{2}}{3}x^3+\displaystyle\frac{{}_{2n}\mathrm{C}_{3}}{4}x^4+\cdots+\displaystyle\frac{{}_{2n}\mathrm{C}_{2n-1}}{2n}x^{2n}+\displaystyle\frac{{}_{2n}\mathrm{C}_{2n}}{2n+1}x^{2n+1}+D\)・・・④
(\(D\)は積分定数)

④に\(x=0\)を代入することで \(D=\displaystyle\frac{1}{2n+1}\) となることが分かる。

④で\(x=1,-1\) を代入すると
\(\displaystyle\frac{2^{2n+1}}{2n+1}\)
\(={}_{2n}\mathrm{C}_{0}+\displaystyle\frac{{}_{2n}\mathrm{C}_{1}}{2}+\displaystyle\frac{{}_{2n}\mathrm{C}_{2}}{3}+\displaystyle\frac{{}_{2n}\mathrm{C}_{3}}{4}+\cdots+\displaystyle\frac{{}_{2n}\mathrm{C}_{2n-1}}{2n}+\displaystyle\frac{{}_{2n}\mathrm{C}_{2n}}{2n+1}+D\)・・・⑤

\(0\)
\(=-{}_{2n}\mathrm{C}_{0}+\displaystyle\frac{{}_{2n}\mathrm{C}_{1}}{2}-\displaystyle\frac{{}_{2n}\mathrm{C}_{2}}{3}+\displaystyle\frac{{}_{2n}\mathrm{C}_{3}}{4}+\cdots+\displaystyle\frac{{}_{2n}\mathrm{C}_{2n-1}}{2n}-\displaystyle\frac{{}_{2n}\mathrm{C}_{2n}}{2n+1}+D\)・・・⑥

(偶数番目の項が必要なので)

⑤+⑥より
\(\displaystyle\frac{2^{2n+1}}{2n+1}=2\{\displaystyle\frac{{}_{2n}\mathrm{C}_{1}}{2}+\displaystyle\frac{{}_{2n}\mathrm{C}_{3}}{4}+\cdots+\displaystyle\frac{{}_{2n}\mathrm{C}_{2n-1}}{2n}+D\}\)

\(\displaystyle\frac{2^{2n}}{2n+1}=\displaystyle\frac{{}_{2n}\mathrm{C}_{1}}{2}+\displaystyle\frac{{}_{2n}\mathrm{C}_{3}}{4}+\cdots+\displaystyle\frac{{}_{2n}\mathrm{C}_{2n-1}}{2n}+\displaystyle\frac{1}{2n+1}\)

よって
\(\displaystyle\frac{4^{n}-1}{2n+1}=\displaystyle\frac{{}_{2n}\mathrm{C}_{1}}{2}+\displaystyle\frac{{}_{2n}\mathrm{C}_{3}}{4}+\cdots+\displaystyle\frac{{}_{2n}\mathrm{C}_{2n-1}}{2n}\)・・・⑦

(⑦の右辺)
\(=\displaystyle\sum_{k=0}^{n-1}\displaystyle\frac{{}_{2n}\mathrm{C}_{2k+1}}{2k+2}\) だから

\(\displaystyle\sum_{k=0}^{n-1}\displaystyle\frac{{}_{2n}\mathrm{C}_{2k+1}}{2k+2}=\displaystyle\frac{4^{n}-1}{2n+1}\)

(例題3)
異なる\(n\)個のものから\(r\)個をとる組の総数を\({}_n\mathrm{C}_r\)とする。ただし、\({}_0\mathrm{C}_0=1\)である。等式
\({}_n\mathrm{C}_r=\displaystyle\sum_{k=1}^{n-r+1}{}_{n-k}\mathrm{C}_{n-k-r+1}\)
が任意の自然数\(n,r\)　(\(n≧r≧1\))　について成立することを示せ。ただし、必要ならば等式
\({}_{n+1}\mathrm{C}_r={}_n\mathrm{C}_r+{}_n\mathrm{C}_{r-1}\)　(\(r≧1\), \(n≧r\))
を利用してもよい。

まずは、\(\displaystyle\sum_{k=1}^{n-r+1}{}_{n-k}\mathrm{C}_{n-k-r+1}\) について整理していきます。
ちなみに利用する後半の等式については意味で考えると、\(n+1\)人から\(r\)人選ぶのは「(特定の\(A\)さんを選ばない場合、残りの\(n\)人から\(r\)人選ぶ) + (\(A\)さんを選ぶ場合、残りの\(n\)人から\(r-1\)人選ぶ)」ということです。(数式処理でも証明できます)

(解答)
\({}_{n-k}\mathrm{C}_{n-k-r+1}\)
\(={}_{n-k}\mathrm{C}_{(n-k)-(n-k-r+1)}\)
\(={}_{n-k}\mathrm{C}_{r-1}\) より

\(\displaystyle\sum_{k=1}^{n-r+1}{}_{n-k}\mathrm{C}_{n-k-r+1}\)
\(=\displaystyle\sum_{k=1}^{n-r+1}{}_{n-k}\mathrm{C}_{r-1}\)・・・①

ここで、\({}_{n+1}\mathrm{C}_r={}_n\mathrm{C}_r+{}_n\mathrm{C}_{r-1}\) (\(r≧1\), \(n≧r\))　を利用します。部分分数分解のときのように差の形を意識して
\({}_{n+1}\mathrm{C}_r-{}_n\mathrm{C}_r={}_n\mathrm{C}_{r-1}\)　(左辺は左下の数字が1個違いで、右下の数字が同じ)
において、①のシグマの中身ができるように\(n\)に\(n-k\)を代入すると
\({}_{n-k+1}\mathrm{C}_r-{}_{n-k}\mathrm{C}_r={}_{n-k}\mathrm{C}_{r-1}\) (\(r≧1\), \(n-k≧r\))
となりますが、不等式の部分は\(k\)について解くと \(k≦n-r\) となるので、①のシグマの項を \(1≦k≦n-r\) と \(k=n-r+1\) に分けます。(後の変形で分かりますが、\(k=n-r+1\)を含めると \({}_{r-1}\mathrm{C}_r\) という式が出てきてしまう)

ここで、
\({}_{n+1}\mathrm{C}_r={}_n\mathrm{C}_r+{}_n\mathrm{C}_{r-1}\)　(\(r≧1\), \(n≧r\))

の\(n\)に\(n-k\)を代入すると
\(\color{blue}{{}_{n-k+1}\mathrm{C}_r-{}_{n-k}\mathrm{C}_r={}_{n-k}\mathrm{C}_{r-1}}\) (\(r≧1\), \(n-k≧r\))

となり、\(k≦n-r\) より①は
\(\displaystyle\sum_{k=1}^{n-r+1}{}_{n-k}\mathrm{C}_{r-1}\)
\(=\displaystyle\sum_{k=1}^{n-r}\color{blue}{{}_{n-k}\mathrm{C}_{r-1}}+{}_{r-1}\mathrm{C}_{r-1}\)
\(=\displaystyle\sum_{k=1}^{n-r}(\color{blue}{{}_{n-k+1}\mathrm{C}_r-{}_{n-k}\mathrm{C}_r})+1\)

あとは、\(k=1,2,\cdots,n-r\) と代入すると途中の項が打ち消されることになります。このとき\(k=n-r+1\)を含めていると、右側の \({}_{n-k}\mathrm{C}_r\) が \({}_{r-1}\mathrm{C}_r\) になってしまいます。

\(=\{({}_{n}\mathrm{C}_{r}-\bcancel{{}_{n-1}\mathrm{C}_{r}})+(\bcancel{{}_{n-1}\mathrm{C}_{r}}-\bcancel{{}_{n-2}\mathrm{C}_{r}})+\cdots+(\bcancel{{}_{r+1}\mathrm{C}_{r}}-{}_{r}\mathrm{C}_{r})\}+1\)
\(={}_{n}\mathrm{C}_{r}-{}_{r}\mathrm{C}_{r}+1\)
\(={}_{n}\mathrm{C}_{r}\)

したがって
\({}_n\mathrm{C}_r=\displaystyle\sum_{k=1}^{n-r+1}{}_{n-k}\mathrm{C}_{n-k-r+1}\)
が成り立つ。

(参考)
\(\displaystyle\sum_{k=1}^{n-r+1}{}_{n-k}\mathrm{C}_{r-1}\)・・・①
具体的に書くと証明したい等式は

\({}_n\mathrm{C}_r={}_{n-1}\mathrm{C}_{r-1}+{}_{n-2}\mathrm{C}_{r-1}+{}_{n-3}\mathrm{C}_{r-1}+\cdots+{}_{r-1}\mathrm{C}_{r-1}\)

ですが、異なる\(n\)個のものに\(1\)から\(n\)までの番号をつけると、\({}_n\mathrm{C}_r\)つまり異なる\(n\)個から\(r\)個を選ぶ方法の総数は次の選び方の和になることがわかります。

・最大の番号が\(n\)のとき、残り\(n-1\)個から\(r-1\)個選ぶから \({}_{n-1}\mathrm{C}_{r-1}\) 通り
・最大の番号が\(n-1\)のとき、残り\(n-2\)個から\(r-1\)個選ぶから \({}_{n-2}\mathrm{C}_{r-1}\) 通り
・最大の番号が\(n-2\)のとき、残り\(n-3\)個から\(r-1\)個選ぶから \({}_{n-3}\mathrm{C}_{r-1}\) 通り
\(\cdots\)
・最大の番号が\(r\)のとき、残り\(r-1\)個から\(r-1\)個選ぶから \({}_{r-1}\mathrm{C}_{r-1}\) 通り
(最大の番号がこれより小さくなることはあり得ない)

以上になります。お疲れさまでした。
ここまで見ていただきありがとうございました。
next→絶対値の和　 back→組合せと数列